On the structure of graphs uniquely hamiltonian-connected from a vertex
A graph \(\underline G=(\underline V,\underline A)\) with \(| \underline V| =p\) is said to be uniquely hamiltonian-connected from a vertex v (uhc from v) if for every vertex u in \(\underline G-\underline v\), there is a unique hamiltonian path \(\underline H_{\underline u}\) in \(\underline G\). In this paper are only considered graphs with \(p>3\). For such graphs already Hendry has shown that \(\deg(v)\) must be even and p must be odd, moreover he showed that the number of edges in \(\underline G\) equals \(3(p-1)/2\) and that every vertex in \(\underline V(\underline G)-\{\underline v\}\) has degree 2,3, or 4; he got additional results and he formulated problems and open questions on the structure of graphs uhc from v. In this paper the structural investigations are continued, and many notions are necessary for this, for instance: - An edge \(e=xy\) in \(\underline G\) which lies on every hamiltonian path of \(\underline G\) starting at v is called a forced edge; - If x is adjacent to y in \(\underline H_{\underline y}\) x is said to be penultimate to y, written: \(x=p(y);\) - In this case the edge \(e=xy\) is called ultimate edge. Using many lemmas the authors obtain the following main results for graphs \(\underline G\) uhc from v: - An edge \(e=xy\) is a forced edge of \(\underline G\) iff \(x=p(y)\) and \(y=p(x)\) (Theorem 2.5); - If \(\deg(v)=2\) and \(a=p(b)\), then the (ultimate) edge \(e=ab\) lies on the unique hamiltonian cycle of \(\underline G\) (Corollary 4.5 which is a consequence of Theorem 4.4); - General case: If \(a=p(b)\), then the (ultimate) edge \(e=ab\) lies on every hamiltonian cycle of \(\underline G\) (Theorem 5.4); - Consequence of Theorem 5.4: If \(a=p(b)\) then the (ultimate) edge \(e=ab\) lies on the unique hamiltonian cycle of \(\underline G-\underline v\) (Corollary 6.1). By using these results the authors also answer to five of the six above- mentioned questions from Hendry whether a graph can be uhc from more than one vertex. Theorem 6.2 yields a relevant result: A graph \(\underline G\) can be uhc from at most three vertices. Furthermore, if \(\underline G\) is uhc from more than one vertex, then all distinguished vertices must have degree 2.
- The size of graphs uniquely Hamiltonian-connected from a vertex
- The structure of transform graphs
- Forbidden subgraphs of graphs uniquely Hamiltonian-connected from a vertex
- Uniquely Hamiltonian graphs of minimum degree 4
- scientific article; zbMATH DE number 867696 (Why is no real title available?)
- Graphs uniquely Hamiltonian-connected from a vertex
- A degree constraint for uniquely Hamiltonian graphs
This page was built for publication: On the structure of graphs uniquely hamiltonian-connected from a vertex
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2639074)
