不含三角形的图的λ3-最优性的充分条件

设G=(V,E)是一个连通图,边集S(?)E是一个3-限制性边割,如果G-S是不连通的并且G-S的每个分支至少有三个点.图G的3-限制性边连通度λ_3(G)是G中最小的一个3-限制性边割的基数.图G是λ_3(G)连通的,如果3-限制性边割存在.G是λ_3-最优的,如果λ_3(G)=ξ_3(G),其中ξ_3(G)=min{|[U,(?)]|:U(?)V,|U|=3 and G[U]是连通的).G[U]表示V的子集U的导出子图,(?)=V\U表示U的补.[U,(?)]是一条边的一个端点在U中另一个端点在(?)中的边的集合.本文给出了不含三角形的图是λ_3-最优的一些充分条件.     

正则图的限制性边连通度

将连通图分离成阶至少为二的分支之并的边割称为限制性边割,最小限制性边割的阶称为限制性边连通度. 用λ′(G)表示限制性连通度,则λ′(G)≤ξ(G),其中ξ(G)表示最小边度. 如果上式等号成立,则称G是极大限制性边连通的. 本文证明了当k＞|G|/2时,k正则图G是极大限制性边连通的,其中k≥2, |G|≥4; k的下界在某种程度上是不可改进的.     

超级限制边连通二部图的充分条件

设S是连通图G的一个边割.若G-S不包含孤立点,则称S是G的一个限制边割.图G的最小限制边割的边数称为G的限制边连通度,记为λ'(G).如果图G的限制边连通度等于其最小边度,则称图G是最优限制边连通的,简称λ'-最优的.进一步,如果图G的每个最小限制边割恰好分离出图G的一条边,则称图G是超级限制边连通的,简称超级-λ'的.设G是一个最小度δ(G)≥2的n≥4阶二部图,ξ(G)是G的最小边度.本文证明了(a)若ξ(G)≥(n/2-2)(1+1/δ(G)-1),则G是λ'-最优的;(b)若ξ(G)>(n/2-2)(1+1/δ(G)-1),则G是超级-λ'的,除非图G是K2,n-2,n≥6或是Cartesian积图Kn/4,n/4×K2,其中n≥8且n整除4.最后,论文举例说明该结果是最好可能的.     

点可迁图的限制边连通性

3限制边割是连通图的一个边割, 它将此图分离成阶不小于3的连通分支. 图G的最小3限制边割所含的边数称为此图的3限制边连通度, 记作λ\-3(G). 它以图G的3阶连通点导出 子图的余边界的最小基数ξ_3(G)为上界. 如果λ_3(G)=ξ_3(G), 则称图G是极大3限制边连通的 . 已知在某种程度上,3限制边连通度较大的网络有较好的可靠性. 作者在文中证明: 如果k正则连通点可迁图的 围长至少是5, 那么它是是极大3限制边连通的.     

点可迁图的限制边连通度

设S是连通图G的边子集.如果G-S不连通而且不含孤立点,那么称S是G的一个限制边割.G中所有限制边割中最小边数称为G的限制边连通度,记为′(G).限制边连通度是对传统边连通度的推广,而且是计算机互连网络容错性的一个重要度量.点可迁图是一类重要的网络模型.本文证明了如下结论 设G是连通的点可迁图.如果G的点数n4,而且点度k2,那么或者′(G)=2k-2,或者n是偶数,G含三角形且存在整数m2,使得k′(G)=n/m2k-3.     

极小k边连通图的一个极值问题

本文只讨论单纯图。所有符号的意义均同于[2]。依照[1]给出定义 如图 G=(V,E)具有性质:λ(G)=k,而对(?)e∈E 均有λ(G-e)=k-1,则称 G 为极小 k 边连通图。设已给图 G=(V,E),如果 A,B(?)V,且 A∩B=φ,则记[A,B]={xy↓x∈A,y∈B,xy∈E}。如果 S(?)E,|S|=k,且 G-S=G_1 U G_2 V(G_1)∩V(G_2)=φ,V(G_1)≠φ,     

图是超限制性边连通的充分条件

设G=（V,E）是连通图.边集S E是一个限制性边割,如果G-S是不连通的且G—S的每个分支至少有两个点.G的限制性连通度λ＇（G）是G的一个最小限制性边割的基数.G是λ＇-连通的,如果G存在限制性边割.G是λ＇-最优的,如果λ＇（G）=ζ（G）,其中ζ（G）是min{d（x）＋d（y）-2：xy是G的一条边}.进一步,如果每个最小的限制性边割都孤立一条边,则称G是超限制性边连通的或是超-λ＇.G的逆度R（G）=∑_（v∈V） 1/d（v）,其中d（v）是点v的度数.我们证明了G是λ＇-连通的且不含三角形,如果R（G）≤2＋1/ζ-ζ/（（2δ-2）（2δ-3））＋（n-2δ-ζ＋2）/（（n-2δ＋1）（n-2δ＋2））,则G是超-λ＇.     

极大限制边连通超图的两个充分条件

图的限制边连通度是经典边连通度的推广,可用于精确度量网络的容错性.极大限制边连通图是使限制边连通度达到最优的一类图.首先将图的限制边连通度和最小边度的概念推广到r一致线性超图H,证明当H的最小度δ(H)≥r+1时,H的最小边度ξ(H)是它的限制边连通度λ′(H)的一个上界,并将满足ξ(H)=λ′(H)的H称为极大限制边连通超图,然后证明n个顶点的r一致线性超图H如果满足δ(H)≥(n-1)/(2(r-1))+(r-1),则它是极大限制边连通的,最后证明直径为2,围长至少为4的一致线性超图是极大限制边连通的.所得结论是图中相关结果的推广.     

具有两个同阶轨道的双轨道图的圈边连通度

一个边割被称为圈边割,如果该边割能分离图的两个不同圈.如果一个图有圈边割,称该图为圈边可分离的.一个圈边可分离图G的最小圈边割的阶数被称为圈边连通度,记作cλ（G）.定义：ζ（G）=min{w（X）｜X导出G的最短圈},其中w（X）为端点分别在X和V（G）-X中的边的数目.如果一个圈边可分离图G使得cλ（G）=ζ（G）成立,称该图是圈边最优的.Tian和Meng在文章[11]以及Yang et al在文章[15]中研究了两种不同的双轨道图的圈边最优性.本文我们将研究具有两个同阶轨道的双轨道图的圈边连通度.     

图的局部k限制边连通性及最优性

首先研究图的局部k限制边连通性问题和局部λ_k-连通图的存在性问题.然后研究图的局部λ_k最优性,并且应用邻域条件得到了一个保证图局部λ_k最优的充分条件.     

方差分量模型中回归系数的线性Minimax估计

考虑方差分量(混合线性)模型y=Xβ+U1ξ1+U2ξ2+…+Ukξk,这里Xn×p,Ui,n×ti为已知设计矩阵,βp×1是固定效应,iξ是ti×1随机效应向量,满足E(iξ)=0,cov(iξ)=σ2iIti,iξ都不相关.往往Uk=In,ξk=ek,即最后一项为随机误差,热β∈RP和i2σ>0(i=1,2,…,k)为未知参数.我们考虑β的可估函数Sβ,选取二次损失函数L(d,Sβ)=(d-Sβ)′(d-Sβ)∑ki=1ciσi2+β′X′Vk-1Xβ,然后在线性估计类中给出Sβ的惟一的mini max估计.     

完全可控线性系统的谱分布

<正> 其中x(·)∈R_n,u(·)∈R_r,A,B分别为n×n,n×r阶复常数阵,R_n,R_r分别为n,r维酉空间,有如下熟知结果:任给n个复数λ_1,…,λ_n,恒存在r×n阶复数阵C,使阵的谱集σ(A+BC)={λ_1,…,λ_n}的充要条件为     

The Rainbow Vertex-disconnection in Graphs

Let G be a nontrivial connected and vertex-colored graph. A subset X of the vertex set of G is called rainbow if any two vertices in X have distinct colors. The graph G is called rainbow vertex-disconnected if for any two vertices x and y of G, there exists a vertex subset S of G such that when x and y are nonadjacent, S is rainbow and x and y belong to different components of G-S; whereas when x and y are adjacent, S + x or S + y is rainbow and x and y belong to different components of(G-xy)-S. For a connected graph G, the rainbow vertex-disconnection number of G, denoted by rvd(G), is the minimum number of colors that are needed to make G rainbow vertexdisconnected. In this paper, we characterize all graphs of order n with rainbow vertex-disconnection number k for k ∈ {1, 2, n}, and determine the rainbow vertex-disconnection numbers of some special graphs. Moreover, we study the extremal problems on the number of edges of a connected graph G with order n and rvd(G) = k for given integers k and n with 1 ≤ k ≤ n.     

图 P2×Cn的均匀邻强边色数

对图G(V,E),一正常边染色f若满足(1)对(V)uv∈E(G),f[u]≠f[v],其中f[u]={f(uv)|uv∈E};(2)对任意i≠j,有||E|-|Ej||≤1,其中Ei={e| e∈E(G)且f(e)=i}.则称f为G(V,E)的一k-均匀邻强边染色,简称k-EASC,并且称Xcas(G)=min{k|存在G(V,E)的一k-EASC为G(V,E)的均匀邻强边色数.本文得到了图P2×Cn的均匀邻强边色数.     

关于图P_n~k的均匀染色

对简单图G=〈V,E〉及自然数k,令V(Gk) =V(G) ,E(Gk) =E(G)∪{uv|d(u,v) =k},其中d(u,v)表示G中u,v的距离,称图Gk为G的k方图.本文讨论了路的k方图Pkn的均匀点染色、均匀边染色和均匀邻强边染色,利用图的色数的基本性质和构造染色函数的方法,得到相应的色数χev(Pkn) ,χ′ee(Pkn) ,χ′eas(Pkn) .并证明猜想“若图G有m -EASC,则一定有m +1 -EASC”对Pkn是正确的.     

二分图中含有完美对集的2因子

该文证明若G是2n阶均衡二分图，δ(G)≥(2n-1)/3，则对任何正整数k，n≥4k时，任给G的一个完美对集M，G中存在一个包含M的所有边的恰含k个分支的2 因子(k=1，n=5且δ(G)=3除外）. 特别k=2时，在条件n≥5且δ(G)≥(n+2)/2下，结论也成立. 这里所给的δ(G)的下界是最好的可能. 