Cycles through specified vertices in triangle-free graphs

Daniel Paulusma; Kiyoshi Yoshimoto

Discussiones Mathematicae Graph Theory (2007)

  • Volume: 27, Issue: 1, page 179-191
  • ISSN: 2083-5892

Abstract

top
Let G be a triangle-free graph with δ(G) ≥ 2 and σ₄(G) ≥ |V(G)| + 2. Let S ⊂ V(G) consist of less than σ₄/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 σ₄ are best possible.

How to cite

top

Daniel Paulusma, and Kiyoshi Yoshimoto. "Cycles through specified vertices in triangle-free graphs." Discussiones Mathematicae Graph Theory 27.1 (2007): 179-191. <http://eudml.org/doc/270311>.

@article{DanielPaulusma2007,
abstract = {Let G be a triangle-free graph with δ(G) ≥ 2 and σ₄(G) ≥ |V(G)| + 2. Let S ⊂ V(G) consist of less than σ₄/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 σ₄ are best possible.},
author = {Daniel Paulusma, Kiyoshi Yoshimoto},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {cycle; path; triangle-free graph},
language = {eng},
number = {1},
pages = {179-191},
title = {Cycles through specified vertices in triangle-free graphs},
url = {http://eudml.org/doc/270311},
volume = {27},
year = {2007},
}

TY - JOUR
AU - Daniel Paulusma
AU - Kiyoshi Yoshimoto
TI - Cycles through specified vertices in triangle-free graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2007
VL - 27
IS - 1
SP - 179
EP - 191
AB - Let G be a triangle-free graph with δ(G) ≥ 2 and σ₄(G) ≥ |V(G)| + 2. Let S ⊂ V(G) consist of less than σ₄/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 σ₄ are best possible.
LA - eng
KW - cycle; path; triangle-free graph
UR - http://eudml.org/doc/270311
ER -

References

top
  1. [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. Zbl0562.05032
  2. [2] B. Bollobás and G. Brightwell, Cycles through specified vertices, Combinatorica 13 (1993) 137-155. Zbl0780.05033
  3. [3] J.A. Bondy, Longest Paths and Cycles in Graphs of High Degree, Research Report CORR 80-16 (1980). 
  4. [4] J.A. Bondy and L. Lovász, Cycles through specified vertices of a graph, Combinatorica 1 (1981) 117-140, doi: 10.1007/BF02579268. Zbl0492.05049
  5. [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. Zbl0883.05089
  6. [6] R. Diestel, Graph Theory, Second edition, Graduate Texts in Mathematics 173, Springer (2000). 
  7. [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. Zbl0666.05044
  8. [8] J. Harant, On paths and cycles through specified vertices, Discrete Math. 286 (2004) 95-98, doi: 10.1016/j.disc.2003.11.059. Zbl1048.05050
  9. [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. Zbl0841.05057
  10. [10] D.A. Holton, Cycles through specified vertices in k-connected regular graphs, Ars Combin. 13 (1982) 129-143. Zbl0497.05036
  11. [11] O. Ore, Note on hamiltonian circuits, American Mathematical Monthly 67 (1960) 55, doi: 10.2307/2308928. Zbl0089.39505
  12. [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. Zbl0838.05071
  13. [13] D. Paulusma and K. Yoshimoto, Relative length of longest paths and longest cycles in triangle-free graphs, submitted, http://www.math.cst.nihon-u.ac.jp/yosimoto/paper/related_length1_sub.pdf. Zbl1134.05042
  14. [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. Zbl0686.05031
  15. [15] L. Stacho, Cycles through specified vertices in 1-tough graphs, Ars Combin. 56 (2000) 263-269. Zbl0994.05081
  16. [16] K. Yoshimoto, Edge degree conditions and all longest cycles which are dominating, submitted. 
  17. [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. Zbl0985.05031

NotesEmbed ?

top

You 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.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.