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

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

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

《嶺東學報》 23期 (2008/06) Pp. 11-20

https://doi.org/10.29850/LTJ.200806.0002

摘要

圖形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.

並列關鍵字

minimal vertex cover ； product ； star ； path

參考文獻

J. Chen,I. A. Kanj,W. Jia(2001).Vertex cover: further obserations and further improvements.Journal of Algorithms.41,280-301.

Gary Chartrand,Linda Lesniak(1986).Graphs and digraphs.California:Wadsworth, Inc..

R. M. Karp,R. E. Miller(Eds.),J. W. Thatcher(Eds.)(1972).Complexity of Computer Computation.New York:Plenum Press.

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.(Proceedings of KI-94 Workshops, the 18th German Annual Conference on Artificial Intelligence).

Xinshun Xu,Jun Ma(2006).An efficient simulated annealing algorithm for the minimum vertex cover problem.Neurocomputing.69,913-916.