\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$ denotes the subgraph of $G_\gamma$ induced by $V_s$. A component of $G_\gamma$ 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$ 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}