×

Clique-heavy subgraphs and pancyclicity of 2-connected graphs. (English) Zbl 1388.05146

Summary: Graph \(G\) on \(n\) vertices is said to be pancyclic if it contains cycles of all lengths \(k\) for \(k\in\{3,\dots,n\}\). A vertex \(v\in V(G)\) is called super-heavy if the number of its neighbours in \(G\) is at least \((n+1)/2\). The complete bipartite graph \(K_{1, 3}\) is called a claw.
For a given graph \(H\) we say that \(G\) is \(H\)-\(\mathrm c_1\)-heavy if for every induced subgraph \(K\) of \(G\) isomorphic to \(H\) and every maximal clique \(C\) in \(K\) there is a super-heavy vertex in every non-trivial component of \(K-C\); and that \(G\) is \(H\)-\(\mathrm o_1\)-heavy if in every induced subgraph of \(G\) isomorphic to \(H\) there are two non-adjacent vertices with sum of degrees at least \(|G|+1\). Let \(Z_1\) denote a graph consisting of a triangle with a pendant edge.
In this paper we prove that every 2-connected \(K_{1, 3}\)-\(\mathrm o_1\)-heavy and \(Z_1\)-\(\mathrm c_1\)-heavy graph is pancyclic. As a consequence we obtain a complete characterization of graphs \(H\) such that every 2-connected graph claw-\(\mathrm o_1\)-heavy and \(H\)-\(\mathrm c_1\)-heavy graph is pancyclic. This result extends previous work by P. Bedrossian [Forbidden subgraph and minimum degree conditions for Hamiltonicity. Memphis, TN: Memphis State University (PhD Thesis) (1991)].

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C45 Eulerian and Hamiltonian graphs
05C40 Connectivity
Full Text: DOI

References:

[1] Bedrossian, P., Forbidden subgraph and minimum degree conditions for Hamiltonicity (1991), Memphis State University: Memphis State University USA, PhD thesis
[2] Benhocine, A.; Wojda, A., The Geng-Hua Fan conditions for pancyclic or Hamilton-connected graphs, J. Comb. Theory, Ser. B, 58, 167-180 (1987) · Zbl 0613.05038
[3] Bondy, J., Pancyclic graphs I, J. Comb. Theory, Ser. B, 11, 80-84 (1971) · Zbl 0183.52301
[4] Bondy, J.; Murty, U., Graph Theory with Applications (1976), Macmillan London and Elsevier: Macmillan London and Elsevier New York · Zbl 1226.05083
[5] Faudree, R. J.; Gould, R. J., Characterizing forbidden pairs for hamiltonian properties, Discrete Math., 173, 45-60 (1997) · Zbl 0879.05050
[6] Li, B.; Ning, B., Heavy subgraphs, stability and hamiltonicity (Jun. 2015), arXiv e-prints
[7] Li, B.; Ning, B.; Broersma, H.; Zhang, S., Characterizing heavy subgraph pairs for pancyclicity, Graphs Comb., 31, 3, 649-667 (2015) · Zbl 1312.05092
[8] Li, B.; Ryjáček, Z.; Wang, Y.; Zhang, S., Pairs of heavy subgraphs for hamiltonicity of 2-connected graphs, SIAM J. Discrete Math., 26, 3, 1088-1103 (2012) · Zbl 1256.05052
[9] Ferrara, M.; Jacobson, M. S.; Harris, A., Cycle lengths in Hamiltonian graphs with a pair of vertices having large degree sum, Graphs Comb., 26, 215-223 (2010) · Zbl 1230.05179
[10] Ore, O., Note on Hamilton circuits, Am. Math. Mon., 67, 1, 55 (1960) · Zbl 0089.39505
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.