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