Odd cycle transversals and independent sets in fullerene graphs

Details Odd cycle transversals and independent sets in fullerene graphs Odd cycle transversals and independent sets in fullerene graphs

2012-03-18

arxiv.org/abs/1203.3912v1

Mathematics

Combinatorics

17 pages, 4 figures

Scientific paper

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 Do\v{s}li\'c and Vuki\v{c}evi\'c, 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.

Affiliated with

Also associated with

No associations

Rating

Odd cycle transversals and independent sets in fullerene graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Odd cycle transversals and independent sets in fullerene graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Odd cycle transversals and independent sets in fullerene graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-617068