\documentclass[12pt]{article}

\hoffset-1cm
\textwidth      16cm
\textheight     23cm
\oddsidemargin  1.3cm
\evensidemargin 0.75cm
\marginparwidth 0cm
\marginparsep   0cm

\headheight     .7cm
\topskip        0.3cm
\footskip       0.8cm

\author{M. Hofmeister \\
        Siemens AG, Munich \\
        Corporate Research \& Development}
\title{Combinatorial aspects of an exact sequence \\
that is related to a graph}
%\date{July 1992}
\date{}

\frenchspacing
\sloppy

%\pagestyle{myheadings}
%\markboth{{\protect\footnotesize{\sc M. Hofmeister}}} % left
%{{\protect\footnotesize{\sc Combinatorial aspects of an exact sequence ...}}}       % right
%\frenchspacing
\sloppy
\def\IF{\hbox{$ I\hskip-0.30em F $}}
\def\IN{\hbox{$ I\hskip-0.32em N $}} 
%\setlength{\parskip}{4pt}

\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}
\newtheorem{cor}{Corollary}
\newtheorem{exa}{Example}
\newtheorem{rem}{Remark}
\newtheorem{prb}{Problem}
\newtheorem{pro}{Proposition}

\begin{document}

\maketitle

\begin{abstract}
{The five problems of counting component colorings, vertex colorings, arc colorings,
cocycles, and switching equivalence classes of a graph with respect to a finite field
up to isomorphism are related by an exact sequence that stems from a coboundary operator.
This cohomology is presented, and counting formulas are given for each of the five problems.
} 
\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Introduction}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Let $G$ be an undirected simple graph with vertex set $V = V(G)$, edge set $E =
E(G)$, and automorphism group $\Gamma$. Two objects related to $G$ ( e.g. vertices,
edges, components, vertex colorings,... ) are called {\it isomorphic}, if there
is an automorphism of G mapping the one onto the other.

For some prime power $q$, let $\IF_q$ be the finite field of this order. Consider
the following problems, which are related by the common use of the field $\IF_q$.

\begin{prb}
 Color the components of $G$ with $q$ colors. What is the number of
such colorings up to isomorphism?
\end{prb}

\begin{prb}
Count the nonisomorphic vertex colorings with $q$ colors.
\end{prb}

\begin{prb}
Let $A = A(G)$ be the set of ( directed ) arcs of the corresponding symmetric
digraph of $G$. An {\rm alternating coloring} of $G$ is an arc coloring with
color set $\IF_q$, such that inverse arcs have inverse colors, with respect to
addition in $\IF_q$. Count the alternating colorings of $G$ up to isomorphism.
\end{prb}

\begin{prb}
A {\rm cocycle} of $G$ is an alternating coloring of $G$ such that, whenever
$(i,j) \in A$, $i \in V_x$, $j \in V_y$, it follows that the color of $(i,j)$ is
$x-y$ for a vertex partition ${(V_u)}_{u \in \IF_q}$ in (~possibly~empty~) pairwise
disjoint sets. Enumerate the nonisomorphic cocycles of $G$.
\end{prb}

\begin{prb}
Two alternating colorings of $G$ are called {\rm switching equivalent}, if they
differ only by a cocycle of $G$. What is the number of nonisomorphic switching
equivalence classes?
\end{prb}

There is a nice cohomological approach relating these five problems. Our purpose is
to present this cohomology and solutions of the problems. But let us first continue
with some remarks. Problems 1 and 2 can be easily solved by {\sc P\'olya}'s
theorem. Problem 3 reduces to the problem of coloring the edges of $G$ with $q$
colors up to isomorphism if the field characteristic of $\IF_q$ ( denoted by
$\chi(\IF_q)$ ) equals two; in this case, the enumeration can be done by 
{\sc P\'olya}'s theorem again. Problem 4 is solved in \cite{5} in full generality.
The last problem was
solved in \cite{7} for complete graphs and $q = 2$, and later for arbitrary graphs
and $q = 2$ in \cite{3} and \cite{8} independently. In this paper we will present a
counting formula for this problem in the general case of arbitrary graphs and finite fields;
its proof can be found in \cite{6}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Cohomology}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

All objects considered in Problems 1 - 5 have one property in common: they form
vector spaces over $\IF_q$. A vertex coloring of $G$ with $q$ colors can be
understood as a function $f : V \to \IF_q$; let ${\cal C}^0 (G;\IF_q)$ be the vector
space of such functions, with pointwise addition and scalar multiplication. In a
similar way, an alternating coloring of $G$ can be described by a function
$F : A \to \IF_q$ such that $F(i,j) = - F(j,i)$ for each arc $(i,j) \in A$; let 
${\cal C}^1 (G;\IF_q)$ be the vector space of such functions, with pointwise addition
and scalar multiplication again. Next we define the vector space homomorphism

\begin{equation}
\delta : {\cal C}^0 (G;\IF_q) \to {\cal C}^1 (G;\IF_q)
\end{equation}

\noindent
by setting

\begin{equation}
\delta (f)(i,j) = f(i)-f(j) \hspace{1cm} ( (i,j) \in A ).
\end{equation}

\noindent
Let ${\cal H}^0 (G;\IF_q) = ke(\delta)$, the 0-{\it cohomology space} of $G$, and let
${\cal H}^1 (G;\IF_q) = {\cal C}^1 (G;\IF_q)/ im(\delta)$, the 1-{\it cohomology 
space} of $G$. Let $\delta^0 : {\cal H}^0 (G;\IF_q) \to {\cal C}^0 (G;\IF_q)$ and
$\delta^1 : {\cal C}^1 (G;\IF_q) \to {\cal H}^1 (G;\IF_q)$ be the canonical
monomorphism and epimorphism, respectively. Then we have an exact sequence

\begin{displaymath}
\delta^0 \hspace{2.4cm} \delta \hspace{2.4cm} \delta^1
\end{displaymath}
\vspace*{-0.95cm}
\begin{equation}
\label{Exact} 
0 \longrightarrow {\cal H}^0 (G;\IF_q) \longrightarrow {\cal C}^0 (G;\IF_q)
\longrightarrow {\cal C}^1 (G;\IF_q) \longrightarrow {\cal H}^1 (G;\IF_q) \longrightarrow 0.
\end{equation}

\noindent
Since ${\cal H}^0 (G;\IF_q)$ consists of those functions of ${\cal C}^0 (G;\IF_q)$ which are
constant on the components of $G$, the space ${\cal H}^0 (G;\IF_q)$ is the space of component
colorings of $G$ with $q$ colors. The set of cocycles of $G$ corresponds to $im(\delta)$,
while the set of switching equivalence classes is given by ${\cal H}^1 (G;\IF_q)$.

The following dimension formulas can be easily obtained from
elementary counting arguments and exactness of Sequence~\ref{Exact}.

\begin{pro}
Let $m,n,k$ be the number of edges, vertices, and components of $G$. Then

\begin{enumerate}
\item $dim ( {\cal H}^0 (G;\IF_q) ) = k$;
\item $dim ( {\cal C}^0 (G;\IF_q) ) = n$;
\item $dim ( {\cal C}^1 (G;\IF_q) ) = m$;
\item $dim ( {\cal H}^1 (G;\IF_q) ) = m-n+k$;
\item $dim ( im(\delta) ) = n-k$.
\end{enumerate}
\end{pro}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Automorphisms}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The automorphism group $\Gamma$ of $G$, considered as a permutation group of the vertices
of $G$, acts as a permutation group on edges, arcs, and components of $G$ via $\gamma [i,j]
= [\gamma(i),\gamma(j)]$, $\gamma (i,j) = (\gamma(i),\gamma(j))$, and $\gamma(H) =
\tilde{H}$ iff $\gamma(i)$ is a vertex of $\tilde{H}$ for some vertex $i$ of $H$, for each 
edge $[i,j]$, arc $(i,j)$,
and component $H$ of $G$. The cycle type of $\gamma \in \Gamma$, considered as a
permutation of components, vertices, and edges of $G$, is denoted by
$(\omega_1 (\gamma),\dots,\omega_k (\gamma))$, $(\nu_1 (\gamma),\dots,\nu_n (\gamma))$,
and $(\epsilon_1 (\gamma),\dots,\epsilon_m (\gamma))$, respectively. Their
corresponding sums are denoted by $\omega (\gamma)$, $\nu (\gamma)$, and
$\epsilon (\gamma)$.

The group $\Gamma$ acts not only on vertices and edges of $G$, but also on the spaces
${\cal C}^0 (G;\IF_q)$ and ${\cal C}^1 (G;\IF_q)$ via

\parbox{11cm}{
\begin{eqnarray*}
\gamma(f) = f \circ \gamma^{-1} \hspace{0.5cm} {\rm for} \hspace{0.5cm} 
f \in {\cal C}^0 (G;\IF_q), \\
\gamma(F) = F \circ \gamma^{-1} \hspace{0.5cm} {\rm for} \hspace{0.5cm} 
F \in {\cal C}^1 (G;\IF_q).
\end{eqnarray*}} \hfill
\parbox{1cm}{\begin{eqnarray}\label{TwoEqu}\end{eqnarray}}

\begin{pro}
\label{GammaDelta}
For every $\gamma \in \Gamma$, $\gamma \circ \delta = \delta \circ \gamma$.
\end{pro}

It is Proposition 
\ref{GammaDelta} from which we conclude that $\Gamma$ acts on ${\cal H}^0 (G;\IF_q)$
and $im(\delta)$ in an obvious way, and on ${\cal H}^1 (G;\IF_q)$ via

\begin{equation}
\gamma (F+im(\delta)) = \gamma(F)+im(\delta).
\end{equation}

\noindent
In the sense of Equations \ref{TwoEqu}, every $\gamma \in \Gamma$ establishes vector space
automorphisms of the four spaces of Sequence \ref{Exact} and of $im(\delta)$. Our
considerations may be summarized by the observation that the diagram

\begin{displaymath}
\delta^0 \hspace{2.4cm} \delta \hspace{2.4cm} \delta^1
\end{displaymath}
\vspace*{-1.15cm}
\begin{displaymath}
0 \longrightarrow {\cal H}^0 (G;\IF_q) \longrightarrow {\cal C}^0 (G;\IF_q)
\longrightarrow {\cal C}^1 (G;\IF_q) \longrightarrow {\cal H}^1 (G;\IF_q) \longrightarrow 0
\end{displaymath}
\vspace*{-0.5cm}
\begin{equation}
\label{DiaGram}
\hspace*{-0.25cm}
\gamma \downarrow \hspace{2.1cm} \gamma \downarrow \hspace{2.1cm} \gamma \downarrow
\hspace{2.1cm} \gamma \downarrow
\end{equation}
\vspace*{-0.5cm}
\begin{displaymath}
0 \longrightarrow {\cal H}^0 (G;\IF_q) \longrightarrow {\cal C}^0 (G;\IF_q)
\longrightarrow {\cal C}^1 (G;\IF_q) \longrightarrow {\cal H}^1 (G;\IF_q) \longrightarrow 0
\end{displaymath}
\vspace*{-0.8cm}
\begin{displaymath}
\delta^0 \hspace{2.4cm} \delta \hspace{2.4cm} \delta^1
\end{displaymath}

\noindent
is commutative.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Enumeration}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


The Problems 1-5 can be restated in the following form: Count the orbits of the actions
of $\Gamma$ on the spaces  ${\cal H}^0 (G;\IF_q)$,  ${\cal C}^0 (G;\IF_q)$,
${\cal C}^1 (G;\IF_q)$, $im(\delta)$, and  ${\cal H}^1 (G;\IF_q)$. By {\sc Burnside}'s
lemma ( which is in fact due to {\sc Cauchy-Frobenius} ), these problems reduce to 
the problems of counting the component colorings, vertex
colorings, alternating colorings, cocycles, and switching equivalence classes that are
fixed under $\gamma$, for every $\gamma \in \Gamma$. 

We define homomorphisms $\alpha_\gamma^0 : {\cal C}^0 (G;\IF_q) \to {\cal C}^0 (G;\IF_q)$
and $\alpha_\gamma^1 : {\cal C}^1 (G;\IF_q) \to {\cal C}^1 (G;\IF_q)$ by setting 

\parbox{11cm}{
\begin{eqnarray*}
\alpha_\gamma^0 (f) = f-\gamma (f), \\
\alpha_\gamma^1 (F) = F-\gamma (F),
\end{eqnarray*}} \hfill
\parbox{1cm}{\begin{eqnarray}\end{eqnarray}}

\noindent
for $f \in {\cal C}^0 (G;\IF_q)$  and $F \in {\cal C}^1 (G;\IF_q)$. Set 
$\beta_\gamma^0 = \alpha_\gamma^0 | {\cal H}^0 (G;\IF_q)$, and let $\beta_\gamma^1 :
{\cal H}^1 (G;\IF_q) \to {\cal H}^1 (G;\IF_q)$ be defined by 
$\beta_\gamma^1 ( F+im(\delta) ) = \alpha_\gamma^1 (F) + im(\delta)$. In order to solve the
Problems 1-5, it suffices to determine the sizes of $ke(\beta_\gamma^0)$,
$ke(\alpha_\gamma^0)$, $ke(\alpha_\gamma^1)$, $ke(\alpha_\gamma^1 | im(\delta))$, and
$ke(\beta_\gamma^1)$. But in the cases of nonisomorphic component colorings and vertex
colorings we can use {\sc P\'olya}'s theorem directly.

\begin{thm}
The number of nonisomorphic component colorings of $G$ with $q$ colors is

\begin{equation}
\frac{1}{|\Gamma|} \sum_{\gamma \in \Gamma} q^{\omega(\gamma)} .
\end{equation}
\end{thm}

\begin{thm}
The number of nonisomorphic vertex colorings of $G$ with $q$ colors is

\begin{equation}
\frac{1}{|\Gamma|} \sum_{\gamma \in \Gamma} q^{\nu(\gamma)} .
\end{equation}
\end{thm}

Let $\gamma \in \Gamma$, and let $\sigma_\nu$ be a vertex cycle of $\gamma$. The cycle 
$\sigma_\nu$ is called {\it diagonal}, if its size is even, say $|\sigma_\nu| = 2t$, and
$[i,\gamma^t(i)] \in E$ for some $i \in \sigma_\nu$. The corresponding edge cycle and
arc cycle as well as their edges and arcs are called diagonal, too. Now set

\begin{equation}
\rho (\gamma) = \left\{ \begin{array}{l@{\quad,\quad}l}
               {\rm number\hspace{0.1cm}of\hspace{0.1cm}diagonal\hspace{0.1cm}vertex\hspace{0.1cm}cycles
                \hspace{0.1cm} of}\hspace{0.1cm} \gamma & {\rm if} \hspace{0.3cm} \chi(\IF_q) \not= 2, \\
               0 & {\rm if} \hspace{0.3cm} \chi(\IF_q) = 2.
            \end{array} \right.
\end{equation}

\noindent
\begin{thm}
The number of nonisomorphic alternating colorings of $G$ with $q$ colors is

\begin{equation}
\frac{1}{|\Gamma|} \sum_{\gamma \in \Gamma} q^{\epsilon(\gamma)-\rho(\gamma)} .
\end{equation}
\end{thm}

Now we turn attention on the cocycles of $G$. Let $\sigma_\omega$ be a component cycle of 
$\gamma$. A vertex cycle $\sigma_\nu$ of $\gamma$ is {\it associated} to $\sigma_\omega$,
if $\sigma_\nu$ permutes vertices of components in $\sigma_\omega$. Let $\kappa(\gamma)$
be the number of component cycles $\sigma_\omega$ of $\gamma$ that have an associated
vertex cycle $\sigma_\nu$ such that

\begin{equation}
\frac{|\sigma_\nu|}{|\sigma_\omega|} \not\equiv 0\pmod{\chi(\IF_q)}.
\end{equation}

\noindent
Note that $\frac{|\sigma_\nu|}{|\sigma_\omega|}$ indicates how many vertices of $\sigma_\nu$
are contained in a component of $\sigma_\omega$. Recall that $k$ is the number of components of $G$.

\begin{thm}
The number of nonisomorphic cocycles of $G$ over $\IF_q$ is

\begin{equation}
\frac{1}{|\Gamma| q^k} \sum_{\gamma \in \Gamma} q^{\nu(\gamma)-\kappa(\gamma)+\omega(\gamma)} .
\end{equation}
\end{thm}

As an application of Theorem 4, let $ G = K_n $ be the complete
graph with $ n $ vertices.
Then we have $ k=1 $ and $ \Gamma = S_n $, the symmetric group on
the $ n $ vertices. For every $ \gamma \in S_n $ we have
$ \omega(\gamma) = 1 $, hence $ |\sigma_{\omega}| = 1 $ for the
only component cycle of $ \gamma $. We conclude that
$$
 \kappa (\gamma) = \left\{ \begin{array}{rl}
     0 & \mbox{if $ |\sigma_{\nu}| \equiv 0 \pmod{p} $ for every
         vertex cycle $ \sigma_{\nu} $ of $ \gamma $}, \\
     1 & \mbox{otherwise} ~.
                    \end{array} \right.
$$
Now, by Theorem 4, the number of non-equivalent cocycles of
$ K_n $ over $ \IF_q $ is
\begin{equation}                                                % (5)
\frac{1}{n!} \sum q^{\nu(\gamma)} + \frac{1}{q \cdot n!}
\sum q^{\nu(\gamma)},
\end{equation}
where the first sum extends over all $ \gamma \in S_n $ such
that $ |\sigma_{\nu}| \equiv 0 \pmod{p} $ for every vertex
cycle $ \sigma_{\nu} $ of $ \gamma $, and the second sum extends
over the remaining permutations in $ S_n $.

The {\it cycle index} of $ S_n $ [2] is the polynomial
$$
Z(S_n;{\bf s}) = \frac{1}{n!} \sum_{\gamma \in S_n}
s_1^{\nu_1(\gamma)} \dots s_n^{\nu_n(\gamma)} ~,
$$
where $ {\bf s} = (s_1,s_2,s_3,\dots) $. Set
$ {\bf 1} = (1,1,1,\dots) $ and for $ r \in I\!\!N $ define
$ {\bf 1} [r] = (x_1,x_2,x_3,\dots) $ by setting
$$
x_i = \left\{ \begin{array}{rl}
     1 & \mbox{if $ r $ is a divisor of $ i $ },  \\
     0 & \mbox{otherwise} ~.
                    \end{array} \right.
$$
Then it follows from Expression 14 by a short calculation
that the number of non-equivalent cocycles of $ K_n $
over $ \IF_q $ is
$$
\frac{1}{q} (Z(S_n;q \cdot {\bf 1}) + (q-1)
             Z(S_n;q \cdot {\bf 1}[p]))  ~,
$$
where, as usual, the number $ p $ is the field characteristic
of $ \IF_q $. From this formula we obtained Table 1. The cycle
indices of small order symmetric groups are tabulated in \cite{2}.

\begin{table}[ht]
\begin{center}
\begin{tabular}{r|rrrrrrr}
$ q \backslash^{\textstyle n} $ & 2 & 3 & 4 & 5 & 6 & 7 & 8  \\
\hline
2 & 2 & 2 & 3 & 3 & 4 & 4 & 5 \\
3 & 2 & 4 & 5 & 7 & 10 & 12 & 15 \\
4 & 4 & 5 & 11 & 14 & 24 & 30 & 45 \\
5 & 3 & 7 & 14 & 26 & 42 & 66 & 99 \\
7 & 4 & 12 & 30 & 66 & 132 & 246 & 429 \\
8 & 8 & 15 & 50 & 99 & 232 & 429 & 835 \\
9 & 5 & 21 & 55 & 143 & 339 & 715 & 1430 \\
11 & 6 & 26 & 91 & 273 & 728 & 1768 & 3978 \\
13 & 7 & 30 & 140 & 476 & 1428 & 3876 & 9690 \\
16 & 16 & 51 & 276 & 969 & 3504 & 10659 & 30954 \\
17 & 9 & 57 & 285 & 1197 & 4389 & 14296 & 43263 \\
19 & 10 & 70 & 385 & 1771 & 7084 & 25300 & 82225 \\
23 & 12 & 100 & 650 & 3510 & 16380 & 67860 & 254475 \\
25 & 13 & 117 & 819 & 4755 & 23751 & 105183 & 420732 \\
\end{tabular}
 \\  \bigskip
 Table 1
\end{center}
\end{table}

Now we will present a counting formula for the number of nonisomorphic switching
equivalence classes of the graph $G$. We remarked already, that the
problem reduces, by {\sc Burnside}'s lemma, to the computation of the size of 
$ke(\beta_\gamma^1)$, since this space is the set of switching equivalence classes fixed
by the automorphism $\gamma \in \Gamma$. 

Consider the fiber product of the homomorphisms $\delta$ and $\alpha_\gamma^1$, i.e.
the space ${\cal C}_\gamma (G;\IF_q)$ consisting of all pairs $(f,F)$ such that 
$\delta(f) = \alpha_\gamma^1 (F)$, together with the canonical projections
$\mu_\gamma^0 : {\cal C}_\gamma (G;\IF_q) \to {\cal C}^0 (G;\IF_q)$ and 
$\mu_\gamma^1 : {\cal C}_\gamma (G;\IF_q) \to {\cal C}^1 (G;\IF_q)$. Set
${\cal C}_\gamma^0 (G;\IF_q) = im(\mu_\gamma^0)$ and 
${\cal C}_\gamma^1 (G;\IF_q) = im(\mu_\gamma^1)$. Then we have
$im(\delta^1 | {\cal C}_\gamma^1 (G;\IF_q)) = ke(\beta_\gamma^1)$. It is clear that
we can obtain the size of $ke(\beta_\gamma^1)$ from $dim({\cal C}_\gamma^0 (G;\IF_q))$.

For an automorphism $\gamma$ of $G$, let $G_\gamma$ be the {\it cycle graph} of $G$ with respect to
$\gamma$, i.e. the simple graph with the vertex cycles of $\gamma$ as vertices; two different
vertices $\sigma_\nu$, $\tau_\nu$ of $G_\gamma$ are adjacent in $G_\gamma$ iff there are
$i \in \sigma_\nu$, $j \in \tau_\nu$ such that $[i,j] \in E(G)$.

We define an evaluation on vertex cycles of $\gamma$ by
setting $\Omega(\sigma_\nu) = s$ if $|\sigma_\nu| = p^s u$, where $s$ is chosen so that $p$ is
not a divisor from $u$. Let $V_s$ be the set of vertex cycles of $\gamma$ that satisfy 
$\Omega(\sigma_\nu) = s$. Then $G_\gamma<V_s>$ denotes the subgraph of $G_\gamma$ induced by
$V_s$. A component of $G_\gamma<V_s>$ is called {\it minimal} in $G_\gamma$ if it does not
contain a vertex that is adjacent in $G_\gamma$ to a vertex $\sigma_\nu$ with 
$\Omega(\sigma_\nu) < s$. Let $X_\gamma$ be the subgraph consisting of the minimal components
of all graphs $G_\gamma<V_s>$ in $G_\gamma$ if $p \not= 2$, respectively the subgraph consisting
of such components that do not contain a vertex that is a diagonal vertex cycle of $\gamma$
if $p = 2$. Let $\xi (\gamma)$ be the number of components of $X_\gamma$.

Recall that the number of vertex cycles of $\gamma$ is denoted by $\nu (\gamma)$.


\begin{thm}
\label{Main}
The number of nonisomorphic switching equivalence classes of $G$ is

\begin{equation}
\frac{1}{|\Gamma|} \sum_{\gamma \in \Gamma} q^{\epsilon(\gamma)-\nu(\gamma)+\xi(\gamma)
-\rho(\gamma)}.
\end{equation}
\end{thm}

In order to illustrate the last theorem, consider again the complete graph $G = K_n$
with $n$ vertices, and remember the notations about its automorphism group given above.

\begin{table}[th]
\begin{center}
\begin{tabular}{r|rrrrrrr}
$ q \backslash^{\textstyle n} $ & 2 & 3 & 4 & 5 & 6 & 7  \\
\hline
2 & 1 & 2 & 3 & 7 & 16 & 54 \\
3 & 1 & 2 & 4 & 14 & 120 & 3222 \\
4 & 1 & 4 & 11 & 100 & 2200 & 242064  \\
5 & 1 & 3 & 10 & 155 & 14030 & 6099115 \\
7 & 1 & 4 & 21 & 1036 & 395283 & 943185908 \\
8 & 1 & 8 & 50 & 3088 & 1557536 & 7022450816 \\
\end{tabular}
 \\  \bigskip
 Table 2
\end{center}
\end{table}

Let $\gamma \in S_n$, and let $(\nu_1, \dots ,\nu_n)$ be the cycle type of $\gamma$.
Then $\nu(\gamma) = \sum_{i=1}^n \nu_i$. From the cycle index of the {\it pair group}
$S_n^{(2)}$ ( see \cite{2} ) we obtain $\epsilon(\gamma)$; the cycle indices of pair groups are
tabulated in \cite{2} for $n \le 10$.

Every vertex cycle of $\gamma$ of even length is diagonal, hence 

\begin{equation}
\xi(\gamma) = \left\{ \begin{array}{l@{\quad,\quad}l}
              0 & {\rm if\hspace{1mm}every\hspace{1mm}vertex\hspace{1mm}cycle\hspace{1mm}
                  of\hspace{1mm}\gamma\hspace{1mm}is\hspace{1mm}of\hspace{1mm}even\hspace{1mm}
                  length\hspace{1mm}and\hspace{1mm}}p=2, \\
              1 & {\rm otherwise.} 
            \end{array} \right.
\end{equation}

\noindent
Recall that $p$ is the field characteristic of $\IF_q$. Furthermore,

\begin{equation}
\rho(\gamma) = \left\{ \begin{array}{l@{\quad,\quad}l}
              {\rm Number\hspace{1mm}of\hspace{1mm}vertex\hspace{1mm}cycles\hspace{1mm}of\hspace{1mm}
              \gamma\hspace{1mm}of\hspace{1mm}even\hspace{1mm}length}  & {\rm if}\: p \not=2, \\
              0 & {\rm otherwise.} 
            \end{array} \right.
\end{equation}

\noindent
Using these facts, we obtained Table 2 presenting the numbers of nonisomorphic switching
equivalence classes of $K_n$ for some small values of $n$ and $q$.


\begin{thebibliography}{8}


\bibitem{1} {\sc J.L. Gross, T.W. Tucker},
                {\em Topological Graph Theory},
                Wiley Interscience Series in Discrete Mathematics and
                Optimization, John Wiley \&\ Sons (1987).
\bibitem{2} {\sc F. Harary, E.M. Palmer}, {\em Graphical Enumeration},
                Academic Press, New York and London (1973).
\bibitem{3} {\sc M. Hofmeister},
                {\em Counting double covers of graphs},
                J. Graph Theory {\bf 12} (1988), 437-444.
\bibitem{4} {\sc M. Hofmeister},
                {\em Isomorphisms and automorphisms of graph coverings},
                Discrete Math. {\bf 98} (1991), 175-183.
\bibitem{5} {\sc M. Hofmeister},
                {\em Non-equivalent cocycles of graphs over finite fields},
                submitted.
\bibitem{6} {\sc M. Hofmeister},
                {\em On an exact sequence related to a graph},
                submitted.
\bibitem{7} {\sc C.L. Mallows, N.J.A. Sloane},
                {\em Two-graphs, switching classes, and Euler graphs are
                 equal in number},
                SIAM J. Appl. Math. {\bf 28} (1975), 876-880.
\bibitem{8} {\sc A.L. Wells}, {\em Even signings, signed switching classes, 
                 and $(1,-1)$-matrices}, J. Comb. Theory Ser. B
                 {\bf 36} (1984), 194-212.

\end{thebibliography}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                          END OF TEX FILE                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%






\end{document}

