No label defined (Q4522110)

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.