The minimum size of graphs Hamiltonian-connected from a vertex
type: Item
instance of: scholarly article
title: The minimum size of graphs Hamiltonian-connected from a vertex
zbMATH Open document ID: 0672.05058
DOI: 10.1016/0012-365X(89)90325-7
author: C. J. Knickerbocker
author: Patti Frazer Lock
author: Michael Sheard
published in: Discrete Mathematics
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 4099357
MaRDI profile type: Publication
cites work: Q3924248
cites work: Graphs uniquely Hamiltonian-connected from a vertex
description: scientific article; zbMATH DE number 4099357