×

Circumferences of 3-connected claw-free graphs. (English) Zbl 1333.05158

Summary: In M. Li et al. [ibid. 309, No. 11, 3580–3587 (2009; Zbl 1229.05180)], proved that a 3-connected claw-free graph of order \(n\) with minimum degree \(\delta\) contains a cycle of length at least \(\min \{n, 6 \delta - 15 \}\), and they conjectured that such graphs should have a cycle of length at least \(\min \{n, 9 \delta - 3 \}\). We prove that this conjecture is true with \(\delta \geq 8\).

MSC:

05C38 Paths and cycles
05C12 Distance in graphs
05C40 Connectivity
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Citations:

Zbl 1229.05180
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), American Elsevier: American Elsevier New York · Zbl 1134.05001
[2] Catlin, P. A., A reduction method to find spanning Eulerian subgraphs, J. Graph Theory, 12, 29-45 (1988) · Zbl 0659.05073
[3] Catlin, P. A.; Han, Z.; Lai, H.-J., Graphs without spanning Eulerian trails, Discrete Math., 160, 81-91 (1996) · Zbl 0859.05060
[4] Chen, W.-G.; Chen, Z.-H., Fan-type conditions for spanning Eulerian subgraphs, Graphs Combin., 31, 2087-2102 (2015) · Zbl 1327.05239
[5] Chen, Z.-H.; Lai, H.-J.; Li, X. W.; Li, D. Y.; Mao, J. Z., Eulerian subgraphs in 3-edge-connected graphs and Hamiltonian line graphs, J. Graph Theory, 42, 308-319 (2003) · Zbl 1018.05059
[6] Dirac, G., Some theorems on abstract graphs, Proc. Lond. Math. Soc., 2, 69-81 (1952) · Zbl 0047.17001
[7] Harary, F.; Nash-Williams, C. St. J.A., On Eulerian and Hamiltonian graphs and line graphs, Canad. Math. Bull., 8, 701-710 (1965) · Zbl 0136.44704
[8] Lai, H.-J.; Shao, Y.; Zhan, M., Hamiltonicity in 3-connected claw-free graphs, J. Combin. Theory Ser. B, 96, 493-504 (2006) · Zbl 1095.05024
[9] Li, M.; Cui, Y.; Xiong, L. M.; Tian, Y.; Jiang, H.; Yuan, X., Circumferences and minimum degrees in 3-connected claw-free graphs, Discrete Math., 309, 3580-3587 (2009) · Zbl 1229.05180
[10] Mathews, M. M.; Sumner, D. P., Longest paths and cycles in \(K_{1, 3}\)-free graphs, J. Graph Theory, 9, 269-277 (1985) · Zbl 0591.05041
[11] Roussopoulos, N. D., A max \(\{m, n \}\) algorithm for determining the graph \(H\) from its line graph \(G\), Inform. Process. Lett., 2, 108-112 (1973) · Zbl 0274.05116
[12] Ryjáček, Z., On a closure concept in claw-free graphs, J. Combin. Theory Ser. B, 70, 217-224 (1997) · Zbl 0872.05032
[13] Shao, Y., Claw-free graphs and line graphs (2005), West Virginia University, (Ph.D. dissertation)
[14] Veldman, H. J., On dominating and spanning circuits in graphs, Discrete Math., 124, 229-239 (1994) · Zbl 0789.05061
[15] Voss, H. J.; Zuluaga, C., Maximal gerade and ungerade kreise in graphen, I. Wiss Z. Techn. Hochsch. Ilmenau, 23, 4, 57-70 (1977) · Zbl 0366.05039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.