research-article

Exponential Families of Non-Isomorphic Triangulations of Complete Graphs

Authors:

C.Paul Bonnington,

M.J. Grannell,

T.S. Griggs,

J. ŠiráňAuthors Info & Claims

Journal of Combinatorial Theory Series B, Volume 78, Issue 2

Pages 169 - 184

https://doi.org/10.1006/jctb.1999.1939

Published: 01 March 2000 Publication History

Abstract

We prove that the number of non-isomorphic face 2-colourable triangulations of the complete graph Kn in an orientable surface is at least 2n2/54 O(n) for n congruent to 7 or 19 modulo 36, and is at least 22n2/81 O(n) for n congruent to 19 or 55 modulo 108.

References

[1]

M.J. Grannell, T.S. Griggs, J. ¿irá¿, Face 2-colourable triangular embeddings of complete graphs, J. Combin. Theory Ser. B, 74 (1998) 8-19.

Digital Library

Google Scholar

[2]

M.J. Grannell, T.S. Griggs, J. ¿irá¿, Surface embeddings of Steiner triple systems, J. Combin. Des., 6 (1998) 325-336.

Crossref

Google Scholar

[3]

V. P. Korzhik, and, H. J. Voss, On the number of non-isomorphic orientable regular embeddings of complete graphs, submitted for publication.

Google Scholar

[4]

S. Lawrencenko, S. Negami, A.T. White, Three nonisomorphic triangulations of an orientable surface with the same complete graph, Discrete Math., 135 (1994) 367-369.

Digital Library

Google Scholar

[5]

G. Ringel, Springer, 1974.

Google Scholar

[6]

A.T. White, Block designs and graph imbeddings, J. Combin. Theory Ser. B, 25 (1978) 166-183.

Crossref

Google Scholar

[7]

R.M. Wilson, Nonisomorphic Steiner triple systems, Math. Z., 135 (1974) 303-313.

Crossref

Google Scholar

[8]

J.W.T. Youngs, The mystery of the Heawood conjecture, in: Graph Theory and its Applications, Academic Press, 1970, pp. 17-50.

Google Scholar

Cited By

View all

Kawarabayashi KMohar BNedela RZeman P(2024)Automorphisms and Isomorphisms of Maps in Linear TimeACM Transactions on Algorithms10.1145/368679821:1(1-32)Online publication date: 22-Nov-2024
https://dl.acm.org/doi/10.1145/3686798
Korzhik V(2015)Recursive constructions and nonisomorphic minimal nonorientable embeddings of complete graphsDiscrete Mathematics10.1016/j.disc.2015.05.024338:12(2186-2196)Online publication date: 6-Dec-2015
https://dl.acm.org/doi/10.1016/j.disc.2015.05.024
Korzhik V(2015)Nonorientable biembeddings of cyclic Steiner triple systems generated by Skolem sequencesDiscrete Mathematics10.1016/j.disc.2015.02.017338:8(1345-1361)Online publication date: 6-Aug-2015
https://dl.acm.org/doi/10.1016/j.disc.2015.02.017
Show More Cited By

Index Terms

Exponential Families of Non-Isomorphic Triangulations of Complete Graphs
1. Mathematics of computing
  1. Discrete mathematics
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Quotient-complete arc-transitive graphs

We examine the class of G-arc-transitive graphs with at least one nontrivial complete normal quotient, such that all other normal quotients are either complete or empty graphs. Such graphs arise naturally as basic graphs under normal quotient analysis ...
Triangulations of orientable surfaces by complete tripartite graphs

Orientable triangular embeddings of the complete tripartite graph K"n","n","n correspond to biembeddings of Latin squares. We show that if n is prime there are at least e^n^l^n^n^-^n^(^1^+^o^(^1^)^) nonisomorphic biembeddings of cyclic Latin squares of ...
Decompositions of complete graphs and complete bipartite graphs into isomorphic supersubdivision graphs

A graph H is called a supersubdivison of a graph G if H is obtained from G by replacing every edge uv of G by a complete bipartite graph K_2,m (m may vary for each edge) by identifying u and v with the two vertices in K_2,m that form one of the two ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Combinatorial Theory Series B

Journal of Combinatorial Theory Series B Volume 78, Issue 2

March 2000

113 pages

ISSN:0095-8956

Editors:
Adrian Bondy
Univ. Claude Bernard Lyon 1, Villeurbanne,, France
,
U. S. R. Murty
Univ. of Waterloo, Waterloo, Ont., Canada

Issue’s Table of Contents

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 March 2000

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kawarabayashi KMohar BNedela RZeman P(2024)Automorphisms and Isomorphisms of Maps in Linear TimeACM Transactions on Algorithms10.1145/368679821:1(1-32)Online publication date: 22-Nov-2024
https://dl.acm.org/doi/10.1145/3686798
Korzhik V(2015)Recursive constructions and nonisomorphic minimal nonorientable embeddings of complete graphsDiscrete Mathematics10.1016/j.disc.2015.05.024338:12(2186-2196)Online publication date: 6-Dec-2015
https://dl.acm.org/doi/10.1016/j.disc.2015.05.024
Korzhik V(2015)Nonorientable biembeddings of cyclic Steiner triple systems generated by Skolem sequencesDiscrete Mathematics10.1016/j.disc.2015.02.017338:8(1345-1361)Online publication date: 6-Aug-2015
https://dl.acm.org/doi/10.1016/j.disc.2015.02.017
Grannell MKnor M(2013)Dihedral Biembeddings and Triangulations by Complete and Complete Tripartite GraphsGraphs and Combinatorics10.1007/s00373-012-1163-129:4(921-932)Online publication date: 1-Jul-2013
https://dl.acm.org/doi/10.1007/s00373-012-1163-1
Grannell MKnor M(2012)Triangular EmbeddingsJournal of Graph Theory10.1002/jgt.2059069:4(370-382)Online publication date: 1-Apr-2012
https://dl.acm.org/doi/10.1002/jgt.20590
Korzhik V(2010)Exponentially many nonisomorphic genus embeddings of Kn, mDiscrete Mathematics10.1016/j.disc.2010.06.038310:21(2919-2924)Online publication date: 1-Nov-2010
https://dl.acm.org/doi/10.1016/j.disc.2010.06.038
Korzhik V(2009)Exponentially many nonisomorphic orientable triangular embeddings of K12s+3Discrete Mathematics10.1016/j.disc.2008.01.027309:4(852-866)Online publication date: 1-Mar-2009
https://dl.acm.org/doi/10.1016/j.disc.2008.01.027
Kawarabayashi KMohar BLadner RDwork C(2008)Graph and map isomorphism and all polyhedral embeddings in linear timeProceedings of the fortieth annual ACM symposium on Theory of computing10.1145/1374376.1374443(471-480)Online publication date: 17-May-2008
https://dl.acm.org/doi/10.1145/1374376.1374443
Solov'Eva F(2007)Tilings of nonorientable surfaces by Steiner triple systemsProblems of Information Transmission10.1134/S003294600703004043:3(213-224)Online publication date: 1-Sep-2007
https://dl.acm.org/doi/10.1134/S0032946007030040
Korzhik V(2006)On the maximal distance between triangular embeddings of a complete graphJournal of Combinatorial Theory Series B10.1016/j.jctb.2005.09.00696:3(426-435)Online publication date: 1-May-2006
https://dl.acm.org/doi/10.1016/j.jctb.2005.09.006
Show More Cited By

Abstract

References

Cited By

Index Terms

Recommendations

Quotient-complete arc-transitive graphs

Triangulations of orientable surfaces by complete tripartite graphs

Decompositions of complete graphs and complete bipartite graphs into isomorphic supersubdivision graphs

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations