Maximum genus orientable embeddings from circuit decompositions of dense eulerian graphs and digraphs

EUROCOMB’23

M. N. Ellingham Joanna Ellis-Monaghan

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-056

PDF
Abstract
Suppose we have an eulerian (di)graph with a (directed) circuit decomposition. We show that if the (di)graph is sufficiently dense, then it has an orientable embedding in which the given circuits are facial walks and there are exactly one or two other faces. This embedding has maximum genus subject to the given circuits being facial walks. When there is only one other face, it is necessarily bounded by an euler circuit. Thus, if the numbers of vertices and edges have the same parity, a sufficiently dense (di)graph $D$ with a given (directed) euler circuit $C$ has an orientable embedding with exactly two faces, each bounded by an euler circuit, one of which is $C$. The main theorem encompasses several special cases in the literature, for example, when the digraph is a tournament.

Pages:
401–406
References

Lars Døvling Andersen, André Bouchet, and Bill Jackson. Orthogonal A-trails of 4-regular graphs embedded in surfaces of low genus. J. Combin. Theory Ser. B, 66(2):232-246, 1996.
https://doi.org/10.1006/jctb.1996.0017

Jack Edmonds. On the surface duality of linear graphs. J. Res. Nat. Bur. Standards Sect. B, 69B:121-123, 1965.
https://doi.org/10.6028/jres.069B.012

M. N. Ellingham and Joanna A. Ellis-Monaghan. Edge-outer graph embedding and the complexity of the DNA reporter strand problem. Theoret. Comput. Sci., 785:117-127, 2019.
https://doi.org/10.1016/j.tcs.2019.03.019

Grahame Erskine, Terry Griggs, and Jozef Širáň. On the upper embedding of symmetric configurations with block size 3. Discrete Math., 343(4):111774, 6, 2020.
https://doi.org/10.1016/j.disc.2019.111774

Mike J. Grannell, Terry S. Griggs, and Jozef Širáň. Maximum genus embeddings of Steiner triple systems. European J. Combin., 26(3-4):401-416, 2005.
https://doi.org/10.1016/j.ejc.2004.01.014

Terry S. Griggs, Thomas A. McCourt, and Jozef Širáň. On the upper embedding of Steiner triple systems and Latin squares. Ars Math. Contemp., 18(1):127-135, 2020.
https://doi.org/10.26493/1855-3974.1959.9c7

Terry S. Griggs, Constantinos Psomas, and Jozef Širáň. Maximum genus embeddings of Latin squares. Glasg. Math. J., 60(2):495-504, 2018.
https://doi.org/10.1017/S0017089517000234

Nataša Jonoska, Nadrian C. Seeman, and Gang Wu. On existence of reporter strands in DNA-based graph structures. Theoret. Comput. Sci., 410(15):1448-1460, 2009.
https://doi.org/10.1016/j.tcs.2008.12.004

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 M. N. Ellingham, Joanna Ellis-Monaghan

PDF