Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/803792
- Degree sequences and poset structure of order 9 graphs
Eggleton, Roger B.;
MacDougall, James A.
- The set G(n) of unlabelled simple graphs of order n is a poset with partial ordering G ≤ H whenever G is a spanning subgraph of H. On the website www.maths.uq.edu.au/~pa/research/poset9.html we have made available a tabulation of the Hasse diagram for G(9), a digraph of order 274668 and size 4147388, extending our recent tabulations for G(n) with 4 ≤ n ≤ 8. The present paper is a descriptive summary of features of G(9) derived from the tabulation, including: the maximum number of graphs in G(9) with the same degree sequence is 3020, corresponding to 2¹3²4³5²6¹; there are 36 self-complementary graphs in G(9), but 10794 graphs with self-complementary degree sequences; there are 49 graphs in G(9) that are edge-transitive, and 134996 that have no edge-symmetry; the maximum number of immediate successors of a graph in G(9) is 28, and 12 graphs attain this maximum; the number of immediate successors of a graph in G(9) is distributed unimodally, with peak at 16 attained by 25010 graphs. All underlying data are available on the website.
- Congressus Numerantium Vol. 166, p. 83-95
- Utilitas Mathematica Publishing Inc
- Resource Type
- journal article