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.
- On the extremal number of edges in Hamiltonian connected graphs
- The size of graphs uniquely Hamiltonian-connected from a vertex
- Graphs uniquely Hamiltonian-connected from a vertex
- Maximum graphs non-Hamiltonian-connected from a vertex
- Hamiltonian-connected graphs with large neighborhoods and degrees
- On the extremal number of edges in Hamiltonian connected graphs
- The size of graphs uniquely Hamiltonian-connected from a vertex
- The structure of transform graphs
- The maximum degree of a minimally Hamiltonian-connected graph
- Maximum graphs non-Hamiltonian-connected from a vertex
- scientific article; zbMATH DE number 1247721 (Why is no real title available?)
This page was built for publication: The minimum size of graphs Hamiltonian-connected from a vertex
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1119940)
