Enumeration of the First Multicyclic Isomorphism-Free Labeled Graphs (Extended Abstract)


To appear at Formal Power Series and Algebraic Combinatorics (FPSAC01), Tempe, Arizona (USA), May 20-26, 2001


Given a fixed connected graph $H$, a $H$-free graph is one which does not contain any subgraph isomorphic to $H$. We describe a very general technique which can be applied to enumerate any labeled graphs without isomorph for the first multicyclic components, i.e., connected graphs with $n$ vertices and $(n+k)$ edges for \textit{small $k$}. The results are obtained by means of generating functions which are shown to verify a differential equation of ``heat conduction'' type, reducing the enumeration of $H$-free labeled graphs to the enumeration of two types of graphs; graphs with one and only one occurrence of $H$ and graphs with many occurrences of $H$ but necessarily juxtaposed. Then, general methods are presented and used to enumerate the first low order cyclic components of these two types of graphs. These techniques are less efficient and impracticable for greater $k$, but supply the lack of combinatorial results to deal with labeled $H$-free graphs. Furthermore, the methods are illustrated by the examples of the enumeration of $C_{3}$-free or triangle-free and $K_{4}$-free labeled graphs.

Server START Conference Manager
Update Time 23 Feb 2001 at 08:48:04
Maintainer maylis@labri.u-bordeaux.fr.
Start Conference Manager
Conference Systems