Weak cycle partition involving degree sum conditions
type: Item
instance of: scholarly article
title: Weak cycle partition involving degree sum conditions
zbMATH Open document ID: 1170.05038
author: Hao Li
author: Zhiquan Hu
published in: Discrete Mathematics
publication date: 2009-04-09T00:00:00Z
review text: 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\}\).
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 5542361
zbMATH Keywords: degenerated cycle partition
zbMATH Keywords: weak cycle partition
zbMATH Keywords: degree sum
reviewed by: Dalibor Fronček
MaRDI profile type: Publication
full work available at URL: j.disc.2007.12.081
OpenAlex ID: W2088610017
cites work: Degree conditions for 2-factors
cites work: Partition of a graph into cycles and degenerated cycles
cites work: Partition of a graph into cycles and vertices
DOI: 10.1016/J.DISC.2007.12.081
Recommended article: On vertex-disjoint cycles and degree sum conditions
Recommended article: Degree sum conditions on two disjoint cycles in graphs
Recommended article: Degree sum conditions for vertex-disjoint cycles passing through specified vertices
Recommended article: Q5480718
Recommended article: Cycle Partitions in Graphs
Recommended article: Q5442611
Recommended article: Degree sum conditions for cyclability in bipartite graphs
Recommended article: Decomposition of the product of cycles based on degree partition
Recommended article: Degree sums and dominating cycles
Recommended article: Partition of a graph into cycles and degenerated cycles
description: scientific article; zbMATH DE number 5542361