- Tytuł:
- Nested Locally Hamiltonian Graphs and the Oberly-Sumner Conjecture
- Autorzy:
-
de Wet, Johan P.
Frick, Marietjie - Powiązania:
- https://bibliotekanauki.pl/articles/32222536.pdf
- Data publikacji:
- 2022-11-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
locally traceable
locally hamiltonian
Hamilton Cycle Problem
locally k -nested-hamiltonian
Oberly-Sumner Conjecture - Opis:
- A graph G is locally P, abbreviated L, if for every vertex v in G the open neighbourhood N(v) of v is non-empty and induces a graph with property P. Specifically, a graph G without isolated vertices is locally connected (LC) if N(v) induces a connected graph for each v ∈ V (G), and locally hamiltonian (LH) if N(v) induces a hamiltonian graph for each v ∈ V (G). A graph G is locally locally P (abbreviated L2P) if N(v) is non-empty and induces a locally P graph for every v ∈ V (G). This concept is generalized to an arbitrary degree of nesting. For any k ≥ 0 we call a graph locally k-nested-hamiltonian if it is LmC for m = 0, 1, . . ., k and LkH (with L0C and L0H meaning connected and hamiltonian, respectively). The class of locally k-nested-hamiltonian graphs contains important subclasses. For example, Skupień had already observed in 1963 that the class of connected LH graphs (which is the class of locally 1-nested-hamiltonian graphs) contains all triangulations of closed surfaces. We show that for any k ≥ 1 the class of locally k-nested-hamiltonian graphs contains all simple-clique (k + 2)-trees. In 1979 Oberly and Sumner proved that every connected K1,3-free graph that is locally connected is hamiltonian. They conjectured that for k ≥ 1, every connected K1,k+3-free graph that is locally (k + 1)-connected is hamiltonian. We show that locally k-nested-hamiltonian graphs are locally (k + 1)-connected and consider the weaker conjecture that every K1,k+3-free graph that is locally k-nested-hamiltonian is hamiltonian. We show that if our conjecture is true, it would be “best possible” in the sense that for every k ≥ 1 there exist K1,k+4-free locally k-nested-hamiltonian graphs that are non-hamiltonian. We also attempt to determine the minimum order of non-hamiltonian locally k-nested-hamiltonian graphs and investigate the complexity of the Hamilton Cycle Problem for locally k-nested-hamiltonian graphs with restricted maximum degree.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2022, 42, 4; 1281-1312
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł