Odd Cycle Transversals and Independent Sets in Fullerene Graphs

DOI10.1137/120870463MaRDI QIDQ4899070zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

fullerene graphindependent setmax-cutodd cycle transversal

Mathematics Subject Classification ID

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

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.

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

Cited in

(15)

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

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)