Cycle Traversability for Claw-Free Graphs and Polyhedral Maps
Tóm tắt
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
Tài liệu tham khảo
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.