On the structure of graphs uniquely hamiltonian-connected from a vertex (Q2639074): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3818315 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3924248 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Graphs uniquely Hamiltonian-connected from a vertex / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The size of graphs uniquely Hamiltonian-connected from a vertex / rank | |||
Normal rank |
Latest revision as of 13:54, 21 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the structure of graphs uniquely hamiltonian-connected from a vertex |
scientific article |
Statements
On the structure of graphs uniquely hamiltonian-connected from a vertex (English)
0 references
1991
0 references
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.
0 references
structural investigations of a special class of graphs
0 references
Hamiltonian connectivity
0 references