Cycle intersection graphs and minimum decycling sets of even graphs

DOI10.1142/S1793830920500275zbMATH Open1456.05031arXiv1810.04252OpenAlexW3003939283MaRDI QIDQ4965894FDOQ4965894

Authors: Michael Cary 

Publication date: 18 March 2021

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

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.

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

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

zbMATH Keywords

even graphspanning treedecycling numberdecyclingcycle rank

Mathematics Subject Classification ID

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

Cites Work

• Reducibility among combinatorial problems
• A reduction method to find spanning Eulerian subgraphs
• Decycling hypercubes
• Decycling graphs
• Decycling numbers of random regular graphs
• Large induced forests in triangle-free planar graphs
• Title not available (Why is that?)
• A simple proof of an inequality connecting the alternating number of independent sets and the decycling number
• The decycling number of regular graphs
• The decycling number of generalized Petersen graphs
• Decycling bubble sort graphs
• Decycling cubes and grids
• Title not available (Why is that?)
• On inverse problems for the cycle graph operator
• Title not available (Why is that?)
• The Decycling Number of Cubic Planar Graphs
• Combinatorial Geometry and Graph Theory
• Decycling sets in certain Cartesian product graphs with one factor complete
• 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)