×

Global cycle properties in locally connected, locally traceable and locally Hamiltonian graphs. (English) Zbl 1333.05177

Summary: Let \(\mathcal{P}\) be a graph property. A graph \(G\) is said to be locally \(\mathcal{P}\) if the subgraph induced by the open neighbourhood of every vertex in \(G\) has property \(\mathcal{P}\). Ryjáček’s well-known conjecture that every connected, locally connected graph is weakly pancyclic motivated us to consider the global cycle structure of locally \(\mathcal{P}\) graphs, where \(\mathcal{P}\) is, in turn, ‘connected’, ‘traceable’ and ‘Hamiltonian’. We show that (i) the locally connected graphs with maximum degree at most 5 are all weakly pancyclic, but infinitely many are nonhamiltonian, (ii) all the connected, locally traceable graphs with maximum degree at most 5 are fully cycle extendable, except for three exceptional graphs, (iii) all the connected, locally Hamiltonian graphs with maximum degree at most 6 are fully cycle extendable, (iv) if \(G\) is a locally Hamiltonian graph \(G\) of order \(n\) and maximum degree at least \(n - 5\), then \(G\) is weakly pancyclic.

MSC:

05C45 Eulerian and Hamiltonian graphs
05C40 Connectivity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Akiyama, J.; Nishizeki, T.; Saito, N., NP-completeness of the Hamiltonian cycle problem for bipartite graphs, J. Inf. Process., 3, 73-76 (1980) · Zbl 0444.68058
[2] Bondy, J. A., Pancyclic graphs I, J. Combin. Theory, 11, 80-84 (1971) · Zbl 0183.52301
[3] Bondy, J. A., Pancyclic graphs: Recent results, infinite and finite sets, (Colloq. Math. Soc. János Bolyai (1973), Keszthely: Keszthely Hungary), 181-187
[4] Bondy, J. A.; Murty, U. S.R., Graph Theory (2008), Springer · Zbl 1134.05001
[5] Chartrand, G.; Gould, R.; Polimeni, A. D., A note on locally connected and Hamiltonian-connected graphs, Israel J. Math., 33, 5-8 (1979) · Zbl 0421.05048
[6] Chartrand, G.; Pippert, R. E., Locally connected graphs, Časopis Pěst. Mat., 99, 158-163 (1974) · Zbl 0278.05113
[7] Clark, L., Hamiltonian properties of connected locally connected graphs, Congr. Numer., 32, 199-204 (1981)
[9] Dirac, G. A., Some theorems on abstract graphs, Proc. Lond. Math. Soc., 2, 69-81 (1952) · Zbl 0047.17001
[10] Gordon, V. S.; Orlovich, Y. L.; Potts, C.; Strusevich, V. A., Hamiltonian properties of locally connected graphs with bounded vertex degree, Discrete Appl. Math., 159, 1759-1774 (2011) · Zbl 1228.05200
[11] Hendry, G. R.T., A strengthening of Kikust’s theorem, J. Graph Theory, 13, 257-260 (1989) · Zbl 0668.05042
[12] Hendry, G. R.T., Extending cycles in graphs, Discrete Math., 85, 59-72 (1990) · Zbl 0714.05038
[13] Kikust, P. B., The existence of a hamiltonian cycle in a regular graph of degree 5 [Russian, Latvian summary], (Latvian Mathematical Yearbook, Vol. 16 (1975)), 33-38
[14] Li, M.; Corneil, D. G.; Mendelsohn, E., Pancyclicity and NP-completeness in planar graphs, Discrete Appl. Math., 98, 3, 219-225 (2000) · Zbl 0939.05027
[15] Oberly, D. J.; Sumner, D. P., Every connected, locally connected nontrivial graph with no induced claw is Hamiltonian, J. Graph Theory, 3, 351-356 (1979) · Zbl 0424.05036
[16] Pareek, C. M., On the maximum degree of locally hamiltonian non-hamiltonian graphs, Util. Math., 23, 103-120 (1983) · Zbl 0523.05048
[17] Pareek, C. M.; Skupień, Z., On the smallest non-hamiltonian locally hamiltonian graph, J. Univ. Kuwait (Sci.), 10, 9-16 (1983) · Zbl 0514.05040
[18] Picouleau, C., Complexity of the Hamiltonian cycle in regular graph problem, Theoret. Comput. Sci, 131, 463-473 (1994) · Zbl 0809.68091
[19] Skupień, Z., Locally hamiltonian graphs and Kuratowski’s theorem, Bull. Acad. Pol. Sci., Ser. Sci. Math. Astron. Phys., 13, 615-619 (1965) · Zbl 0134.43106
[20] Skupień, Z., Locally Hamiltonian and planar graphs, Fund. Math., 58, 193-200 (1966) · Zbl 0141.40903
[22] West, D. B., Research problems, Discrete Math., 272, 301-306 (2003)
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.