On the average genus of a graph (Q2366954): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q591987 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: Arthur T. White / rank | |||
Normal rank |
Revision as of 23:09, 19 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the average genus of a graph |
scientific article |
Statements
On the average genus of a graph (English)
0 references
11 August 1993
0 references
The average genus of a fixed connected graph \(G\) is the average value of the genus of the imbedding surface, taken over all labelled orientable 2- cell imbeddings of \(G\). Thus if \(G\) has degree sequence \(\{d_ 1,d_ 2,\dots,d_ p\}\), the average genus of \(G\) is the expected value of the genus random variable on the sample space of all \(\prod^ p_{i=1}(d_ i-1)!\) labelled orientable 2-cell imbeddings of \(G\), with the uniform distribution. Not all nonnegative rational numbers occur as values for this random variable, as \(G\) varies; it is shown that the six smallest positive values are 1/3, 1/2, 5/9, 2/3, 19/27, and 3/4. A ``necklace of type \((r,s)\)'' is shown to have average genus \(1-(1/2)^ r(2/3)^ s\), from which three corollaries follow: (1) Arbitrarily many mutually nonhomeomorphic 2-connected graphs can have the same average genus. (2) The average genus of a graph with nontrivial genus range can lie arbitrarily close to the maximum genus (which is 1, for these necklaces). (3) The number 1 is an upper limit point of the set of possible values of average genus. It is also shown that the only 3-connected graph whose average genus is less than 1 is \(K_ 4\) (which has average genus 7/8).
0 references
necklace
0 references
average genus
0 references
imbeddings
0 references
random variable
0 references