Taxonomy of graphs of Order 10 |
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, 274668 graphs of order n = 9, and 12005168 of order n=10. Thus, the number of graphs of order n = 10 is around forty 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 = 10, 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 earlier papers Structure of graph posets for orders 4 to 8 and Degree Sequences and Poset Structure of Order 9 Graphs we explicitly determined the structure of the poset of graphs of order n for each n up to and including 9. 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 Taxonomy of graphs of Order 10, in which we present corresponding information for the graphs of order n = 10, 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 = 10. The reference for the paper is: Peter Adams, Roger Eggleton and James MacDougall, Taxonomy of graphs of Order 10, Congressus Numerantium 180 (2006), 65-80.
Links to the full data on which the paper is based are provided below.
There are too many graphs of order n = 10 to include the full SEAM signature. Instead, we simply give the canonical edge sequence of each of the first 6002584 graphs, in SEAM order. (The remaining graphs are readily deduced by centrally-symmetric complementation.)
We call a graph G a SEAM sentinel if it comes first in the SEAM ordering of all graphs with the same degree sequence as G. In the following files we give the full signatures of all SEAM sentinels of each order up to and including 10.
Here is a tabulation of the distinct degree sequences of graphs of order 10, and their frequencies.
In the following files we present information regarding the components of graphs of orders 4 to 10 inclusive. For more information, please refer to our paper.
The girth of a graph G is the order of the smallest cycle in G, or 0 if G is acyclic. The following file presents information regarding the girths of graphs of orders 4 to 10 inclusive. For more information, please refer to our paper.
Due to the very large size, it is not feasible to present complete data on the poset of all simple unlabelled graphs of order n = 10. However, in the following file we list the outdegree sequence, indegree sequence and full degree sequence of the Hasse diagram of the poset.