The graph of labellings of a given graph.

*(English)*Zbl 0665.05041Let be \(H=(V,E)\) a finite undirected graph with n vertices. A labelling of H is as known a bijection \(\lambda\) : V(H)\(\to \{1,...,n\}\) and there are n! ordered pairs \((H,\lambda_ i)\). In the set of these pairs is defined the property of isomorphism, which is an equivalence relation. Any class of this equivalence is called a labelled graph H and the set of all labelled graphs is denoted by \(\Lambda\) (H). In this paper a graph \(\Pi\) (H) is considerd whose vertex set consists of \(\Lambda\) (H), this means consequently that all graphs \(H_ i\) on the vertex set \(\{\) 1,...,n\(\}\) isomorphic to H are the vertices of this derived graph, and two vertices \(H_ 1\), \(H_ 2\) are adjacent iff holds
\[
| E(H_ 1)-E(H_ 2)| =| E(H_ 2)-E(H_ 1)| =1.
\]
It is shown that \(\Pi\) (H), which arises from a regular graph H, has no edges and this means \(\Pi\) (H) is discrete (Theorem 1). By four further theorems such classes of graphs H are characterized for which \(\Pi\) (H) is disconnected and in Theorem 6 is proved that holds \(\Pi\) (H)\(\cong \Pi (\overline{H})\), where \(\overline{H}\) is the complement of H.

Finally the author formulates two problems to the characterization of such graphs H for which \(\Pi\) (H) is discrete respectively disconnected.

Finally the author formulates two problems to the characterization of such graphs H for which \(\Pi\) (H) is discrete respectively disconnected.

Reviewer: H.-J.Presia

##### MSC:

05C75 | Structural characterization of families of graphs |

Full Text:
EuDML

**OpenURL**

##### References:

[1] | TOMASTA P.: Problems 15-18. Czechoslovak Conference on Graph Theory and Combinatorics, Racek Valley, May 1986. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.