
arXiv: cs/0411093
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.
FOS: Computer and information sciences, Labelled graphs, triangle-free graphs, Discrete Mathematics (cs.DM), multivariate generating functions, Exact enumeration problems, generating functions, Random graphs (graph-theoretic aspects), enumerative combinatorics, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Enumeration in graph theory, Combinatorial problems, 510, forbidden subgraphs, Theoretical Computer Science, labelled graphs, asymptotic enumeration, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Computer Science - Data Structures and Algorithms, analytic combinatorics, FOS: Mathematics, Mathematics - Combinatorics, Theory, Data Structures and Algorithms (cs.DS), Enumerative combinatorics, Triangle-free graphs, random graphs, Random graphs, Asymptotic enumeration, ACM Classification: G.2.1 Combinatorics G.2.2 Graph Theory General Terms: Algorithms, Combinatorics (math.CO), ACM Classification: G.2.1 Combinatorics G.2.2 Graph Theory General Terms: Algorithms, Theory, Multivariate generating functions, Analytic combinatorics, Computer Science(all), Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Labelled graphs, triangle-free graphs, Discrete Mathematics (cs.DM), multivariate generating functions, Exact enumeration problems, generating functions, Random graphs (graph-theoretic aspects), enumerative combinatorics, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Enumeration in graph theory, Combinatorial problems, 510, forbidden subgraphs, Theoretical Computer Science, labelled graphs, asymptotic enumeration, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Computer Science - Data Structures and Algorithms, analytic combinatorics, FOS: Mathematics, Mathematics - Combinatorics, Theory, Data Structures and Algorithms (cs.DS), Enumerative combinatorics, Triangle-free graphs, random graphs, Random graphs, Asymptotic enumeration, ACM Classification: G.2.1 Combinatorics G.2.2 Graph Theory General Terms: Algorithms, Combinatorics (math.CO), ACM Classification: G.2.1 Combinatorics G.2.2 Graph Theory General Terms: Algorithms, Theory, Multivariate generating functions, Analytic combinatorics, Computer Science(all), Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 3 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
