Forbidden Subgraphs in Connected Graphs
| dc.creator | Ravelomanana, Vlady | |
| dc.creator | Thimonier, Loys | |
| dc.date | 2004-11-25 | |
| dc.date.accessioned | 2026-07-07T03:22:05Z | |
| dc.date.available | 2026-07-07T03:22:05Z | |
| dc.description | Given a set $ξ=\{H_1,H_2,...\}$ of connected non acyclic graphs, a $ξ$-free graph is one which does not contain any member of $% ξ$ as copy. Define the excess of a graph as the difference between its number of edges and its number of vertices. Let ${\gr{W}}_{k,ξ}$ be theexponential generating function (EGF for brief) of connected $ξ$-free graphs of excess equal to $k$ ($k \geq 1$). For each fixed $ξ$, a fundamental differential recurrence satisfied by the EGFs ${\gr{W}}_{k,ξ}$ is derived. We give methods on how to solve this nonlinear recurrence for the first few values of $k$ by means of graph surgery. We also show that for any finite collection $ξ$ of non-acyclic graphs, the EGFs ${\gr{W}}_{k,ξ}$ are always rational functions of the generating function, $T$, of Cayley's rooted (non-planar) labelled trees. From this, we prove that almost all connected graphs with $n$ nodes and $n+k$ edges are $ξ$-free, whenever $k=o(n^{1/3})$ and $|ξ| < \infty$ by means of Wright's inequalities and saddle point method. Limiting distributions are derived for sparse connected $ξ$-free components that are present when a random graph on $n$ nodes has approximately $\frac{n}{2}$ edges. In particular, the probability distribution that it consists of trees, unicyclic components, $...$, $(q+1)$-cyclic components all $ξ$-free is derived. Similar results are also obtained for multigraphs, which are graphs where self-loops and multiple-edges are allowed. | |
| dc.identifier | https://arxiv.org/abs/cs/0411093 | |
| dc.identifier | http://arxiv.org/abs/cs/0411093 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/32459 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Discrete Mathematics | |
| dc.subject | Combinatorics | |
| dc.subject | ACM Classification: G.2.1 Combinatorics G.2.2 Graph Theory General Terms: Algorithms, Theory | |
| dc.title | Forbidden Subgraphs in Connected Graphs | |
| dc.type | text |