Cycle intersection graphs and minimum decycling sets of even graphs

DOI10.1142/S1793830920500275MaRDI QIDQ4965894zbMATH OpenOpenAlexFDO

Authors Michael Cary

Publication date 18 March 2021

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

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

zbMATH Keywords

even graphspanning treedecycling numberdecyclingcycle rank

Mathematics Subject Classification ID

Trees (05C05) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38)

Abstract: We introduce the cycle intersection graph of a graph, an adaptation of the cycle graph of a graph, and use the structure of these graphs to prove an upper bound for the decycling number of all even graphs. This bound is shown to be significantly better when an even graph admits a cycle decomposition in which any two cycles intersect in at most one vertex. Links between the cycle rank of the cycle intersection graph of an even graph and the decycling number of the even graph itself are found. The problem of choosing an ideal cycle decomposition is addressed and is presented as an optimization problem over the space of cycle decompositions of even graphs.

Recommendations

• Decycling graphs
• Even cycle decompositions of 4-regular graphs and line graphs
• Decycling cubes and grids
• Even-cycle decompositions of graphs with no odd-\(K_4\)-minor
• Strongly even-cycle decomposable graphs

Cites work

• scientific article; zbMATH DE number 54781 (Why is no real title available?)
• scientific article; zbMATH DE number 1744105 (Why is no real title available?)
• scientific article; zbMATH DE number 819129 (Why is no real title available?)
• A reduction method to find spanning Eulerian subgraphs
• A simple proof of an inequality connecting the alternating number of independent sets and the decycling number
• Combinatorial Geometry and Graph Theory
• Decycling bubble sort graphs
• Decycling cubes and grids
• Decycling graphs
• Decycling hypercubes
• Decycling numbers of random regular graphs
• Decycling sets in certain Cartesian product graphs with one factor complete
• Large induced forests in triangle-free planar graphs
• On inverse problems for the cycle graph operator
• Reducibility among combinatorial problems
• The Decycling Number of Cubic Planar Graphs
• The decycling number of generalized Petersen graphs
• The decycling number of regular graphs
• Vertices with the second neighborhood property in Eulerian digraphs

Cited in

(1)

• Vertices with the second neighborhood property in Eulerian digraphs

This page was built for publication: Cycle intersection graphs and minimum decycling sets of even graphs

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