Large Degree Vertices in Longest Cycles of Graphs, I

Binlong Li; Liming Xiong; Jun Yin

Discussiones Mathematicae Graph Theory (2016)

  • Volume: 36, Issue: 2, page 363-382
  • ISSN: 2083-5892

Abstract

top
In this paper, we consider the least integer d such that every longest cycle of a k-connected graph of order n (and of independent number α) contains all vertices of degree at least d.

How to cite

top

Binlong Li, Liming Xiong, and Jun Yin. "Large Degree Vertices in Longest Cycles of Graphs, I." Discussiones Mathematicae Graph Theory 36.2 (2016): 363-382. <http://eudml.org/doc/277123>.

@article{BinlongLi2016,
abstract = {In this paper, we consider the least integer d such that every longest cycle of a k-connected graph of order n (and of independent number α) contains all vertices of degree at least d.},
author = {Binlong Li, Liming Xiong, Jun Yin},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {longest cycle; large degree vertices; order; connectivity; independent number},
language = {eng},
number = {2},
pages = {363-382},
title = {Large Degree Vertices in Longest Cycles of Graphs, I},
url = {http://eudml.org/doc/277123},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Binlong Li
AU - Liming Xiong
AU - Jun Yin
TI - Large Degree Vertices in Longest Cycles of Graphs, I
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 2
SP - 363
EP - 382
AB - In this paper, we consider the least integer d such that every longest cycle of a k-connected graph of order n (and of independent number α) contains all vertices of degree at least d.
LA - eng
KW - longest cycle; large degree vertices; order; connectivity; independent number
UR - http://eudml.org/doc/277123
ER -

References

top
  1. [1] B. Bollobás and G. Brightwell, Cycles through specified vertices, Combinatorica 13 (1993) 147-155. doi:10.1007/BF01303200[Crossref] Zbl0780.05033
  2. [2] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer-Verlag, London, 2008). 
  3. [3] V. Chvátal and P. Erdős, A note on Hamiltonian circuits, Discrete Math. 2 (1972) 111-113. doi:10.1016/0012-365X(72)90079-9[Crossref] 
  4. [4] G.A. Dirac, Some theorems on abstract graphs, Proc. Lond. Math. Soc. (3)2 (1952) 69-81. doi:10.1112/plms/s3-2.1.69[Crossref] 
  5. [5] M. Kouider, Cycles in graphs with prescribed stability number and connectivity, J. Combin. Theory Ser. B 60 (1994) 315-318. doi:10.1006/jctb.1994.1023[Crossref] Zbl0805.05045
  6. [6] B. Li and S. Zhang, Forbidden subgraphs for longest cycles to contain vertices with large degree, Discrete Math. 338 (2015) 1681-1689. doi:10.1016/j.disc.2014.07.003[Crossref][WoS] 
  7. [7] D. Paulusma and K. Yoshimoto, Cycles through specified vertices in triangle-free graphs, Discuss. Math. Graph Theory 27 (2007) 179-191. doi:10.7151/dmgt.1354[Crossref] Zbl1134.05043
  8. [8] A. Saito, Long cycles through specified vertices in a graph, J. Combin. Theory Ser. B 47 (1989) 220-230. doi:10.1016/0095-8956(89)90021-X[Crossref] 
  9. [9] R. Shi, 2-neighborhoods and Hamiltonian conditions, J. Graph Theory 16 (1992) 267-271. doi:10.1002/jgt.3190160310[Crossref] Zbl0761.05066
  10. [10] S. O, D.B. West and H. Wu, Longest cycles in k-connected graphs with given inde- pendence number , J. Combin. Theory Ser. B 101 (2011) 480-485. doi:10.1016/j.jctb.2011.02.005[Crossref] 

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.