Abstract
Let G be a graph, and \(v \in V(G)\) and \(S \subseteq V(G)\setminus{v}\) of size at least k. An important result on graph connectivity due to Perfect states that, if v and S are k-linked, then a (k−1)-link between a vertex v and S can be extended to a k-link between v and S such that the endvertices of the (k−1)-link are also the endvertices of the k-link. We begin by proving a generalization of Perfect's result by showing that, if two disjoint sets S1 and S2 are k-linked, then a t-link (t<k) between two disjoint sets S1 and S2 can be extended to a k-link between S1 and S2 such that the endvertices of the t-link are preserved in the k-link.
Next, we are able to use these results to show that a 3-connected claw-free graph always has a cycle passing through any given five vertices, but avoiding any other one specified vertex. We also show that this result is sharp by exhibiting an infinite family of 3-connected claw-free graphs in which there is no cycle containing a certain set of six vertices but avoiding a seventh specified vertex. A direct corollary of our main result shows that a 3-connected claw-free graph has a topological wheel minor Wk with k ≤ 5 if and only if it has a vertex of degree at least k.
Finally, we also show that a graph polyhedrally embedded in a surface always has a cycle passing through any given three vertices, but avoiding any other specified vertex. The result is best possible in the sense that the polyhedral embedding assumption is necessary, and there are infinitely many graphs polyhedrally embedded in surfaces having no cycle containing a certain set of four vertices but avoiding a fifth specified vertex.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
J. A. Bondy and L. Lovász: Cycles through specified vertices of a graph, Combinatorica1 (1981), 117–140.
Z. Chen: A twelve vertex theorem for 3-connected claw-free graphs, Graphs Combin.32 (2016), 553–558.
M. Chudnovsky and P. D. Seymour: The structure of claw-free graphs, in: Surveys in Combinatorics, London Math. Soc. Lecture Note Ser., 327, Cambridge Univ. Press, Cambridge, 2005, 153–171.
V. Chvátal: New directions in Hamiltonian graph theory, (Proc. Third Ann Arbor Conf. Graph Theory, Univ. Michigan, Ann Arbor, Mich., 1971), Academic Press, New York, 1973, 65–95.
G. A. Dirac: In abstrakten graphen vorhandene vollständige 4-graphen und ihre unterteilungen, Math. Nachr.22 (1960), 61–85.
M. N. Ellingham, D. A. Holton and C. H.C. Little: Cycles through ten vertices in 3-connected cubic graphs, Combinatorica4 (1984), 265–273.
R. Faudree, E. Flandrin and Z. Ryjáček: Claw-free graphs–a survey, Discrete Math.164 (1997), 87–147.
E. Flandrin, E. Győri, H. Li and J. Shu: Cyclability in k-connected K1,4-free graphs, Discrete Math.310 (2010), 2735–2741.
R. Gould: A look at cycles containing specified elements of a graph, Discrete Math.309 (2009), 6299–6311.
E. Győri and M. D. Plummer: A nine vertex theorem for 3-connected claw-free graphs, Stud. Sci. Math. Hungar.38 (2001), 233–244.
R. Häggkvist and W. Mader: Circuits through prescribed vertices in k-connected k-regular graphs, J. Graph Theory39 (2002), 145–163.
R. Häggkvist and C. Thomassen: Circuits through specified edges, Discrete Math.41 (1982), 29–34.
R. Halin: Zur Theorie der n-fach zusammenhängenden Graphen, Abh. Math. Sem Hamburg33 (1969), 133–164.
D. A. Holton, B. D. McKay, M. D. Plummer and C. Thomassen: A nine point theorem for 3-connected graphs, Combinatorica2 (1982), 53–62.
D. A. Holton and M. D. Plummer: Cycles through prescribed and forbidden point sets, (Workshop on Combinatorial Optimization, Bonn, 1980), Ann. Discrete Math.16, North-Holland, 1982, 129–147.
D. A. Holton and C. Thomassen: Research problem 81, Discrete Math.62 (1986), 111–112.
K. Kawarabayashi: One or two disjoint circuits cover independent edges: Lovász—Woodall Conjecture, J. Combin. Theory Ser. B84 (2002), 1–44.
K. Kawarabayashi: Cycles through a prescribed vertex set in N-connected graphs, J. Combin. Theory Ser. B90 (2004), 315–323.
A. K. Kelmans and M. V. Lomonosov: When m vertices in a k-connected graph cannot be walked round along a simple cycle, Discrete Math.38 (1982), 317–322.
L. Lovász, Problem 5, Per. Math. Hungar.4 (1974), 82.
M. M. Matthews and D. P. Sumner: Hamiltonian results in K1;3-free graphs, J. Graph Theory8 (1984), 139–146.
D. M. Mesner and M. E. Watkins: Some theorems about n-vertex connected graphs, J. Math. Mech.16 (1966), 321–326.
B. Mohar and C. Thomassen: Graphs on Surfaces, Hopkins Univ. Press, Baltimore, 2001.
D. A. Nelson: Hamiltonian Graphs, M.A. Thesis, Vanderbilt University, 1973.
H. Perfect: Applications of Menger's Graph Theorem, J. Math. Anal. Appl.22 (1968), 96–111.
M. D. Plummer and E. Wilson: On cycles and connectivity in planar graphs, Canad. Math. Bull.16 (1973), 283–288.
G. T. Sallee: Circuits and paths through specified nodes, J. Combin. Theory Ser. B15 (1973), 32–39.
R. Thomas and X. Yu: 4-connected projective-planar graphs are Hamiltonian, J. Combin. Theory Ser. B62 (1994), 114–132.
W. T. Tutte: A theorem on planar graphs, Trans. Amer. Math. Soc.82 (1956), 99–116.
M. E. Watkins and D. M. Mesner: Cycles and connectivity in graphs, Canad. J. Math.19 (1967), 1319–1328.
D. R. Woodall: Circuits containing specified edges, J. Combin. Theory Ser. B22 (1977), 274–278.
Acknowledgments
The authors would like to thank the referees for their valuable comments.
Author information
Authors and Affiliations
Corresponding author
Additional information
Partially supported by the NKFIH Grant K116769.
Partially supported by a grant from the Simons Foundation (No. 359516).
Rights and permissions
About this article
Cite this article
Győri, E., Plummer, M.D., Ye, D. et al. Cycle Traversability for Claw-Free Graphs and Polyhedral Maps. Combinatorica 40, 405–433 (2020). https://doi.org/10.1007/s00493-019-4042-z
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00493-019-4042-z