The property of Hamiltonian connectedness in Toeplitz graphs (Q2173741)

From MaRDI portal
scientific article
Language Label Description Also known as
English
The property of Hamiltonian connectedness in Toeplitz graphs
scientific article

    Statements

    The property of Hamiltonian connectedness in Toeplitz graphs (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    17 April 2020
    0 references
    Summary: A spanning path in a graph \(G\) is called a Hamiltonian path. To determine which graphs possess such paths is an NP-complete problem. A graph \(G\) is called Hamiltonian-connected if any two vertices of \(G\) are connected by a Hamiltonian path. We consider here the family of Toeplitz graphs. About them, it is known only for \(n=3\) that \(T_n\left\langle p, q\right\rangle\) is Hamiltonian-connected, while some particular cases of \(T_n\left\langle p, q, r\right\rangle\) for \(p=1\) and \(q=2,3,4\) have also been investigated regarding Hamiltonian connectedness. Here, we prove that the nonbipartite Toeplitz graph \(T_n\left\langle 1, q, r\right\rangle\) is Hamiltonian-connected for all \(1<q<r<n\) and \(n\geq5r-2\).
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references