Characterization and enumeration of toroidal K_{3,3}-subdivision-free graphs

Details Characterization and enumeration of toroidal K_{3,3}-subdivision-free graphs Characterization and enumeration of toroidal K_{3,3}-subdivision-free graphs

2004-11-16

arxiv.org/abs/math/0411356v1

Discrete Math. 307 (2007), no. 23, pp. 2993-3005

Mathematics

Combinatorics

18 pages, 7 figures and 4 tables

Scientific paper

10.1016/j.disc.2007.03.083

We describe the structure of 2-connected non-planar toroidal graphs with no K_{3,3}-subdivisions, using an appropriate substitution of planar networks into the edges of certain graphs called toroidal cores. The structural result is based on a refinement of the algorithmic results for graphs containing a fixed K_5-subdivision in [A. Gagarin and W. Kocay, "Embedding graphs containing K_5-subdivisions'', Ars Combin. 64 (2002), 33-49]. It allows to recognize these graphs in linear-time and makes possible to enumerate labelled 2-connected toroidal graphs containing no K_{3,3}-subdivisions and having minimum vertex degree two or three by using an approach similar to [A. Gagarin, G. Labelle, and P. Leroux, "Counting labelled projective-planar graphs without a K_{3,3}-subdivision", submitted, arXiv:math.CO/0406140, (2004)].

Affiliated with

Also associated with

No associations

Rating

Characterization and enumeration of toroidal K_{3,3}-subdivision-free 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 Characterization and enumeration of toroidal K_{3,3}-subdivision-free graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Characterization and enumeration of toroidal K_{3,3}-subdivision-free graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-655222