Asymptotic Behaviour of the Number of Labelled Essential Acyclic Digraphs and Labelled Chain Graphs

We provide an asymptotic formula for the number of labelled essential DAGs a_n and show that lim_na_n/a_n=c, where a_n is the number of labelled DAGs and c13.65, which is interesting in the field of Bayesian networks. Furthermore, we present an asymptotic formula for the number of labelled chain graphs.Acknowledgment. I would like to thank Prof. Peter Grabner for his support and very helpful discussions, which where constitutive for this article. I am also thankful to the referees for their comments.This Research was supported by the Austrian Science Fund (FWF), START-Project Y96-MATFinal version received: January 28, 2004     

Asymptotic enumeration of 2-covers and line graphs

A 2-cover is a multiset of subsets of [n]?{1,2,…,n} such that each element of [n] lies in exactly two of the subsets. A 2-cover is called proper if all of the subsets are distinct, and is called restricted if any two of them intersect in at most one element.In this paper we find asymptotic enumerations for the number of line graphs on n labelled vertices and for 2-covers.We find that the number s_n of 2-covers and the number t_n of proper 2-covers both have asymptotic growth

     

Enumeration of matchings in families of self-similar graphs

The number of matchings of a graph G is an important graph parameter in various contexts, notably in statistical physics (dimer-monomer model). Following recent research on graph parameters of this type in connection with self-similar, fractal-like graphs, we study the asymptotic behavior of the number of matchings in families of self-similar graphs that are constructed by a very general replacement procedure. Under certain conditions on the geometry of the graphs, we are able to prove that the number of matchings generally follows a doubly exponential growth. The proof depends on an independence theorem for the number of matchings that has been used earlier to treat the special case of Sierpiński graphs. We also further extend the technique to the matching-generating polynomial (equivalent to the partition function for the dimer-monomer model) and provide a variety of examples.     

Longest Cycles in 3-connected Graphs with Given Independence Number

Fouquet and Jolivet conjectured that a k-connected graph of order n and independence number α ≥ k has a cycle of length at least [Fouquet and Jolivet, Problèmes combinatoires et théorie des graphes Orsay (1976), Problems, page 438]. Here we prove this conjecture for k=3.     

Bicolored Matchings in Some Classes of Graphs

We consider the problem of finding in a graph a set R of edges to be colored in red so that there are maximum matchings having some prescribed numbers of red edges. For regular bipartite graphs with n nodes on each side, we give sufficient conditions for the existence of a set R with |R|=n+1 such that perfect matchings with k red edges exist for all k,0≤k≤n. Given two integers p<q we also determine the minimum cardinality of a set R of red edges such that there are perfect matchings with p red edges and with q red edges. For 3-regular bipartite graphs, we show that if p≤4 there is a set R with |R|=p for which perfect matchings M_k exist with |M_k∩R|≤k for all k≤p. For trees we design a linear time algorithm to determine a minimum set R of red edges such that there exist maximum matchings with k red edges for the largest possible number of values of k.     

Bounds for the Independence Number of Critical Graphs

In 1968 Vizing conjectured that any independent vertex set ofan edge-chromatic critical graph G contains at most half ofthe vertices of G, that is, (G|(G)|). Let be the maximum vertexdegree in a critical graph. For each , we determine c() suchthat (G)c()|V)|. 1991 Mathematics Subject Classification 05C15,05C70.     

Factor-Critical Graphs with Given Number of Maximum Matchings

A connected graph G is said to be factor-critical if G − ν has a perfect matching for every vertex ν of G. In this paper, the factor-critical graphs G with |V(G)| maximum matchings and with |V(G)| + 1 ones are characterized, respectively. From this, some special bicritical graphs are characterized. This work is supported by the Ph.D. Programs Foundation of Ministry of Education of China (No.20070574006) and the NNSF(10201019) of China.     

无爪3 -正则图的独立数

如果图G的一个集合X中任两个点不相邻, 则称 X 为独立集合. 如果 N[X]=V(G), 则称X是一个控制集合. i(G)(β(G))分别表示所有极大独立集合的最小(最大)基数. γ(G)(Γ(G))表示所有极小控制集合的最小(最大)基数. 在这篇论文中, 作者证明如下结论: (1) 如果 G ∈R 且G 是n阶3 -正则图, 则 γ(G)= i(G), β(G)=n/3. (2) 每个n阶连通无爪3 -正则图 G, 如果 G(G≠ K₄) 且不含诱导子图K₄-e, 则 β(G) =n/3.     

Extremal Graphs With a Given Number of Perfect Matchings

Let denote the maximum number of edges in a graph having n vertices and exactly p perfect matchings. For fixed p, Dudek and Schmitt showed that for some constant when n is at least some constant . For , they also determined and . For fixed p, we show that the extremal graphs for all n are determined by those with vertices. As a corollary, a computer search determines and for . We also present lower bounds on proving that for (as conjectured by Dudek and Schmitt), and we conjecture an upper bound on . Our structural results are based on Lovász's Cathedral Theorem.     

Asymptotic enumeration of RNA secondary structure

Based on the new representation of RNA secondary structures, we obtain the basic relations about secondary structures with a prescribed size m for hairpin loops and minimum stack length l. Furthermore, we make an asymptotic analysis on RNA secondary structures with certain additional constrains.     

Lower Bounds of Size Ramsey Number for Graphs with Small Independence Number

Acta Mathematicae Applicatae Sinica, English Series - Let r ≥ 3 be an integer such that r ? 2 is a prime power and let H be a connected graph on n vertices with average degree at least...     

An Asymptotic Ratio in the Complete Binary Tree

Let T _n be the complete binary tree of height n considered as the Hasse-diagram of a poset with its root 1 _n as the maximum element. For a rooted tree T, define two functions counting the embeddings of T into T _n as follows A(n;T)=|{S T _n  : 1 _n ∈S, S≅T}|, and B(n;T)=|{S T _n :1 _n ∉S, S≅T}|. In this paper we investigate the asymptotic behavior of the ratio A(n;T)/B(n;T), and we show that lim  _n→∞[A(n;T)/B(n;T)]=2^ℓ;−1−1, for any tree T with ℓ leaves. This revised version was published online in June 2006 with corrections to the Cover Date.     

渐近稳定性定理的推广

本文讨论了较一般的非线性微分方程组零解的渐近稳定性，推广了文［１］及文［２］的证明方法和其中的一些结果．特别是去掉了Ｌｉａｐｕｎｏｖ函数具有无穷小上界的条件。最后举例说明作者所得的新结果有效且优于前人的有关结果．     

Asymptotic enumeration of some RNA secondary structures

In this paper, we derive recursions of some RNA secondary structures with certain properties under two new representations. Furthermore, by making use of methods of asymptotic analysis and generating functions we present asymptotic enumeration of these RNA secondary structures.     

A Degree Sum Condition Concerning the Connectivity and the Independence Number of a Graph

Let G be a graph and S ⊂ V(G). We denote by α(S) the maximum number of pairwise nonadjacent vertices in S. For x, y ∈ V(G), the local connectivity κ(x, y) is defined to be the maximum number of internally-disjoint paths connecting x and y in G. We define . In this paper, we show that if κ(S) ≥ 3 and for every independent set {x ₁, x ₂, x ₃, x ₄} ⊂ S, then G contains a cycle passing through S. This degree condition is sharp and this gives a new degree sum condition for a 3-connected graph to be hamiltonian.     

An application of Vizing and Vizing-like adjacency lemmas to Vizing’s Independence Number Conjecture of edge chromatic critical graphs

In 1968, Vizing conjectured that, if G is a Δ-critical graph with n vertices, then , where α(G) is the independence number of G. In this note, we apply Vizing and Vizing-like adjacency lemmas to this problem and obtain better bounds for Δ∈{7,…,19}.     

A Characterization of Graphs Where the Independence Number Equals the Radius

In a classical 1986 paper by Erdös, Saks and Saós every graph of radius r has an induced path of order at least 2r ? 1. This result implies that the independence number of such graphs is at least r. In this paper, we use a result of S. Fajtlowicz about radius-critical graphs to characterize graphs where the independence number is equal to the radius, for all possible values of the radius except 2, 3, and 4. We briefly discuss these remaining cases as well.     

完美匹配树的次大和次小的最大特征值

本文讨论完美匹配树的次大和次小的最大特征值问题,得到了次大的最大特征值的上界的明确表达式并确定了达到此上界的极树,同时也得到了次小的最大特征值的下界并确定了相应的极树。     

Asymptotic enumeration of dense 0-1 matrices with specified line sums

Let s=(s₁,s₂,…,sm) and t=(t₁,t₂,…,tn) be vectors of non-negative integers with . Let B(s,t) be the number of m×n matrices over {0,1} with jth row sum equal to sj for 1?j?m and kth column sum equal to tk for 1?k?n. Equivalently, B(s,t) is the number of bipartite graphs with m vertices in one part with degrees given by s, and n vertices in the other part with degrees given by t. Most research on the asymptotics of B(s,t) has focused on the sparse case, where the best result is that of Greenhill, McKay and Wang (2006). In the case of dense matrices, the only precise result is for the case of equal row sums and equal column sums (Canfield and McKay, 2005). This paper extends the analytic methods used by the latter paper to the case where the row and column sums can vary within certain limits. Interestingly, the result can be expressed by the same formula which holds in the sparse case.     

On the Number of Group-Weighted Matchings

Let G be a bipartite graph with a bicoloration {A,B}, |A|=|B|. Let E(G) A x B denote the edge set of G, and let m(G) denote the number of perfect matchings of G. Let K be a (multiplicative) finite abelsian group |K| = k, and let w:E(G) K be a weight assignment on the edges of G. FOr S E(G) let w(S) = _eSw(e). A perfect matching M of G is a w-matching if w(M)=1. We shall be interested in m(G,w), the number of w-matchings of G.It is shown that if deg(a) d for all a A, then either G has no w-matchings, or G has at least (d - k + 1)! w-matchings.