On the structure of graphs uniquely hamiltonian-connected from a vertex (Q2639074)

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.