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

Simple item page
dc.creatorGagarin, Andrei
dc.creatorLabelle, Gilbert
dc.creatorLeroux, Pierre
dc.date2004-11-16
dc.date.accessioned2026-07-07T09:36:45Z
dc.date.available2026-07-07T09:36:45Z
dc.descriptionWe 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)].
dc.description18 pages, 7 figures and 4 tables
dc.identifierhttps://arxiv.org/abs/math/0411356
dc.identifierhttp://arxiv.org/abs/math/0411356
dc.identifierDiscrete Math. 307 (2007), no. 23, pp. 2993-3005
dc.identifierdoi:10.1016/j.disc.2007.03.083
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/160230
dc.subjectCombinatorics
dc.subjectDiscrete Mathematics
dc.subject05C30, 05C10 (Primary); 68R10 (Secondary)
dc.titleCharacterization and enumeration of toroidal K_{3,3}-subdivision-free graphs
dc.typetext

Files

Collections

arXiv