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\}\).
- On vertex-disjoint cycles and degree sum conditions
- Degree sum conditions on two disjoint cycles in graphs
- Degree sum conditions for vertex-disjoint cycles passing through specified vertices
- Degree sum conditions and vertex-disjoint cycles in a graph
- Cycle Partitions in Graphs
- Degree sum conditions and Chvátal-Erdös conditions for cycles
- Degree sum conditions for cyclability in bipartite graphs
- Decomposition of the product of cycles based on degree partition
- Degree sums and dominating cycles
- Partition of a graph into cycles and degenerated cycles
- Degree conditions for the partition of a graph into cycles, edges and isolated vertices
- Degree conditions for the existence of vertex-disjoint cycles and paths: a survey
- Partitioning the vertices of a digraph into directed cycles and degenerated directed cycles
- On partitioning a bipartite graph into cycles and degenerated cycles
- Partition of a graph into cycles and vertices
This page was built for publication: Weak cycle partition involving degree sum conditions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1011695)
