Strong embeddings of minimum genus

Details Strong embeddings of minimum genus Strong embeddings of minimum genus

2009-08-13

arxiv.org/abs/0908.1933v2

Discrete Math. 310 (2010) 2595-2599

Mathematics

Combinatorics

Scientific paper

10.1016/j.disc.2010.03.019

A "folklore conjecture, probably due to Tutte" (as described in [P.D. Seymour, Sums of circuits, Graph theory and related topics (Proc. Conf., Univ. Waterloo, 1977), pp. 341-355, Academic Press, 1979]) asserts that every bridgeless cubic graph can be embedded on a surface of its own genus in such a way that the face boundaries are cycles of the graph. In this paper we consider closed 2-cell embeddings of graphs and show that certain (cubic) graphs (of any fixed genus) have closed 2-cell embedding only in surfaces whose genus is very large (proportional to the order of these graphs), thus providing plethora of strong counterexamples to the above conjecture. The main result yielding such counterexamples may be of independent interest.

Affiliated with

Also associated with

No associations

Rating

Strong embeddings of minimum genus 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 Strong embeddings of minimum genus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Strong embeddings of minimum genus will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-701755