Forbidden Subgraphs in Connected Graphs

Details Forbidden Subgraphs in Connected Graphs Forbidden Subgraphs in Connected Graphs

2004-11-25

arxiv.org/abs/cs/0411093v1

Computer Science

Data Structures and Algorithms

Scientific paper

Given a set $\xi=\{H_1,H_2,...\}$ of connected non acyclic graphs, a $\xi$-free graph is one which does not contain any member of $% \xi$ 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,\xi}$ be theexponential generating function (EGF for brief) of connected $\xi$-free graphs of excess equal to $k$ ($k \geq 1$). For each fixed $\xi$, a fundamental differential recurrence satisfied by the EGFs ${\gr{W}}_{k,\xi}$ 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 $\xi$ of non-acyclic graphs, the EGFs ${\gr{W}}_{k,\xi}$ 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 $\xi$-free, whenever $k=o(n^{1/3})$ and $|\xi| < \infty$ by means of Wright's inequalities and saddle point method. Limiting distributions are derived for sparse connected $\xi$-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 $\xi$-free is derived. Similar results are also obtained for multigraphs, which are graphs where self-loops and multiple-edges are allowed.

Affiliated with

Also associated with

No associations

Rating

Forbidden Subgraphs in Connected Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Forbidden Subgraphs in Connected Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Forbidden Subgraphs in Connected Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-414846