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
    0 references
    0 references
    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

    Identifiers