##plugins.themes.bootstrap3.article.main##
Abstract
We study two measures of nonplanarity of cubic graphs G, the genus γ (G), and the edge deletion number ed(G). For cubic graphs of small orders these parameters are compared with another measure of nonplanarity, the rectilinear crossing number (G). We introduce operations of connected sum, specified for cubic graphs G, and show that under certain conditions the parameters γ(G) and ed(G) are additive (subadditive) with respect to them.
The minimal genus graphs (i.e. the cubic graphs of minimum order with given value of genus γ) and the minimal edge deletion graphs (i.e. cubic graphs of minimum order with given value of edge deletion number ed) are introduced and studied. We provide upper bounds for the order of minimal genus and minimal edge deletion graphs.
##plugins.themes.bootstrap3.article.details##
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution (CC-BY) 4.0 License that allows others to share the work with an acknowledgment of the work’s authorship and initial publication in this journal.
Provided they are the owners of the copyright to their work, authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal’s published version of the work (e.g., post it to an institutional repository, in a journal or publish it in a book), with an acknowledgment of its initial publication in this journal.
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories, disciplinary repositories, or on their website) prior to and during the submission process.
References
2. Daniel Bienstock, Nathaniel Dean. Bounds for rectilinear crossing numbers. J. Graph Theory, 17(3):333–348, 1993.
3. Gruia Călinescu, Cristina G Fernandes, Ulrich Finkler, Howard Karloff. A better approximation algorithm for finding planar subgraphs. J. Algorithms, 27(2):269–302, May 1998.
4. Luerbio Faria, Celina M. Herrera de Figueiredo, Sylvain Gravier, Candido F. X. de Mendonça, Jorge Stolfi. On maximum planar induced subgraphs. Discrete Appl.Math., 154(13):1774–1782, 2006.
5. Luerbio Faria, Celina M. Herrera de Figueiredo, Candido F. X. Mendonça. On the complexity of the approximation of nonplanarity parameters for cubic graphs. Discrete Appl. Math., 141(1-3):119–134, 2004.
6. Jean-Luc Fouquet, Henri Thuillier. On some conjectures on cubic 3-connected graphs. Discrete Math., 80(1):41–57, 1990.
7. M. R. Garey, D. S. Johnson. Crossing number is NP-complete. SIAM J. Algebraic Discrete Methods, 4(3):312–316, 1983.
8. Jonathan L. Gross. Embeddings of cubic Halin graphs: genus distributions. Ars Math. Contemp., 6(1):37–56, 2013.
9. Jonathan L. Gross, Thomas W. Tucker. Topological graph theory. Dover Publications, Inc., Mineola, NY, 2012.
10. R. K. Guy. A combinatorial problem. Nabla (Bulletin of the Malayan Mathematical Society), 7:68–72, 1960.
11. J. F. P. Hudson. Piecewise linear topology. University of Chicago Lecture Notes prepared with the assistance of J. L. Shaneson and J. Lees. W. A. Benjamin, Inc., New York-Amsterdam, 1969.
12. Ed Pegg Jr, G. Exoo. Crossing number graphs. The Mathematica Journal, 11(2):161–170, 2009.
13. Gary L. Miller. An additivity theorem for the genus of a graph. J. Combin. Theory Ser. B, 43(1):25–47, 1987.
14. Bojan Mohar, Carsten Thomassen. Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, 2001.
15. Bojan Mohar, Andrej Vodopivec. The genus of Petersen powers. J. Graph Theory, 67(1):1–8, 2011.
16. Roman Nedela, Martin Škoviera. Atoms of cyclic connectivity in cubic graphs. Math. Slovaca, 45(5):481–499, 1995.
17. Shengjun Pan, R. Bruce Richter. The crossing number of 11 is 100. J. Graph Theory, 56(2):128–134, 2007.
18. L. Plachta. On minimal genus cubic graphs. in preparation.
19. Gerhard Ringel. Map color theorem. Springer-Verlag, New York-Heidelberg, 1974. Die Grundlehren der mathematischen Wissenschaften, Band 209.32 L. Plachta
20. László A. Székely. A successful concept for measuring non-planarity of graphs: the crossing number. Discrete Math., 276(1-3):331–352, 2004. 6th International Conference on Graph Theory.
21. Carsten Thomassen. The graph genus problem is NP-complete. J. Algorithms, 10(4):568–576, 1989.
22. Nicholas C. Wormald. Classifying -connected cubic graphs. In Combinatorial mathematics, VI (Proc. Sixth Austral. Conf., Univ. New England, Armidale, 1978), volume 748 of Lecture Notes in Math., 199–206. Springer, Berlin, 1979.