×

Global cycle properties of locally isometric graphs. (English) Zbl 1333.05173

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 the property of having diameter at most \(k\) for some fixed \(k \geq 1\). For \(k = 2\) these graphs are called locally isometric graphs. For \(\varDelta \leq 5\), we obtain a complete structural characterization of locally isometric graphs that are not fully cycle extendable. For \(\varDelta = 6\), it is shown that locally isometric graphs that are not fully cycle extendable contain a pair of true twins of degree 6. Infinite classes of locally isometric graphs with \(\varDelta = 6\) that are not fully cycle extendable are described and observations are made that suggest that a complete characterization of these graphs is unlikely. It is shown that Ryjáček’s conjecture holds for all locally isometric graphs with \(\varDelta \leq 6\). The Hamilton cycle problem for locally isometric graphs with maximum degree at most 8 is shown to be NP-complete.

MSC:

05C45 Eulerian and Hamiltonian graphs
05C38 Paths and cycles
05C12 Distance in graphs
05C07 Vertex degrees
PDFBibTeX XMLCite
Full Text: DOI arXiv

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)
[8] Dirac, G. A., Some theorems on abstract graphs, Proc. Lond. Math. Soc., 2, 69-81 (1952) · Zbl 0047.17001
[9] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco · Zbl 0411.68039
[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], Latv. Math. Yearbook, 16, 33-38 (1975)
[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] Plesník, J., The NP-completeness of the Hamiltonian cycle problem in bipartite cubic planar graphs, Acta Math. Univ. Comenian, 42-43, 271-273 (1983) · Zbl 0539.05043
[20] 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
[21] Skupień, Z., Locally Hamiltonian and planar graphs, Fund. Math., 58, 193-200 (1966) · Zbl 0141.40903
[23] 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.