Multigraph labeled

In order to describe the graphs on the level of a computer s capabilities we have to label (or number) the nodes. Using the labels 0,1, 2 and 3, we obtain a labeled multigraph from (1.2) which may look like the following, depending on the labeUng ... 

In mathematical terms, we describe the labeled multigraph by a mapping y that assigns the bond multiplicity to each pair of nodes ... 

Definition (Occurrence of bond multiplicities, hybridization) Consider a labeled multigraph y e 9m,nandanodeiofy.assumingthat it is notan isolated node, i.e. (y)j > 0, or, equivalently, b(y), > 0. We denote the number of nodes connected to i by a jt-fold bond by... 

For example, 0,1 < 0,2 < 1,2. This total order on (") gives a unique list notation for the labeled multigraphs y e 9m,n on n nodes containing the values of y on the ordered sequence of pairs of nodes ... 

A major problem is that a computer can handle only labeled structures, whereas we are dealing with unlabeled structures in chemistry, such as the molecule graph (1.1), the multigraph (1.2) and the simple graph (1.3) shown above. We note the following facts and introduce a few terms for the constituents of the graph ... 

Definition (Labeled m-multigraphs on n nodes) For natural numbers m > 0, the set of mappings... 

Example (The multigraph (1.2)) The matrix of the labeled 4-multigraph y and the matrix of the labeled bond graph y corresponding to... 

An important particular case of a symmetry class of mappings is an unlabeled m-multigraph on n nodes. It can be identified with a symmetry class of mappings in the following way Letn = 0,..., n-l denote the set of/o6e/s of the nodes and consider the symmetric group S , the group of all relabelings. Thus, S acts on the set of labels ... 

This finally induces an action on the set of labeled m-multigraphs Y = Smji =... 

Example (Unlabeled m-multigraphs, uniformly at random) Consider the case n = 4, so that S4 is the group in action. Assume that 4 = 0,1,2,3 is the set of (labels of) nodes. 

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. 

Exercise Write down the 27 labeled 3-multigraphs on 3 nodes in lexicographical order. 

We obtain the following set as part of the desired transversal of the orbits of labeled 3-multigraphs... 

From these labeled 3-multigraphs we obtain the set of unlabeled 3-multigraphs by simply erasing the labels ... 

---