Minimum path cover in quasi-claw-free graphs
type: Item
instance of: scholarly article
title: Minimum path cover in quasi-claw-free graphs
zbMATH Open document ID: 1457.05084
author: Mingda Liu
author: Huiqing Liu
author: Xiaodong Chen
published in: Bulletin of the Iranian Mathematical Society
publication date: 2020-07-14T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 7220173
zbMATH Keywords: minimum path cover
zbMATH Keywords: path cover number
zbMATH Keywords: quasi-claw-free graph
zbMATH Keywords: non-insertable vertex
MaRDI profile type: Publication
full work available at URL: s41980-019-00294-4
OpenAlex ID: W2980914077
cites work: Quasi-claw-free graphs
cites work: Q3097395
cites work: Hamiltonicity for K1, r‐free graphs
cites work: Some Theorems on Abstract Graphs
cites work: Variations on the Gallai-Milgram theorem
cites work: On domination in connected cubic graphs
cites work: Arc coverings of graphs
cites work: Note on Hamilton Circuits
cites work: Covering 2‐connected 3‐regular graphs with disjoint paths
cites work: Hamilton cycles in claw-free graphs
DOI: 10.1007/S41980-019-00294-4
description: scientific article; zbMATH DE number 7220173