The Number of Minimal Vertex Covers in the Product of Stars or Paths

星形或路徑乘積圖中最小點覆蓋計數

10.29850/LTJ.200806.0002

周敏貞(Min-Jen Jou)；林正忠(Jenq-Jong Lin)

最小點覆蓋 ； 乘積 ； 星形 ； 路徑 ； minimal vertex cover ； product ； star ； path

嶺東學報

23期（2008 / 06 / 01）

11 - 20

英文

圖形G之點覆蓋，爲G點集之子集合S，且使得圖形G中任一邊的兩個端點，至少有一個屬於S‧若一點覆蓋的子集合均不爲點覆蓋，則稱此點覆蓋爲最小點覆蓋。兩個圖形G和H之（卡式）乘積圖G×H定義爲具有點集V(G)×V(H)且當u1=v1，u2與v2在H中相鄰或當u2=v2，u1與v1在G中相鄰，則稱(u1, u2)與(v1,v2)在G×H中相鄰。在本篇論文中，我們確定了星形或星形與點數不大於5之路徑乘積圖中最小點覆蓋的數目。

Suppose G is a graph. A set S ⊆ V (G) is called a vertex cover of G if each edge of G is incident with at least one vertex of S. A minimal vertex cover is a vertex cover which contains no proper vertex cover. The product (also called cartesian product) G×H of two graphs G and H with vertex sets V (G) and V (H), respectively, has the cartesian product V (G)×V (H) as its set of vertices. Two vertices (u1, u2) and (v1, v2) are adjacent if u1=v1, u2 and v2 are adjacent in H or u2=v2, u1 and v1 are adjacent in G. In this paper, we determine the number of minimal vertex covers in the product of two stars or of a star and a path of order at most 5.

1. Gary Chartrand,Linda Lesniak(1986).Graphs and digraphs.California:Wadsworth, Inc..
2. J. Chen,I. A. Kanj,W. Jia(2001).Vertex cover: further obserations and further improvements.Journal of Algorithms,41,280-301.
3. R. M. Karp,R. E. Miller(Eds.),J. W. Thatcher(Eds.)(1972).Complexity of Computer Computation.New York:Plenum Press.
4. S. Khuri,T. Back,G. I. Bonn (Ed.)(1994).An evolutionary heuristic for the minimum vertex cover problem.Proceedings of KI-94 Workshops, the 18th German Annual Conference on Artificial Intelligence
5. Xinshun Xu,Jun Ma(2006).An efficient simulated annealing algorithm for the minimum vertex cover problem.Neurocomputing,69,913-916.