Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-05T15:52:27.816Z Has data issue: false hasContentIssue false
  • English
  • Français

An Introduction to Random Topological Graph Theory

Published online by Cambridge University Press:  12 September 2008

Arthur T. White
Arthur T. White
Affiliation:
Department of Mathematics and Statistics, Western Michigan University, Kalamazoo, MI 49008, USA
Get access Rights & Permissions [Opens in a new window]

Abstract

We introduce five probability models for random topological graph theory. For two of these models (I and II), the sample space consists of all labeled orientable 2-cell imbeddings of a fixed connected graph, and the interest centers upon the genus random variable. Exact results are presented for the expected value of this random variable for small-order complete graphs, for closed-end ladders, and for cobblestone paths. The expected genus of the complete graph is asymptotic to the maximum genus. For Model III, the sample space consists of all labeled 2-cell imbeddings (possibly nonorientable) of a fixed connected graph, and for Model IV the sample space consists of all such imbeddings with a rotation scheme also fixed. The event of interest is that the ambient surface is orientable. In both these models the complete graph is almost never orientably imbedded. The probability distribution in Models I and III is uniform; in Models II and IV it depends on a parameter p and is uniform precisely when p = 1/2. Model V combines the features of Models II and IV.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 3 , Issue 4 , December 1994 , pp. 545 - 555
Copyright
Copyright © Cambridge University Press 1994

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Archdeacon, D. (1988) Calculations on the average genus and genus distribution of graphs. Congressus Numerantium 67 114–124.Google Scholar
[2]Biggs, N. L. and White, A. T. (1979) Permutation Groups and Combinatorial Structures, Cambridge University Press.CrossRefGoogle Scholar
[3]Furst, M. L., Gross, J. L. and Statman, R. (1989) Genus distributions for two classes of graphs. J. Combinatorial Theory B 46 22–36.CrossRefGoogle Scholar
[4]Goodwin, W. (1972) Imbedding problems in graph theory, Senior Paper, Western Michigan University.Google Scholar
[5]Gross, J. L. and Furst, M. (1987) Hierarchy for imbedding-distribution invariants of a graph. J. Graph Theory 11 205–220.Google Scholar
[6]Gross, J. L., Robbins, D. P. and Tucker, T. W. (1989) Genus distributions for bouquets of circles. J. Combinatorial Theory B 47 292–306.Google Scholar
[7]Gross, J. L. and Tucker, T. W. (1987) Topological Graph Theory, Wiley-Interscience.Google Scholar
[8]Jackson, D. M. (1987) Counting cycles in permutations by group characters, with an application to a topological problem. Trans. Amer. Math. Soc. 299 785–801.CrossRefGoogle Scholar
[9]Jungerman, M. and White, A. T. (1980) On the genus of finite abelian groups. Europ. J. Combinatorics 1 243–251.Google Scholar
[10]Lee, S. H. (1989) An asymptotic result for the average genus of a graph. Graph Theory Newsletter 18.Google Scholar
[11]Lee, S. H. and White, A. T. (1991) Random topological graph theory. In: Alavi, Y., Chung, F. R. K., Graham, R. L. and F-Hsu, D. (eds.) Proceedings of the Second International Conference in Graph Theory, Combinatorics, Algorithms and Applications SIAM 599–613.Google Scholar
[12]Mull, B. (1989) Expected number of symmetries in 2-cell imbeddings of connected graphs. Graph Theory Newsletter 18.Google Scholar
[13]Mull, B., Rieper, R. and White, A. T. (1988) Enumerating 2-cell imbeddings of connected graphs. Proc. Amer. Math. Soc. 103 321–330.Google Scholar
[14]Rieper, R. (1987) The Enumeration of Graph Embeddings, Ph.D. Dissertation, Western Michigan University.Google Scholar
[15]Ringel, G. (1974) Map Color Theorem, Springer-Verlag.Google Scholar
[16]Riordan, J. (1968) Combinatorial Identities, Wiley.Google Scholar
[17]Stahl, S. (1983) The average genus of classes of graph embeddings. Congressus Numerantium 40 375–388.Google Scholar
[18]Stahl, S. (1990) Region distributions of graph embeddings and Stirling numbers. Discrete Math. 82 57–78.CrossRefGoogle Scholar
[19]Stahl, S. (1991) Region distributions of some small diameter graphs. Discrete Math. 89 281–299.CrossRefGoogle Scholar
[20]Stahl, S. (1991) Permutation-partition pairs III: Embedding distributions of linear families of graphs. J. Combinatorial Theory B 52 191–218.CrossRefGoogle Scholar
[21]Stahl, S. (1991) An upper bound for the average number of regions. J. Combinatorial Theory B 52 219–221.Google Scholar
[22]White, A. T. (1984) Graphs, Groups and Surfaces, Revised Edition, North-Holland.Google Scholar