### Large degree vertices in longest cycles of graphs, II

#### 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

#### Full Text:

PDFDOI: 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

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