Join and Meet Digraphs of the Poset of Graphs of Order 5 |
The poset of 34 unlabelled simple graphs of order 5 has the partial ordering in which G precedes H whenever G is a proper spanning subgraph of H. For every independent subset we determine the join, an independent subset comprising the relevant spanning-universal graphs, and the meet, an independent set comprising the relevant greatest common subgraphs. The results are presented as digraphs of order 862. We establish various structural properties of these digraphs and their interaction. This is joint work by Peter Adams (The University of Queensland) and Roger Eggleton (Illinois State University).
This paper has now appeared in Congressus Numerantium 154 (2002), 165-182. Note that reference [1] in this paper has also appeared, in Bull. Inst. Combin. Appl. 37 (2003), 29-34.
Here is the paper, in two formats. For a description and summary of the results, and a short list of references, please read it via one of these links.
The paper includes four tables detailing the poset structure of the set of order 5 graphs, a listing of the 862 independent subsets of this poset, a listing of the joins and meets of these subsets, and a listing of the directed 2-cycles in the superposed join and meet digraphs. The paper also has a figure showing the order 5 graphs and their Steinbach numbers. For completeness, we here provide all this data, and more, in an expanded format convenient for computational work. We use the same numbers as those employed by Peter Steinbach in his useful Field Guide to Simple Graphs.
Here is a table specifying the poset structure on the 34 order 5 graphs.
For readers who do not have on hand a copy of Steinbach's Field Guide to Simple Graphs, this text file gives the Steinbach reference number, degree sequence and edge set of each graph of order 5.
Here is a table giving the join and meet of each of the 862 independent subsets of the order 5 graphs. The subsets are specified by explicit listing of their members, and by their rank number in the lexicographic ordering. Freed from the space limitations of hardcopy publishing, this table has a more convenient format than the corresponding Tables 2 and 3 in our paper. The text version is useful for computational work.
Here are two tables listing the directed paths in the join digraph by their initial independent subset. The maximal paths are labelled with an asterisk; those which are not maximal are labelled with a dash. The first table lists the paths in right-to-left lexicographic order, and assigns to these paths a rank order in square brackets to the right of each path. The second table lists the paths in lexicographic order by their initial subset, and on the left specifies the rank order of these initial subsets.
Here is a table listing the directed paths in the meet digraph by their terminal independent subset. The maximal paths are labelled with an asterisk; those which are not maximal are labelled with a dash. The table lists the paths in left-to-right lexicographic order, and assigns to these paths a rank order in square brackets to the right of each path.
The join and meet digraph, formed by superposition of the join digraph and the meet digraph, has 20 directed 2-cycles. This table lists them in a less compact but more convenient form than the corresponding Table 4 in our paper.
Here we present the corresponding information for the poset of 11 order 4 graphs. This information can easily be calculated by hand, but we include it here for completeness.
Here is a table specifying the poset structure on the 11 order 4 graphs.
For readers who do not have on hand a copy of Steinbach's Field Guide to Simple Graphs, this text file gives the Steinbach reference number, degree sequence and edge set of each graph of order 4.
Here is a table giving the join and meet of each of the 24 independent subsets of the order 4 graphs.
We do not specify here the superposed join and meet digraph, since it contains no directed cycles (other than loops).