The minimum size of graphs Hamiltonian-connected from a vertex (Q1119940)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The minimum size of graphs Hamiltonian-connected from a vertex |
scientific article |
Statements
The minimum size of graphs Hamiltonian-connected from a vertex (English)
0 references
1989
0 references
A graph G is Hamiltonian-connected from a vertex v (hc from v) if there exists a v-u Hamiltonian path for all u in \(G=\{v\}\). \textit{G. Chartrand} and \textit{E. A. Nordhaus} [The theory and applications of graphs, 4th int. Conf. Kalamazoo/Mich. 1980, 189-201 (1981; Zbl 0471.05052)] proved that if a graph of order p is Hamiltonian-connected from a vertex then the number of edges in G is at least \(\lceil (5p-1)/4\rceil\) (where \(\lceil \rceil\) denotes the least integer function). In this note we present a collection of graphs of arbitrarily large order, each Hamiltonian-connected from a vertex, which have p vertices and exactly \(\lceil (5p-1)/4\rceil\) edges.
0 references