ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory 27(1) (2007) 179-191
DOI: 10.7151/dmgt.1354


Daniel Paulusma

Department of Computer Science, Durham University
Science Laboratories, South Road, Durham DH1 3LE, England

Kiyoshi Yoshimoto

Department of Mathematics
College of Science and Technology
Nihon University, Tokyo 101-8308, Japan


Let G be a triangle-free graph with δ(G) ≥ 2 and σ4(G) ≥ |V(G)|+2. Let S ⊂ V(G) consist of less than σ4/4+ 1 vertices. We prove the following. If all vertices of S have degree at least three, then there exists a cycle C containing S. Both the upper bound on |S| and the lower bound on σ4 are best possible.

Keywords: cycle, path, triangle-free graph.

2000 Mathematics Subject Classification: 05C38, 05C45.


[1] P. Ash and B. Jackson, Dominating cycles in bipartite graphs, in: Progress in Graph Theory, J.A. Bondy, U.S.R. Murty, eds., (Academic Press, 1984), 81-87.
[2] B. Bollobás and G. Brightwell, Cycles through specified vertices, Combinatorica 13 (1993) 137-155.
[3] J.A. Bondy, Longest Paths and Cycles in Graphs of High Degree, Research Report CORR 80-16 (1980).
[4] J.A. Bondy and L. Lovász, Cycles through specified vertices of a graph, Combinatorica 1 (1981) 117-140, doi: 10.1007/BF02579268.
[5] H. Broersma, H. Li, J. Li, F. Tian and H.J. Veldman, Cycles through subsets with large degree sums, Discrete Math. 171 (1997) 43-54, doi: 10.1016/S0012-365X(96)00071-4.
[6] R. Diestel, Graph Theory, Second edition, Graduate Texts in Mathematics 173, Springer (2000).
[7] Y. Egawa, R. Glas and S.C. Locke, Cycles and paths trough specified vertices in k-connected graphs, J. Combin. Theory (B) 52 (1991) 20-29, doi: 10.1016/0095-8956(91)90086-Y.
[8] J. Harant, On paths and cycles through specified vertices, Discrete Math. 286 (2004) 95-98, doi: 10.1016/j.disc.2003.11.059.
[9] H. Enomoto, J. van den Heuvel, A. Kaneko and A. Saito, Relative length of long paths and cycles in graphs with large degree sums, J. Graph Theory 20 (1995) 213-225, doi: 10.1002/jgt.3190200210.
[10] D.A. Holton, Cycles through specified vertices in k-connected regular graphs, Ars Combin. 13 (1982) 129-143.
[11] O. Ore, Note on hamiltonian circuits, American Mathematical Monthly 67 (1960) 55, doi: 10.2307/2308928.
[12] K. Ota, Cycles through prescribed vertices with large degree sum, Discrete Math. 145 (1995) 201-210, doi: 10.1016/0012-365X(94)00036-I.
[13] D. Paulusma and K. Yoshimoto, Relative length of longest paths and longest cycles in triangle-free graphs, submitted,
[14] A. Saito, Long cycles through specified vertices in a graph, J. Combin. Theory (B) 47 (1989) 220-230, doi: 10.1016/0095-8956(89)90021-X.
[15] L. Stacho, Cycles through specified vertices in 1-tough graphs, Ars Combin. 56 (2000) 263-269.
[16] K. Yoshimoto, Edge degree conditions and all longest cycles which are dominating, submitted.
[17] S.J. Zheng, Cycles and paths through specified vertices, Journal of Nanjing Normal University, Natural Science Edition, Nanjing Shida Xuebao, Ziran Kexue Ban 23 (2000) 9-13.

Received 8 March 2006
Revised 31 October 2006