Graphs uniquely Hamiltonian-connected from a vertex (Q790840)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Graphs uniquely Hamiltonian-connected from a vertex |
scientific article |
Statements
Graphs uniquely Hamiltonian-connected from a vertex (English)
0 references
1984
0 references
A graph G is called Hamiltonian-connected from a vertex v of G if G contains a Hamiltonian v-w path for each vertex \(w\neq v\). Such graphs have been studied by \textit{G. Chartrand} and \textit{E. A. Nordhaus} [4th Int. Conf., Kalamazoo/Mich. 1980, 189-201 (1981; Zbl 0471.05052)]. Furthermore if the v-w path is unique for each vertex \(w\neq v\) the author calls it uniquely Hamiltonian-connected from v. He constructs several families of graphs with this property and gives many necessary conditions on it. For example, if G is uniquely Hamiltonian-connected from v, has order n, \(n\geq 3\), then n is odd, the degree of v is even and G has at most (3n-3)/2 edges. Despite these results such graphs are not characterized and the author asks many questions about them.
0 references
Hamiltonian path
0 references
Hamiltonian connected
0 references