\documentclass[11pt]{article}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\usepackage{amsthm,amssymb}
\usepackage{psfig,epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}
\newcommand{\rk}{{\rm rk}}
\newcommand{\bbox}{\nopagebreak[4] \hfill\rule{2mm}{2mm}}
\newcounter{resno}
\newenvironment{Proof}{{\sc Proof.\ }}{\hfill\bbox\bigskip}
\newenvironment{prp}{\addtocounter{resno}{1}{\bigskip\noindent\thesection.\theresno\ \sc Proposition.\ }\sl}{\bigskip}
\newenvironment{lem}{\addtocounter{resno}{1}{\bigskip\noindent\thesection.\theresno\ \sc Lemma.\ }\sl}{\bigskip}
\newenvironment{thm}{\addtocounter{resno}{1}{\bigskip\noindent\thesection.\theresno\ \sc Theorem.\ }\sl}{\bigskip}
\newenvironment{cor}{\addtocounter{resno}{1}{\bigskip\noindent\thesection.\theresno\ \sc Corollary.\ }\sl}{\bigskip}
\newenvironment{dfn}{\addtocounter{resno}{1}{\bigskip\noindent\thesection.\theresno\ \sc Definition.\ }\sl}{\bigskip}
\makeatletter
\def\section{\@startsection {section}{1}{\z@}{-3.5ex plus -1ex minus
-.2ex}{2.3ex plus .2ex}{\normalsize\bf}}
\makeatother
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo26.eps}
\vskip 1cm
{\LARGE\bf Counting Set Covers and Split Graphs}
\vskip 1.5cm
{\large Gordon F. Royle} \medskip \\
Department of Computer Science \\
University of Western Australia \\
and \\
Department of Combinatorics and Optimization \\
University of Waterloo \\
\medskip
Email address: \href{mailto:gordon@cs.uwa.edu.au}{gordon@cs.uwa.edu.au}
\vskip2.4cm
\bf {Abstract}
\end{center}
{\em
A bijection between split graphs and minimal covers of a set by subsets
is presented. As the enumeration problem for such minimal covers has
been solved, this implies that split graphs
can also be enumerated.
}
\section{Motivation}
A {\sl split graph}\/ is a chordal graph with a chordal complement. It
is straightforward to recognize split graphs, and therefore to compute
the numbers of split graphs on a small number of vertices, as shown
in Table~\ref{splitg}. Whenever such a table is given, it is to be
understood that they contain numbers of pairwise non-isomorphic
objects, rather than `labeled' objects.
The numbers in Table 1 form sequence
\htmladdnormallink{A48194}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=048194}
in
\cite{sloane94},
which is an online
database of interesting sequences of integers (see also \cite{sloaneplouffe95}).
One of the aims of this database is to permit researchers who encounter a
sequence to determine whether it has occurred before, and in what context,
thereby exposing possibly unexplored connections.
A $k$-cover of an $n$-set $N$ is a collection of $k$ subsets of
$N$ whose union is $N$. A $k$-cover is {\sl minimal} if no sub-collection also
covers $N$. Clarke \cite{clarke90} gives an expression for the number of
minimal $k$-covers of an $n$-set (where again it is to be understood
that the numbers refer to the number of pairwise non-isomorphic objects).
Using this formula, Michael Somos (private communication) computed
the total number of minimal covers of an $n$-set
and using \cite{sloane94} observed that for
$n\leq 11$ (the limit of the sequence known at that time), this number was equal to
the number of split graphs on $n$ vertices.
The current paper shows that this is no coincidence by proving
the following result:
\begin{thm}
There is a one-one correspondence between the split graphs on $n$ vertices
and the minimal covers of a set of size $n$.
\end{thm}
\begin{table}[h]
\centering
\begin{tabular}{|cr|}
\hline
Vertices&Split Graphs\\
\hline
1&1\\
2&2\\
3&4\\
4&9\\
5&21\\
6&56\\
\hline
7&164\\
8&557\\
9&2223\\
10&10766\\
11&64956\\
12&501696\\
\hline
\end{tabular}
\caption{\label{splitg}Split graphs on small numbers of vertices}
\end{table}
\section{Background}
In this paper, a graph means an undirected graph without multiple
edges or loops. For basic graph theory terminology and background,
the books of Diestel \cite{diestel97} and West \cite{west96} are recommended.
A graph is {\sl chordal}\/ (or {\sl triangulated}) if it has no cycle of
length 4 or greater as an induced subgraph. Chordal graphs form an
important class of graphs, and have been extensively studied, particularly
with respect to determining the complexity of a wide range of
problems known to be NP-hard for general graphs. A {\sl split graph}\/ is
a chordal graph with a chordal complement; this terminology arises
because a graph $X$ is a split graph if and only if there is a partition
$V(X) = I \cup C$ where $I$ is an independent set and $C$ a clique (see
Foldes \& Hammer \cite{foldeshammer77}).
Thus $X$ can be `split' into a clique and an independent set---a
split $V(X) = I \cup C$ will be called {\sl special} if every vertex in
$C$ is adjacent to at least one vertex in $I$.
Every split graph has a special split, because if there is a vertex in
$C$ not adjacent to any element of $I$, it can be moved to $I$.
In general a $k$-cover of an $n$-set may include both
empty sets and multiple occurrences of a subset.
The $k$-covers $S_1$ of
$N_1$ and $S_2$ of $N_2$ are isomorphic if there is a bijection
$\phi:N_1 \mapsto N_2$ such that $\phi(S_1) = S_2$.
Clarke \cite{clarke90} considers
several enumeration problems for $k$-covers. He encompasses the
situations where the cover is ordered or unordered, minimal or
not-necessarily minimal and counting is done both by total numbers or
numbers of isomorphism classes. However we will only need to use
the number of isomorphism classes of minimal covers---what
Clarke terms `minimal disordered unlabeled covers'.
Figure~\ref{cover} shows a minimal $4$-cover of a 9-set---in a manner analogous
to drawing a graph it represents an isomorphism class, rather than
a `labeled' cover.
\begin{figure}
\centering
\begin{picture}(140,100)(-10,-10)
\put(20,20){\oval(60,60)}
\put(100,20){\oval(60,60)}
\put(60,60){\oval(60,60)}
\put(100,80){\oval(60,20)}
\put(00,40){\circle*{5}}
\put(40,40){\circle*{5}}
\put(40,80){\circle*{5}}
\put(80,40){\circle*{5}}
\put(40,0){\circle*{5}}
\put(80,0){\circle*{5}}
\put(120,20){\circle*{5}}
\put(80,80){\circle*{5}}
\put(120,80){\circle*{5}}
\end{picture}
\caption{\label{cover}A minimal $4$-cover of a $9$-set}
\end{figure}
Given a cover $S = \{S_1,\ldots, S_k\}$, we define an element
$a \in N$ to be {\sl loyal}\/ if it lies in only one of
the subsets $S_i$. If $S$ is a minimal cover, then every subset $S_i$
contains a loyal element.
\section{Bijection}
In this section we present a bijection between split graphs on
$n$ vertices and minimal covers of a set of size $n$.
Given a minimal cover $S = \{S_1,\ldots,S_k\}$ of a set $N$, form a
graph $X = X(S)$ with vertex set $N$ as follows. Let $I \subseteq V(X)$
be a set obtained by choosing (arbitrarily) one loyal element from
each set $S_i$. Let $X$ be the graph whose edge set is the union of
a clique on each of the sets $S_i$ and a clique on $V(X)\backslash I$.
It is straightforward to verify that a different choice for the subset $I$
does not alter the isomorphism class of $X$. Figure~\ref{split} shows
the graph that arises from the cover of Figure~\ref{cover}.
\begin{lem}
If $S$ is a minimal cover, then the graph $X = X(S)$ defined above is
a split graph.
\end{lem}
\begin{Proof}
As a loyal element belongs to one subset $S_i$, it follows that
$I$ is an independent set of $X$. By definition
$V(X)\backslash I$ is a clique, and therefore $X$ is a split graph.
\end{Proof}
\begin{figure}
\centering
\begin{picture}(140,100)(-10,-10)
\put(40,0){\line(0,1){40}}
\put(40,0){\line(-1,1){40}}
\put(0,40){\line(1,0){40}}
\put(80,0){\line(0,1){40}}
\put(40,40){\line(0,1){40}}
\put(40,40){\line(1,1){40}}
\put(40,40){\line(1,0){40}}
\put(80,40){\line(0,1){40}}
\put(80,40){\line(-1,1){40}}
\put(80,80){\line(-1,0){40}}
\put(80,80){\line(1,0){40}}
\put(40,0){\line(1,2){40}}
\put(40,0){\line(1,1){40}}
\put(120,20){\line(-2,1){40}}
\put(120,20){\line(-4,1){80}}
\put(120,20){\line(-2,-1){40}}
\put(120,20){\line(-4,-1){80}}
\put(120,20){\line(-2,3){40}}
\put(00,40){\circle*{7}}
\put(40,40){\circle*{7}}
\put(40,80){\circle*{7}}
\put(80,40){\circle*{7}}
\put(40,0){\circle*{7}}
\put(80,0){\circle*{7}}
\put(120,20){\circle*{7}}
\put(80,80){\circle*{7}}
\put(120,80){\circle*{7}}
%\put(00,40){\circle{5}}
%\put(80,0){\circle{5}}
%\put(120,80){\circle{5}}
%\put(40,80){\circle{5}}
\end{picture}
\caption{\label{split}A split graph}
\end{figure}
Now, given a split graph $X$, form a cover $S = S(X)$ of $V(X)$ as
follows. Let $\cal M$ be the set of maximal cliques of $X$. Define a
maximal clique $M \in \cal M$ to be {\sl essential} if there
is a vertex $v\in V(X)$ that lies only in $M$. Then take $S$ to
be the set of essential maximal cliques of $X$.
\begin{lem}
If $X$ is a split graph, then the cover $S=S(X)$ defined above is a
minimal cover.
\end{lem}
\begin{Proof}
Let $V(X) = I \cup C$ be a special split of $X$.
Every vertex in $I$ lies in a unique maximal clique, consisting
of itself and its neighbors. Each of these maximal cliques is essential,
and as every vertex in $C$ is in one of these cliques, they form a
cover of $V(X)$. There are no other essential maximal cliques and none of this
collection can be omitted while still covering the vertices in $I$, and
hence $S$ is a minimal cover.
\end{Proof}
\begin{thm}
There is a one-one correspondence between split graphs on $n$ vertices
and minimal covers of an $n$-set.
\end{thm}
\begin{Proof}
If $X$ is a split graph with special split $V(X) = I \cup C$,
then in the cover $S(X)$, the vertices of $I$ form a collection of loyal
elements one from each subset in $S(X)$. It follows
that $X = X(S(X))$ and therefore the two maps $X \mapsto S(X)$ and
$S \mapsto X(S)$ are inverses.
\end{Proof}
\section{Enumeration}
We can now provide a formula for counting split graphs on
$n$ vertices, using Clarke's formulas. The first
step is to obtain an expression for the number of isomorphism
classes of all (not necessarily minimal) $k$-covers of an $n$-set.
This involves a double summation over all partitions of $n$ and $k$.
Denote the set of all partitions of $n$ by ${\cal P}_n$. A partition
$\alpha \in {\cal P}_n$ is given by a sequence
$[\alpha_1, \alpha_2, \ldots, \alpha_m]$ of integers summing
to $n$. If $\alpha$ is such a partition and $\mu_i$ is the
number of parts of size $i$, then let
$$
{n\choose\alpha} = {n! \over \prod_i \mu_i! i^{\mu_i}}.
$$
Clarke \cite{clarke90} shows that the number of isomorphism classes
of $k$-covers of an $n$-set is given by
$$
t(n,k) = {1 \over n!k!} \sum_{\alpha \in {\cal P}_n, \beta \in {\cal P}_k}
{n\choose\alpha}{k\choose\beta} \prod_i \left( \left( \prod_j 2^{(\alpha_i,\beta_j)} \right)-1 \right),
$$
and the number of isomorphism classes of minimal $k$-covers of an
$n$-set is
$$
m(n,k) = t(n-k,k).
$$
Therefore, if $s(n)$ is the number of split graphs on $n$ vertices,
$$
s(n) = \sum_{k=1}^n m(n,k) = \sum_{k=1}^n t(n-k,k).
$$
Table~\ref{splitgbig} gives the values of $s(n)$ for $n \leq 20$, as
computed with Maple.
(Note that the table of values for $t(n,k)$ given in Clarke \cite{clarke90}
gives slightly incorrect values for $t(6,8)$, $t(7,7)$ and $t(7,8)$.)
\begin{table}
\centering
\begin{tabular}{|cr|cr|}
\hline
Vertices&Split Graphs&Vertices&Split Graphs\\
\hline
1&1&11&64956\\
2&2&12&501696\\
3&4&13&5067146\\
4&9&14&67997750\\
5&21&15&1224275498\\
\hline
6&56&16&29733449510\\
7&164&17&976520265678\\
8&557&18&43425320764422\\
9&2223&19&2616632636247976\\
10&10766&20&213796933371366930\\
\hline
\end{tabular}
\caption{\label{splitgbig}Split graphs on up to 20 vertices}
\end{table}
{\bf Acknowledgements}
I would like to thank Michael Somos for letting me know of his
observation, and Neil Sloane for making it possible.
This research was supported in part by funds from an NSERC operating
grant.
\begin{thebibliography}{XX}
\bibitem{clarke90}
Clarke, R. J.
Covering a set by subsets.
{\sl Discrete Math. \bf 81}, (1990), 147--152.
\bibitem{diestel97}
Diestel, Reinhard.
{\sl Graph Theory},
Graduate Texts in Mathematics 173,
Springer-Verlag, (1997).
\bibitem{foldeshammer77}
Foldes, St\'ephane; Hammer, Peter L.
Split graphs,
{\sl Congressus Numerantium, No. XIX}, (1977), 311--315.
\bibitem{sloaneplouffe95}
Sloane, N. J. A.; Plouffe, Simon.
{\sl The Encyclopedia of Integer Sequences},
Academic Press, 1995.
\bibitem{sloane94}
Sloane, N. J. A.
The On-Line Encyclopedia of Integer Sequences.
Published electronically at \htmladdnormallink{http://www.research.att.com/$\sim$njas/sequences/}{http://www.research.att.com/~njas/sequences/}.
\bibitem{west96}
West, Douglas B.
{\sl Introduction to Graph Theory},
Prentice Hall, 1996.
\end{thebibliography}
\vspace*{+.5in}
\centerline{\rule{6.5in}{.01in}}
\vspace*{+.1in}
\noindent
{\small
(Concerned with sequence
\htmladdnormallink{A48194}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=048194}.)
}
\centerline{\rule{6.5in}{.01in}}
\vspace*{+.1in}
\noindent
Received May 3, 2000;
published in Journal of Integer Sequences June 6, 2000.
\centerline{\rule{6.5in}{.01in}}
\vspace*{+.1in}
\noindent
Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.research.att.com/~njas/sequences/JIS/}.
\centerline{\rule{6.5in}{.01in}}
\end{document}