Article ID Journal Published Year Pages File Type
4647949 Discrete Mathematics 2013 6 Pages PDF
Abstract

We consider upper and lower bounds for γ(G)+γ(G¯), the sum of the genus of a graph and its complement. For the lower bound, we show γ(G)+γ(G¯)≥⌈112(n2−13n+24)⌉. Furthermore, we construct an infinite family of graphs attaining this bound along with several other isolated examples. We provide a construction to show that γ(G)+γ(G¯) can be at least as large as 148(5n2−52n+144), and determine sharp upper bounds for a few small orders. Some asymptotic results are considered.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,