Degree Sequences and Poset Structure of Order 9 Graphs |
Structural relationships between the unlabelled simple graphs of small order are often important. However, the rapid proliferation of these graphs makes direct study ever more challenging as order increases. Specifically, there are just 1252 unlabelled simple graphs of order 7 or less, but there are 12346 graphs of order n = 8 and 274668 graphs of order n = 9. Thus, the number of graphs of order n = 9 is more than twenty times the total number of graphs of all smaller orders. Our objective here is to provide easily accessible descriptive information specifying all graphs of order n = 9, together with basic structural relationships among them.
A natural view of the structural relationships between graphs is provided by the subgraph relation, regarded as a partial ordering. Specifically, if G and H are two graphs of order n, we say that G precedes H whenever G is a proper spanning subgraph of H. With this natural partial ordering the set of all graphs of order n becomes a poset (partially ordered set), and its structure provides a framework for systematic studies of properties of graphs of order n.
In an earlier paper Structure of graph posets for orders 4 to 8 we explicitly determined the structure of the poset of graphs of order n for each n up to and including 8. To do this we assigned an identifying number to each graph of order n, using SEAM numbering, a slightly modified version of the numbering scheme introduced by Peter Steinbach in his Field Guide to Simple Graphs. This numbering is based on structural properties of the graphs, and consequently is highly compatible with the position of each graph in the poset of graphs of order n. Here we provide links to our paper Degree sequences and poset structure of order 9 graphs, in which we present corresponding information for the graphs of order n = 9, together with various explicit tabulations of data from which the summaries in that paper were produced.
This is joint work by Peter Adams (The University of Queensland), Roger Eggleton (Illinois State University) and James MacDougall (The University of Newcastle).
This is the paper summarizing results of our computations for graphs of order n = 9. The reference for the published paper is: Peter Adams, Roger Eggleton and James MacDougall, Degree sequences and poset structure of graphs of order 9, Congressus Numerantium, 166 (2004), 83-95.
Links to the full data on which the paper is based are provided below.
Here is the text file listing the SEAM number N* and the full signature of each simple graph of order n = 9. SEAM numbering begins anew for each order; when the order is not clear from the context, it can be added as a prefix, with a colon as separator. For example, the four graphs with degree sequence 222222222 have SEAM numbers 9:1369 (three 3-cycles), 9:1370 (a 3-cycle and a 6-cycle), 9:1371 (a 4-cycle and a 5-cycle) and 9:1372 (a 9-cycle). The following large file may be best viewed in landscape format.
Here is a tabulation of the distinct degree sequences of graphs of order 9, and their frequencies.
Here is the file specifying the structure of the poset of all simple unlabelled graphs of order n = 9. Effectively we specify the Hasse diagram of the poset, by listing for each graph every graph resulting from deleting or adding a single edge. Each graph is represented by its SEAM number (see above). For each graph G of order n = 9, the SEAM number N*(G) is listed twice in the left column of the table: the first listing is followed by the SEAM numbers of all immediate predecessors of G in the poset (that is, all graphs resulting from deletion of a single edge from G), and the second listing is followed by the SEAM numbers of all immediate successors of G in the poset (that is, all graphs resulting from addition of a single edge to G).
The above file specifies the local structure (immediate predecessors and immediate successors) of the Hasse diagram of the poset of order 9 graphs. Here is the summary file specifying the global structure of this diagram. It contains considerably more information than that which could be included in the paper.