Generation of various classes of trivalent graphs. (English) Zbl 1301.05277
Summary: It turns out that there exist numerous useful classes of cubic graphs. Some are needed in connection with maps, hypermaps, configurations, polytopes, or covering graphs. In this paper, we briefly explore these connections and give motivation why some classes of cubic graphs should be generated. Then we describe the algorithms we used to generate these classes. The results are presented in various tables.
MSC:
| 05C75 | Structural characterization of families of graphs |
| 05C15 | Coloring of graphs and hypergraphs |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
Online Encyclopedia of Integer Sequences:
Number of isomorphism classes of connected 3-regular multigraphs of order 2n, loops allowed.References:
| [1] | Petkovšek, M.; Pisanski, T., Counting disconnected structures: chemical trees, fullerenes, I-graphs, and others, Croat. Chem. Acta, 78, 563-567 (2005) |
| [2] | Betten, A.; Brinkmann, G.; Pisanski, T., Counting symmetric configurations \(v_3\), Discrete Appl. Math., 99, 331-338 (2000) · Zbl 0940.05020 |
| [3] | Pisanski, T., A classification of cubic bicirculants, Discrete Math., 307, 567-578 (2007) · Zbl 1109.05055 |
| [4] | Dress, A. W.M.; Huson, D. H., On tilings of the plane, Geom. Dedicata, 24, 295-310 (1987) · Zbl 0634.52011 |
| [5] | Malnič, A., Group actions, coverings and lifts of automorphisms, Discrete Math., 182, 1-3, 203-218 (1998) · Zbl 0893.57001 |
| [6] | Malnič, A., Action graphs and coverings, Discrete Math., 244, 1-3, 299-322 (2002) · Zbl 0996.05067 |
| [7] | Gross, J.; Tucker, T. W., Topological Graph Theory (1987), Wiley: Wiley New York · Zbl 0621.05013 |
| [8] | de Vries, J., Over vlakke configuraties waarin elk punt met twee lijnen incident is, Verslagen en Mededeelingen der Koninklijke Akademie voor Wetenschappen, Afdeeling Natuurkunde, 6, 3, 382-407 (1889) · JFM 21.0538.07 |
| [9] | Brinkmann, G., Fast Generation of Cubic Graphs, J. Graph Theory, 23, 139-149 (1996) · Zbl 0858.05093 |
| [10] | Brinkmann, G.; Goedgebeur, J.; McKay, B., Generation of cubic graphs, Discrete Math. Theor. Comput. Sci., 13, 2 (2011) · Zbl 1283.05256 |
| [11] | Godsil, C.; Royle, G., Algebraic graph theory, (Graduate Texts in Mathematics, vol. 207 (2001), Springer-Verlag: Springer-Verlag New York) · Zbl 0968.05002 |
| [12] | Orbanić, A.; Pellicer, D.; Pisanski, T.; Tucker, T. W., Edge-transitive maps of low genus, Ars Math. Contemp., 4, 385-402 (2011) · Zbl 1254.05049 |
| [14] | Izquierdo, M.; Singerman, D., Hypermaps on surfaces with boundary, European J. Combin., 15, 159-172 (1994) · Zbl 0814.57001 |
| [15] | Jones, G. A., Exotic behaviour of infinite hypermaps, Ars Math. Contemp., 1, 51-65 (2008) · Zbl 1167.05001 |
| [16] | McKay, B. D., Isomorph-free exhaustive generation, J. Algorithms, 26, 306-324 (1998) · Zbl 0894.68107 |
| [18] | Grund, R.; Kerber, A.; Laue, R., MOLGEN — ein Computeralgebrasystem für die Konstruktion molekularer Graphen, MATCH Commun. Math. Comput. Chem., 27, 87-131 (1992) · Zbl 0770.92025 |
| [19] | Brinkmann, G., Isomorphism Rejection in Structure Generation Programs, (Discrete Mathematical Chemistry. Discrete Mathematical Chemistry, DIMACS Series on Discrete Mathematics and Theoretical Computer Science, vol. 51 (2000), American Mathematical Society), 25-38 · Zbl 0963.05126 |
| [20] | Brinkmann, G.; Steffen, E., Chromatic index critical graphs of orders 11 and 12, European J. Combin., 19, 889-900 (1998) · Zbl 0918.05050 |
| [21] | Kempe, A. B., On the geographical problem of the four colours, Amer. J. Math., 2, 193-200 (1879) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
