Odd Cycle Transversals and Independent Sets in Fullerene Graphs

DOI10.1137/120870463zbMATH Open1256.05116arXiv1203.3912OpenAlexW3098079216MaRDI QIDQ4899070FDOQ4899070

Authors: Sulamita Klein, Matěj Stehlík, Luerbio Faria 

Publication date: 4 January 2013

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: A fullerene graph is a cubic bridgeless plane graph with all faces of size 5 and 6. We show that that every fullerene graph on n vertices can be made bipartite by deleting at most sqrt{12n/5} edges, and has an independent set with at least n/2-sqrt{3n/5} vertices. Both bounds are sharp, and we characterise the extremal graphs. This proves conjectures of Doslic and Vukicevic, and of Daugherty. We deduce two further conjectures on the independence number of fullerene graphs, as well as a new upper bound on the smallest eigenvalue of a fullerene graph.

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

Recommendations

• Nice pairs of odd cycles in fullerene graphs
• Odd cycle transversal in mixed graphs
• A note on the cyclical edge-connectivity of fullerene graphs
• Cycle transversals in perfect graphs and cographs
• On the anti-Kekulé number and odd cycle transversal of regular graphs
• On independent cycles and edges in graphs
• Generalizations of Cliques, Odd Cycles and Anticycles and Their Relation to Independence System Polyhedra
• On the number of independent sets in cycle-separated tricyclic graphs
• On finite \(s\)-transitive graphs of odd order
• Extremal even-cycle-free subgraphs of the complete transposition graphs

zbMATH Keywords

independent setmax-cutfullerene graphodd cycle transversal

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Applications of graph theory (05C90) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38)

Cited In (15)

• Long cycles in fullerene graphs
• On the anti-Kekulé number and odd cycle transversal of regular graphs
• The anti-Kekulé number of graphs
• Bipartizing fullerenes
• Patches with short boundaries
• Packing resonant hexagons in fullerenes
• Large independent sets in subquartic planar graphs
• On correlation of hyperbolic volumes of fullerenes with their properties
• Packing and covering odd cycles in cubic plane graphs with small faces
• Packing and covering odd cycles in cubic plane graphs with small faces
• Odd cycle transversal in mixed graphs
• Bipartite edge frustration and maximum independent set problems on fulleroids-\((3,4,6)\)
• The independence numbers of fullerenes and benzenoids
• On two Graffiti conjectures about fullerene graphs
• Local metric dimension for graphs with small clique numbers

This page was built for publication: Odd Cycle Transversals and Independent Sets in Fullerene Graphs

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