On the Average Genus of a Graph

Gross, Jonathan L.; Klein, E. Ward; Rieper, Robert G.

Not all rational numbers are possibilities for the average genus of an individual graph. The smallest such numbers are determined, and varied examples are constructed to demonstrate that a single value of average genus can be shared by arbitrarily many different graphs. It is proved that the number one is a limit point of the set of possible values for average genus and that the complete graph K4 is the only 3-connected graph whose average genus is less than one. Several problems for future study are suggested.



More About This Work

Academic Units
Computer Science
Department of Computer Science, Columbia University
Columbia University Computer Science Technical Reports, CUCS-482-89
Published Here
January 11, 2012