\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}