Structure of Graph Posets for Orders 4 to 8 |
The unlabelled simple graphs of small order are the fundamental objects of graph theory. The structural relationships between these graphs are often important, but their rapid proliferation with increasing order makes direct study of their structural relationships ever more challenging as order increases. Specifically, there are just 52 unlabelled simple graphs of order 5 or less, but there are 156 graphs of order n = 6, a further 1044 graphs of order n = 7, and 12346 graphs of order n = 8. Thus, the number of graphs of order n = 8 is almost ten times the total number of graphs (1252) of all smaller orders. Our objective here is to provide easily accessible descriptive information specifying basic structural relationships among all graphs of order 8 or less.
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.
We have explicitly determined the structure of the poset of graphs of order n for each n up to and including 8. To do this we have 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. Links to tables of this information, and to a paper summarizing some of its principal features, are provided below.
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. It includes a full specification of SEAM numbering. The reference for the published paper is: Peter Adams, Roger Eggleton and James MacDougall, Posets of graphs of orders 4 to 8, Congressus Numerantium, 166 (2004), 63-81.
Links to the full data on which the paper is based are provided below.
Here are the text files in which we have listed the SEAM number N* and the full signature of each simple graph of order up to and including 8. We also include the Steinbach number N for each graph of order 7 or less (this being as far as that numbering has appeared in publication). SEAM numbering begins anew for each order; when the order is not clear from context it can be added as a prefix, with a colon as separator. For example, the graph with SEAM number 7:146 is the cycle of order 7; with the same prefix convention, its Steinbach number also happens to be 7:146.
Here are files for each order n (with n between 4 and 8 inclusive), specifying the structure of the poset of all simple unlabelled graphs of order n. Effectively we specify the Hasse diagram of each 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, the SEAM number N*(G) is listed twice in the left column of the table for order n: 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 files above specify the local structure (immediate predecessors and immediate successors) of the Hasse diagram of the poset comprising the order n graphs. Here are summary files specifying the global structure of these diagrams. For orders up to 6 they are only slightly more detailed than tabular information given in the paper (see above). However, for orders n = 7 and 8 they contain considerably more information than that which could be included in the paper.
The independence graph of the poset of order n graphs is the directed graph having the unlabelled simple graphs of order n as its vertices, and having a directed edge from G to H precisely when N*(G) < N*(H) and G is not a subgraph of H. The following files are the basis for summary information about these independence graphs in the paper.