scientific article; zbMATH DE number 1545702
Let \(G\) be an undirected, simple graph. \(G\) is locally Hamiltonian (respectively traceable) if for every vertex \(v\) in \(G\), the subgraph induced by the neighbourhood of \(v\), is Hamiltonian (traceable). Furthermore a planar graph is maximal planar if no new edge can be added without destroying the planarity property. A planar graph is called outerplanar if it can be embedded in the plane in such a way that all its vertices are incident with the same face. \(G\) is locally connected if for any vertex \(v\), its neighbourhood is connected. From known results in connection with \(K_{1,3}\)-free graphs the author gets immediately the following: (1) If \(G\) is a \(K_{1,3}\)-free graph, then \(G\) is locally 2-connected iff it is locally Hamiltonian. (2) If \(G\) is a \(K_{1,3}\)-free graph, then \(G\) is locally connected iff it is locally traceable (Theorem 1). Therefore in the class of \(K_{1,3}\)-free graphs, all the results concerning locally 2-connected (respectively, locally connected) graphs also apply to locally Hamiltonian (locally traceable) graphs. The author investigates the structure of special locally Hamiltonian and locally traceable graphs. He obtains the least number of edges of such graphs depending on the order. These results are the following theorems: (3) If \(G\) is a connected outerplanar graph of order \(n\geq 3\), then \(G\) is locally traceable iff \(G\) is maximal outerplanar (Theorem 4). (4) If \(G\) is a connected planar graph of order \(n\geq 4\), then \(G\) is locally Hamiltonian iff \(G\) is maximal planar (Theorem 6). (5) Let \(G\) be a connected locally traceable graph of order \(n\geq 3\), then \(G\) contains at least \(2n-3\) edges (Theorem 5). (6) If \(G\) is a connected locally Hamiltonian graph of order \(n\geq 4\), then \(G\) contains at least \(3n-6\) edges (Theorem 7). The author conjectures that every connected locally Hamiltonian graph contains a spanning maximal planar subgraph.
- Hamiltonicity of locally Hamiltonian and locally traceable graphs
- scientific article; zbMATH DE number 4093499
- Traceability of locally Hamiltonian and locally traceable graphs
- Hamiltonian circuits in N2‐locally connected K1,3‐free graphs
- A necessary and sufficient condition for connected, locally k-connected k1,3-free graphs to be k-hamiltonian
- Hamiltonicity in locally finite graphs: two extensions and a counterexample
- Hamiltonicity of locally Hamiltonian and locally traceable graphs
- A localization method in Hamiltonian graph theory
- Nested locally Hamiltonian graphs and the Oberly-Sumner conjecture
- Locally Hamiltonian graphs and minimal size of maximal graphs on a surface
- A note on cycles in locally Hamiltonian and locally Hamilton-connected graphs
- Traceability of locally Hamiltonian and locally traceable graphs
- scientific article; zbMATH DE number 3869369 (Why is no real title available?)
- scientific article; zbMATH DE number 3959473 (Why is no real title available?)
- scientific article; zbMATH DE number 4093499 (Why is no real title available?)
- Weakly Hamiltonian-connected locally semicomplete digraphs
- Strongly Hamiltonian-connected locally semicomplete digraphs
- Long cycles and spanning subgraphs of locally maximal 1-planar graphs
- scientific article; zbMATH DE number 971360 (Why is no real title available?)
- Hamiltonian circuits in N2‐locally connected K1,3‐free graphs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4522110)
