随机图的独立数和分数匹配数的一个注记（英文）

设I为图G顶点集的子集.如果I中的任意两个点均不相邻,则称I为G的独立集.G的最大独立集的阶数称为独立数,记为α(G).图G的分数匹配是边集上的函数f∈[0,1],使得对每个顶点v都有∑f(e)≤1,这里是对所有与顶点v相关联边的函数值求和.分数匹配数β(G)是所有的分数匹配f中∑₍e∈E(G))f(e)的最大值.本文给出了随机图上关于独立数α(G)与分数匹配数β(G)的一些结果.     

独立数的一个下界

设G是一个图,其度序列为(d_v). 若由G的任意邻域导出子图的最大度至多为m, 则G的独立数至少是 ,这里当x>0, 函数f_m+1(x)大于 . 对于加权图G=(V,E,w), 证明了它的加权独立数至少是 ,这里w_v是顶点v的权重.     

图的分散数

The decay number of a connected graph is defined to be the minimum number of the components of the cotree of the graph. Upper bounds of the decay numbers of graphs are obtained according to their edge connectivities. All the bounds in this paper are tight. Moreover, for each integer k between one and the upper bound, there are infinitely many graphs with the decay number k.     

图的独立数的一个新下界

设α（Ｇ）表示简单图Ｇ＝（Ｖ，Ｅ）的独立数．本文给出了α（Ｇ）的一个新的下界：α（Ｇ）≥∑ｖ∈Ｖ（λｄ（ｖ）＋１）／（ｄ（ｖ）＋λｄ（ｖ）＋１），其中λｄ（ｖ）＝ｍａｘ｛０，βＮ（ｖ）－ｄ（ｖ）｝，ｄ（ｖ）＝｜Ｎ（ｖ）｜，Ｎ（ｖ）＝｛ｗ∈Ｖ｜（ｖ，ｗ）∈Ｅ｝，βＮ（ｖ）＝ｍｉｎｗ∈Ｎ（ｖ）ｄ（ｗ）．     

独立数的另一类关系

本文研究了图的独立数与边独立数、独立数与全独立数、边独立数与全独立数、图的独立数与其补图边独立数、图的独立数与其补图的全独立数、图的边独立数与其补图全独立数之间的关系,得到了不可改进的结果     

给定匹配数和独立数时图零度的上界

设G是一个有n个点的简单图,分别记η(G),m(G)和α(G)为图G的零度、匹配数和独立数.设θ(G)是一个非负整数,定义为使图G成为二部图至少需要从G的边集中删去的边数.本文运用二部划分运算,证明了对于有n个点并且不含有圈长为2的倍数的圈为子图的简单图G,有η(G)≤n-2m(G)+20(G)和η(G)≤2α(G)+2θ(G)-n.     

在Δ≤3的图中上独立数和上无赘数的关系

G（V，E）是一个图。β，IR分别是图G的独立数，上无赘数。这篇文章证明文章［6］中提出的一个猜想.     

匹配数为2的图的最小特征值

在所有给定阶数且匹配数为2的连通图中,我们刻画了最小特征值达到极小的图,给出了这类图最小特征值的下界.     

图的连通控制数与无赘数的一个不等式

设G是连通图,γ_C(G)和ir(G)分别表示G的连通控制数和无赘数。孙良于1990年证明了γ_c(G)≤4ir(G)—2,同时提出猜想γ_c(G)≤3ir(G)—2。本文进一步研究γ_c(G)与ir(G)的关系,并证得上述猜想成立。     

给定阶与边独立数的树和单圈图的Laplacian矩阵的最大特征值

得到了给定顶点数和边独立数的树与单圈图的Laplacian矩阵的最大特征值的精确上界，并且给出了达到上界的所有极图．     

Average Distance,Independence Number,and Spanning Trees

Let G be a connected graph of order n and independence number α. We prove that G has a spanning tree with average distance at most , if , and at most , if . As a corollary, we obtain, for n sufficiently large, an asymptotically sharp upper bound on the average distance of G in terms of its independence number. This bound, apart from confirming and improving on a conjecture of Graffiti [8], is a strengthening of a theorem of Chung [1], and that of Fajtlowicz and Waller [8], on average distance and independence number of a graph.     

A Sharp Upper Bound for the Number of Spanning Trees of a Graph

Let G = (V,E) be a simple graph with n vertices, e edges and d₁ be the highest degree. Further let λ_i, i = 1,2,...,n be the non-increasing eigenvalues of the Laplacian matrix of the graph G. In this paper, we obtain the following result: For connected graph G, λ₂ = λ₃ = ... =  λ_n-1 if and only if G is a complete graph or a star graph or a (d₁,d₁) complete bipartite graph. Also we establish the following upper bound for the number of spanning trees of G on n, e and d₁ only:

扇的倍图的邻点可区别边色数

设G(V,E)是阶数至少是3的简单连通图,若f是图G的k-正常边染色,使得对任意的uv∈E(G),C(u)≠C(v),那么称f是图G的k-邻点可区别边染色(k-ASEC),其中C(u)={f(uw)│uw∈E(G)},而χa′s(G)=min{k│存在G的一个k-ASEC},称为G的邻点可区别边色数.本文给出扇的倍图D(Fm)的邻点可区别边色数.     

The Pseudoachromatic Number of a Graph

The pseudoachromatic number of a graph G is the maximum size of a vertex partition of G (where the sets of the partition may or may not be independent) such that, between any two distinct parts, there is at least one edge of G. This parameter is determined for graphs such as cycles, paths, wheels, certain complete multipartite graphs, and for other classes of graphs. Some open problems are raised.AMS Subject Classification (1991): primary 05C75 secondary 05C85     

n圈中辐图的团覆盖数和团划分数

本文主要讨论 Petersen图的一类推广图—— n圈中辐图的团覆盖数和团划分数 ,由此得出该图的团覆盖数和团划分数相等的结论 ,同时给出了其在不同情况下的计算公式 .     

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.     

图的邻点可区别VE-全色数的一个上界

根据图的邻点可区别VE-全染色的定义和性质,用概率方法研究了图的邻点可区别VE-全染色,并给出了图的邻点可区别VE-全色数的一个上界.如果δ≥7且△≥25,则有x_at^ue（G）≤7△,其中δ是图G的最小度,△是图G的最大度.     

求最大线性无关组应注意的问题

参考文献[1]中介绍的求最大线性无关组的方法是不确切的.指出产生错误的根源及避免产生错误的方法.