Weak cycle partition involving degree sum conditions
Let \(G\) be a graph of order \(n\) and \(k\) be a positive integer. A set of mutually vertex-disjoint subgraphs \(\mathcal H=\{H_1,H_2,\dots,H_k\}\) of \(G\) with \(\bigcup_{i=1}^{k}V(H_i)=V(G)\) is called a \(k\)-degenerated cycle partition (\(k\)-DCP) if every \(H_i\) for \(i=1,2,\dots,k\) is either a cycle or \(K_1\) or \(K_2\). \(\mathcal H\) is called a \(k\)-weak cycle partition (\(k\)-WCP) if every \(H_i\) for \(i=1,2,\dots,k\) is either a cycle or \(K_1\). It is proved that if \(G\) is a graph with \(n\geq k+12\) that has a \(k\)-DCP and the degree sum of any two non-adjacent vertices is at least \(\frac{3n+6k-5}{4}\), then either \(G\) has a \(k\)-WCP or \(k=2\) and \(G\) is a subgraph of \(K_2\cup K_{n-2}\cup\{e\}\), where \(e\) is an edge connecting \(V(K_{2})\) and \(V(K_{n-2})\). Using this result, the authors improve a previous result by \textit{H. Enomoto} and \textit{H. Li} [``Partition of graphs into cycles and degenerated cycles'', Discrete Math. 276, No. 1--3, 177--181 (2004; Zbl 1031.05103)] for \(n\geq \max\{k+12, 10k-9\}\).
scientific article; zbMATH DE number 5542361