# Degree Sequences and Poset Structure of Order 9 Graphs

MacDougall, James A. and Eggleton, Roger B. and Adams, Peter D. (2004) Degree Sequences and Poset Structure of Order 9 Graphs. Congressus Numerantium, 166 . pp. 63-95.

 Preview
PDF - Accepted Version
The set $G(n)$ of unlabelled simple graphs of order $n$ is a poset with partial ordering $G \leq 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 \leq n \leq 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^1 3^2 4^3 5^2 6^1$; 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.