Large degree vertices in longest cycles of graphs, II

Binlong Li, Liming Xiong, Jun Yin

Abstract


In this paper, we consider the least integer d such that every k-connected graph G of order n (and of independent number α) has a longest cycle containing all vertices of degree at least d. We completely determine the d when k = 2. We propose a conjecture for those k-connected graph, where k ≥ 3.


Keywords


longest cycle, connectivity, independent number, large degree vertex

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2019.7.2.7

References

B. Bollobas and G. Brightwell, Cycles through specified vertices, Combinatorica 13 (2) (1993), 147--155.

J.A. Bondy and V. Chvatal, A method in graph theory, Discrete Math. 15 (2) (1976), 111--135.

J.A. Bondy and U.S.R. Murty, Graph Theory, Springer, 2008.

V. Chvatal and P. Erdos, A note on Hamiltonian circuits, Discrete Math. 2 (1972), 111--113.

G.A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. 3 (2) (1952), 69--81.

Y. Guo, A. Pinkernell and L. Volkmann, On cycles through a given vertex in multipartite tournaments, Discrete Math. 164 (1997), 165--170.

J. Harant, S. Jendrol and H. Walther, On long cycles through four prescribed vertices of a polyhedral graph, Discuss. Math. Graph Theory 28 (3) (2008), 441--451.

B. Li, H.J. Broersma and S. Zhang, Forbidden subgraph pairs for traceability of block-chains, Electron. J. Graph Theory Appl. 1 (1) (2013), 1--10.

B. Li, L. Xiong and J. Yin, Large degree vertices in longest cycles of graphs, I, Discuss. Math. Graph Theory 36 (2016), 363--382.

B. Li and S. Zhang, Forbidden subgraphs for longest cycles to

contain vertices with large degree, Discrete Math. 338 (2015), 1681--1689.

D. Paulusma and K. Yoshimoto, Cycles through specified vertices in triangle-free graphs, Discuss. Math. Graph Theory 27 (2007), 179--191.

A. Saito, Long cycles through specified vertices in a graph, J. Combin. Theory Ser. B 47 (1989), 220--230.

A. Shabbir, C.T. Zamfirescu and T.I. Zamfirescu, Intersecting longest paths and longest cycles: A survey, Electron. J. Graph Theory Appl. 1 (1) (2013), 56--76.

R. Shi, 2-neighborhoods and Hamiltonian conditions, J. Graph Theory 16 (1992), 267--271.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats