Martin Pal, Tomas Vinar.
**On Multiplicity of Permutation Graphs**.
Unpublished manuscript, Comenius University Bratislava,
December 1996.

**Download preprint:** 96perm.ps, 128Kb

**Download from publisher:** not available

**Related www page:** not available

**Bibliography entry:**
BibTeX

**See also:** early version

**Abstract:**

In this article we deal with labeled and unlabeled permutation graphs. Let $\pi$ be a permutation of elements $\{1,2,\dots,n\}$. {\em Labeled graph} of $\pi$ is a graph where vertices are labeled by numbers $\{1,\dots,n\}$ and edges correspond to inversions in $\pi$. {\em Unlabeled graph} of $\pi$ is a graph without vertex labels which is isomorphic to labeled graph of $\pi$. Several permutations can be represented by the same unlabeled graph. Number of such permutation is called {\em multiplicity} of the graph. We give characterization of the family of labeled permutation graphs. We use this characterization and symmetry to show that multiplicity of unlabeled graphs $G$ and $\compl{G}$ is the same (*). It is also possible to derive other results in multiplicity of special families of graphs using our characterization. This work was inspired by lectures led by prof. Frank Harary at the Summer School at Jyv"askyla University in Finland in 1996. The problem of multiplicity of permutation graphs was stated by him and he also stated (*) as a conjecture. Unfortunately we was not able to find motivation for multiplicity of permutation graphs (although it seems that there is some) and we would be glad to hear about such motivation.

Last update: 10/01/2006