The minimum size of graphs Hamiltonian-connected from a vertex
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.
scientific article; zbMATH DE number 4099357