Unlabeled graph

The six graphs in the upper right are connected, 19, 41 = 6, the others are disconnected. The corresponding eleven equivalence classes of labeled simple graphs are of order 1, 6,3,12, 3, 6,1,12, 4,12, 4 (from left to right, and from top to bottom). The unlabeled 

Equivalence is similar to symmetry. The number of classes of equivalent carbon atoms in a molecule is the number of carbon signals in its NMR spectrum, and two carbon 

3 Definition (Equivalence relation, equivalence class) Consider a nonempty set S. Relations and, in particular, equivalence relations on this set are defined as follows  

An equivalence relation R decomposes the set S into pairwise disjoint and nonempty subsets, the equivalence classes, as it is easy to check, using the symmetry of S. 

the equivalence classes form a set-partition of S in the following sense  

---

As can be seen in Figure 2-13, the diagonal elements of the matrix are always zero and it is symmetric around the diagonal elements (undirected, unlabeled graph). Thus, it is a redundant matrix and can be reduced to half of its entries (Figure 2-14b. For clarity, all zero entries are omitted in Figures 2-14b-d. 

Since all graphs in the same class are in this sense topologically equivalent, a representative member of each class, devoid of explicit vertex (or edge) labels, defines a unique unlabeled graph. Figure 2.3, for example, shows all of the undirected and unlabeled graphs of order 4. 

WriE72 Wright, E. M. The probability of connectedness of an unlabelled graph can be less for more edges. Proc. Am. Math. Soc. 35 (1972) 21-25. 

Interestingly enough, investigations related to counting unlabeled graphs started with the pragmatic problem of calculating the number of paraffin... 

We begin with the enumeration of labeled graphs because, as with counting, they are easier to deal with. The algorithm we outline next for enumerating labeled graphs we will use and modify to enumerate unlabeled graphs. 

To use Scheme I to enumerate unlabeled graphs, we need to remove duplicates, i.e., isomorphic graphs. Of course, this removal can be performed after generating all labeled graphs with n vertices, but this becomes lengthy (i.e., even for modest n. A better strategy is to build unlabeled... 

Figure 18 Two unlabeled graphs drawn at random and unchanged under the permutation n = (135)(246).

N. G. Wormald, SIAM J. Comput., 16, 717 (1987). Generating Random Unlabeled Graphs. 

In all three cases, the four nodes are not numbered or labeled, as we shall say. Hence the above graphs are unlabeled graphs on four nodes. However, they cannot be entered into a computer as is , but require labeling. 

We are now in a position to define unlabeled graphs in terms of group actions. For this purpose, we introduce an important action obtained from a given action gX. G. Polya introduced this approach in the seminal paper [234] ([235] contains an English translation). His aim was to count permutational isomers which means the essentially different distributions of admissible substituents over a molecular skeleton, where essentially different means with respect to the symmetry group of the skeleton. We shall describe this in all detail in Chapter 3, where we show that the same approach allows the construction of corresponding molecular graphs, but this needs further notions. 

More explicitly, a molecule graph is an unlabeled graph where the nodes are colored by an element symbol, together with an admissible atom state. For example, the molecule of cyanic acid is modeled by the following unlabeled, colored graph ... 

This method has been used in several cases, such as to construct unlabeled graphs according to successively increasing number of lines. Nowadays it is a standard method for the construction of discrete structures, for example, molecular graphs. It will be described in detail later on, at present we discuss a simple example only. 

Replacing the labels of the nodes by nodes we find the two existing unlabeled graphs on 4 nodes with 2 bonds ... 

In the next step we transfer the subgraph relations from labeled to unlabeled graphs. This is quite important since we shall speak of substructures of molecular graphs, i.e. of subgraphs of unlabeled multigraphs. 

Definition (Embeddings of unlabeled graphs) Using embeddings, sub- and partial graph relations can be defined for equivalence classes of graphs. For... 

We used such bijections to construct unlabeled graphs, and they can also be applied in a construction of transversals of the orbits on Yf, the method is the same. In this way we can put our hands on the permutational isomers . And this is what we really want, we should like to see the permutational isomers, all of them if possible Let us illustrate this with a famous exeunple that is small enough to perform by hand ... 

The next example is the orderly generation of unlabeled graphs on n nodes. Describing this merely involves replacing the group 1 with the symmetric group S . 

L. Goldberg. Efficient algorithms for listing unlabeled graphs.]. Algorithms, 13 128-143,... 

---