PDF

Discussiones Mathematicae Graph Theory 27(2) (2007) 323-332
DOI: https://doi.org/10.7151/dmgt.1364

VERTEX-DOMINATING CYCLES IN 2-CONNECTED BIPARTITE GRAPHS

Tomoki Yamashita

Department of Mathematics
School of Dentistry, Asahi University
1851 Hozumi, Gifu 501-0296, Japan
e-mail: tomoki@dent.asahi-u.ac.jp

Abstract

A cycle C is a vertex-dominating cycle if every vertex is adjacent to some vertex of C. Bondy and Fan [4] showed that if G is a 2-connected graph with δ(G) ≥ [1/3](|V(G)| −4), then G has a vertex-dominating cycle. In this paper, we prove that if G is a 2-connected bipartite graph with partite sets V₁ and V₂ such that δ(G) ≥ [1/3]( max{|V₁|, |V₂|}+1), then G has a vertex-dominating cycle.

Keywords: vertex-dominating cycle, dominating cycle, bipartite graph.

2000 Mathematics Subject Classification: 05C38, 05C45.

References

[1]	P. Ash and B. Jackson, Dominating cycles in bipartite graphs, in: Progress in Graph Theory, 1984, 81-87.
[2]	D. Bauer, H.J. Veldman, A. Morgana and E.F. Schmeichel, Long cycles in graphs with large degree sum, Discrete Math. 79 (1989/90) 59-70, doi: 10.1016/0012-365X(90)90055-M.
[3]	J.A. Bondy, Longest paths and cycles in graphs with high degree, Research Report CORR 80-16, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada (1980).
[4]	J.A. Bondy and G. Fan, A sufficient condition for dominating cycles, Discrete Math. 67 (1987) 205-208, doi: 10.1016/0012-365X(87)90029-X.
[5]	R. Diestel, Graph Theory, (2nd ed.) (Springer-Verlag, 2000).
[6]	H.A. Jung, On maximal circuits in finite graphs, Ann. Discrete Math. 3 (1978) 129-144, doi: 10.1016/S0167-5060(08)70503-X.
[7]	J. Moon and L. Moser, On hamiltonian bipartite graphs, Israel J. Math. 1 (1963) 163-165, doi: 10.1007/BF02759704.
[8]	O. Ore, Note on Hamilton circuits, Amer. Math. Monthly 67 (1960) 55, doi: 10.2307/2308928.
[9]	A. Saito and T. Yamashita, A Note on Dominating Cycles in Tough Graphs, Ars Combinatoria 69 (2003) 3-8.
[10]	H. Wang, On Long Cycles in a 2-connected Bipartite Graph, Graphs and Combin. 12 (1996) 373-384, doi: 10.1007/BF01858470.

Received 28 April 2006
Revised 23 February 2007
Accepted 23 February 2007