Remarks on component factors in \(K_{1,r}\)-free graphs. (English) Zbl 1514.05128
Summary: An \(\mathcal{F}\)-factor is a spanning subgraph \(H\) such that each connected component of \(H\) is isomorphic to some graph in \(\mathcal{F}\). We use \(P_k\) and \(K_{1,r}\) to denote the path of order \(k\) and the star of order \(r + 1\), respectively. In particular, \(H\) is called a \(\{ P_2, P_3\}\)-factor of \(G\) if \(\mathcal{F} = \{P_2, P_3\}; H\) is called a \(P_{\geq k}\)-factor of \(G\) if \(\mathcal{F} = \{P_k, P_{k+1},\ldots\}\), where \(k \geq 2; H\) is called an \(\mathcal{S}_n\)-factor of \(G\) if \(\mathcal{F} = \{P_2, P_3, K_{1,3},\ldots, K_{1,n}\}\), where \(n \geq 2\). A graph \(G\) is called a \(\mathcal{P}_{\geq k}\)-factor covered graph if there is a \(\mathcal{P}_{\geq k}\)-factor of \(G\) including \(e\) for any \(e \in E(G)\). We call a graph \(G\) is \(K_{1,r}\)-free if \(G\) does not contain an induced subgraph isomorphic to \(K_{1,r}\). In this paper, we give a minimum degree condition for the \(K_{1,r}\)-free graph with an \(\mathcal{S}_n\)-factor and the \(K_{1,r}\)-free graph with a \(\mathcal{P}_{\geq 3}\)-factor, respectively. Further, we obtain sufficient conditions for \(K_{1,r}\)-free graphs to be \(\mathcal{P}_{\geq 2}\)-factor, \(\mathcal{P}_{\geq 3}\)-factor or \(\{P_2, P_3\}\)-factor covered graphs. In addition, examples show that our results are sharp.
MSC:
05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
05C38 | Paths and cycles |