Partitioning a graph into cycles with a specified number of chords

DOI10.1002/JGT.22534MaRDI QIDQ5066898zbMATH OpenOpenAlexFDO

Authors Shuya Chiba, Jin Yan, Su-yun Jiang

Publication date 31 March 2022

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.03893

zbMATH Keywords

chorded cyclescyclesdegree sum conditionspartitions

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: For a graph $G$, let $sigm{a}_2(G)$ be the minimum degree sum of two non-adjacent vertices in $G$. A chord of a cycle in a graph $G$ is an edge of $G$ joining two non-consecutive vertices of the cycle. In this paper, we prove the following result, which is an extension of a result of Brandt et al. (J. Graph Theory 24 (1997) 165-173) for large graphs: For positive integers $k$ and $c$, there exists an integer $f(k,c)$ such that, if $G$ is a graph of order $ngef(k,c)$ and $sigm{a}_2(G)gen$, then $G$ can be partitioned into $k$ vertex-disjoint cycles, each of which has at least $c$ chords.

Recommendations

• Partitioning chordal graphs
• scientific article; zbMATH DE number 617574
• Partition of a graph into cycles and vertices
• Cycle Partitions in Graphs
• Partitioning graphs into paths or cycles of prescribed lengths
• scientific article; zbMATH DE number 2101287
• Partition of a bipartite graph into cycles
• scientific article; zbMATH DE number 2186975
• Graph partition problems into cycles and paths
• Decompositions of graphs into cycles with chords

Cited in

(9)

• Partitioning graphs into paths or cycles of prescribed lengths
• Results and problems on chorded cycles: a survey
• Partitioning chordal graphs
• scientific article; zbMATH DE number 5914863 (Why is no real title available?)
• scientific article; zbMATH DE number 617574 (Why is no real title available?)
• scientific article; zbMATH DE number 2094820 (Why is no real title available?)
• Chorded cycles
• LATIN 2004: Theoretical Informatics
• On vertex-disjoint chorded cycles and degree sum conditions

This page was built for publication: Partitioning a graph into cycles with a specified number of chords

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5066898)