Abstract
The cyclability of a graph H, denoted by C(H), is the largest integer r such that H has a cycle through any r vertices. For a claw-free graph H, by Ryjáček (J Comb Theory Ser B 70:217–224, 1997) closure concept, there is a \(K_3\)-free graph G such that the closure \(cl(H)=L(G)\). In this note, we prove that for a 3-connected claw-free graph H with its closure \(cl(H)=L(G)\), \(C(H)\ge 12\) if and only if G can not be contracted to the Petersen graph in such a way that each vertex in P is obtained by contracting a nontrivial connected \(K_3\)-free subgraph. This is an improvement of the main result in Györi and Plummer (Stud Sci Math Hung 38:233–244, 2001).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aldred, R.E.L., Bau, S., Holton, D.A., McKay, B.: Cycles through 23 vertices in 3-connected cubic planar graphs. Graphs Comb. 15, 373–376 (1999)
Bau, S., Holton, D.: Cycles containing 12 vertices in 3-connected cubic graphs. J. Graph Theory 15, 421–429 (1991)
Bilinski, M., Jackson, B., Ma, J., Yu, X.: Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs. J. Comb. Theory Ser. B 101(4), 214–236 (2011)
Cada, R.: The *-closure for graphs and claw-free graphs. Discret. Math. 308, 5585–5596 (2008)
Chvátal, V.: New directions in Hamiltonian graph theory. New directions in the theory of graphs. In: Harary, F. (ed.) Proc. Third Ann Arbor Conf. Graph Theory, Univ. Michigan, Ann Arbor, MI 1971, pp. 65–95. Academic Press, New York (1973)
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 Theorey 42, 308–319 (2003)
Ellingham, M.N., Holton, D.A., Little, C.H.C.: Cycles through ten vertices in 3-connected cubic graphs. Combinatorica 4(4), 265–273 (1984)
Gould, R.: A look at cycles containing specified elements of a graph. Discret. Math. 309, 6299–6311 (2009)
Györi, E., Plummer, M.D.: A nine vertex theorem for 3-connected claw-free graphs. Stud. Sci. Math. Hung. 38, 233–244 (2001)
Harary, F., Nash-Williams, C.St.J.A.: On Eulerian and Hamiltonian graphs and line graphs. Can. Math. Bull. 8, 701–710 (1965)
Holton, D.A., McKay, B.D., Plummer, M.D., Thomassen, C.: A nine point theorem for 3-connected graphs. Combinatorica 2, 53–62 (1982)
Holton, D.A., Sheehan, J.: The Petersen Graph. Cambridge University Press, Cambridge (1993)
Markus, L.R.: Degree, neighbourhood and claw conditions versus traversability in graphs. Ph.D. Thesis, Department of Mathematics, Vanderbilt University (1992)
Roussopoulos, N.D.: A max\(\{m, n\}\) algorithm for determining the graph \(H\) from its line graph \(G\). Inf. Process. Lett. 2, 108–112 (1973)
Ryjáček, Z.: On a closure concept in claw-free graphs. J. Comb. Theory Ser. B 70, 217–224 (1997)
Shao, Y.: Claw-free graphs and line graphs. Ph.D dissertation, West Virginia University (2005)
Author information
Authors and Affiliations
Corresponding author
Additional information
Research is supported by Butler University Academic Grant (2014).
Rights and permissions
About this article
Cite this article
Chen, ZH. A Twelve Vertex Theorem for 3-Connected Claw-Free Graphs. Graphs and Combinatorics 32, 553–558 (2016). https://doi.org/10.1007/s00373-015-1608-4
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-015-1608-4