Minimum path cover in quasi-claw-free graphs (Q779733)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Minimum path cover in quasi-claw-free graphs
scientific article

    Statements

    Minimum path cover in quasi-claw-free graphs (English)
    0 references
    0 references
    0 references
    0 references
    14 July 2020
    0 references
    A collection \(\mathcal{P}\) of vertex disjoint paths of a graph \(G\) is called a path cover of \(G\) if any vertex of \(G\) belongs to some path in \(\mathcal{P}\). The path cover number of \(G\), denoted by \(p(G)\), is defined to be \(\min \{|\mathcal{P}| : \mathcal{P} \mbox{ is a path cover of } \)G\(\}\). Let \(N(v)\) (\(N[v]\)) denote the open (closed) neighborhood of a vertex \(v\). A graph \(G\) is called quasi-claw-free if the following condition holds. For any two vertices \(x\) and \(y\) at distance 2 in \(G\), there exists a vertex \(u\) such that \(u \in N(x) \cap N(y)\) and \(N(u) \subseteq N[x] \cup N[y]\). Let \(\sigma_{k+1}(G)\) denote the minimum degree sum of an independent set with \(k+1\) vertices in \(G\). The main result of this paper states as follows. Let \(G\) be a quasi-claw-free graph on \(n\) vertices. Then \(p(G) \leq k\) if \(\sigma_{k+1}(G) \geq n-k\) for some positive integer \(k\).
    0 references
    minimum path cover
    0 references
    path cover number
    0 references
    quasi-claw-free graph
    0 references
    non-insertable vertex
    0 references

    Identifiers