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

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)

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)

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