Academic Commons

Reports

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.

Subjects

Files

More About This Work

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