Vertex-dominating cycles in 2-connected bipartite graphs
Discussiones Mathematicae Graph Theory (2007)
- Volume: 27, Issue: 2, page 323-332
- ISSN: 2083-5892
Access Full Article
top
Abstract
topHow to cite
topTomoki Yamashita. "Vertex-dominating cycles in 2-connected bipartite graphs." Discussiones Mathematicae Graph Theory 27.2 (2007): 323-332. <http://eudml.org/doc/270355>.
@article{TomokiYamashita2007,
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.},
author = {Tomoki Yamashita},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {vertex-dominating cycle; dominating cycle; bipartite graph},
language = {eng},
number = {2},
pages = {323-332},
title = {Vertex-dominating cycles in 2-connected bipartite graphs},
url = {http://eudml.org/doc/270355},
volume = {27},
year = {2007},
}
TY - JOUR
AU - Tomoki Yamashita
TI - Vertex-dominating cycles in 2-connected bipartite graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2007
VL - 27
IS - 2
SP - 323
EP - 332
AB - 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.
LA - eng
KW - vertex-dominating cycle; dominating cycle; bipartite graph
UR - http://eudml.org/doc/270355
ER -
References
top- [1] P. Ash and B. Jackson, Dominating cycles in bipartite graphs, in: Progress in Graph Theory, 1984, 81-87. Zbl0562.05032
- [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). Zbl0409.05037
- [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. Zbl0634.05045
- [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. Zbl0399.05039
- [7] J. Moon and L. Moser, On hamiltonian bipartite graphs, Israel J. Math. 1 (1963) 163-165, doi: 10.1007/BF02759704. Zbl0119.38806
- [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. Zbl1073.05558
- [10] H. Wang, On Long Cycles in a 2-connected Bipartite Graph, Graphs and Combin. 12 (1996) 373-384, doi: 10.1007/BF01858470. Zbl0864.05051
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.