可迁图的超常边连通度的最优性

图的超常边连通度是图的边连通度概念的推广.对于n阶点可迁或正则边可迁的简单连通图来说,它的h阶超常边连通度λh一定存在(1≤h≤n/2).本文证明了当dr正则的n-阶点可迁简单连通图满足n≥6,d≥4且围长g≥5时,或d-正则的n-阶边可迁简单连通图满足n≥6,d≥4且围长g≥4时,对于任何的h1≤h≤min{g-1,n/2},λh达到其最大可能值,即λh=hd-2(h-1).     

点可迁图的限制边连通度

设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.     

可迁图的超常边连通度的最优性

图的超常边连通度是图的边连通度概念的推广,对于n阶点可迁或正则边可迁的简单连通图来说,它的h阶超常边连通度λ_h一定存在(1≤h≤n/2)。本文证明了:当d_-正则的n_-阶点可迁简单连通图满足n≥6,d≥4且围长g≥5时,或d_-正则的n_-阶边可迁简单连通图满足n≥6,d≥4且围长g≥4时,对于任何的h:1≤h≤min{g-1,n/2},λ_h达到其最大可能值,即λ_h=hd-2(h-1)。     

关于Mbius立方体网格的连通度(英文)

图的连通度、超连通性和限制连通度是度量互连网络容错性的重要参数 .该文考虑n维M bius立方体网络MQn,证明了它的点和边连通度都为n ,当n是任何正整数时它是超连通的 ,当n≠ 2时它是超边连通的 ,当n≥ 3时它的限制点连通度和当n≥ 2时的限制边连通度都为 2n- 2 .     

给定边连通度的图的最小距离谱半径(英文)

本文研究了边连通度为r的n阶连通图中距离谱半径最小的极图问题,利用组合的方法,确定了K(n-1,r)为唯一的极图,其中K(n-1,r)是由完全图K_(n-1)添加一个顶点v以及连接v与K_(n-1)中r个顶点的边所构成.上述结论推广了极图理论中的相关结果.     

含有给定k-正则子图的[a,b]-因子

设G是一个图,并设n,k,r,a和b是整数且满足k≥1,k≤a＜b和n≥3.对于G的给定的k-正则图H,如果G是K1,n-free图,且G的最小度至少是((n(a+1)+b-a-(k+1))/(b-k))「(ab+b-a-k)/(2(n-1))」-(n-1)/(b-k)(「(an+b-a-k)/(2(n-1))」)2-1,那么G有一个[a,b]-因子F使得E(H)(∈)E(F).类似地,也得到了关于图G有一个r-因子含有G中给定的k-正则子图的度条件.进一步,指出这些度条件是最佳的.     

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

图的限制边连通度是经典边连通度的推广,可用于精确度量网络的容错性.极大限制边连通图是使限制边连通度达到最优的一类图.首先将图的限制边连通度和最小边度的概念推广到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的一致线性超图是极大限制边连通的.所得结论是图中相关结果的推广.     

二项式系数奇偶性的判定准则

判定准则Cnm(m≤n)的奇偶性取决于m和n-m的二进制表达式中是否存在位于同一数位上的两个数码都是1,如果存在,Cmn是偶数,否则Cnm就是奇数.证m=0时,Cnm=C0n=1总是奇数,判定准则显然成立.m=1时,Cnm=C1n=n,若n是奇数,则n-m=n-1是偶数,其二进制表达式的末位是0;若n是偶数,则n-m=n-1是奇数,其二进制表达式的末位是1,判定准则亦成立.可见,m=0或1时,判定准则对任意正整数n都成立.由于Cnm=Cnn-m,因此下面只需在m≥2且n-m≥2的前提下证明判定准则.以下对n使用数学归纳法证明判定准则.n=1时,m=0或1,前面已经证明判定准则成立.假设判定准则对n-1(≥1…     

一些图的拟拉普拉斯能量和基尔霍夫指标（英文）

G是具有拉普拉斯特征值μ1≥μ2≥···≥μn=0的的n阶连通图.G的拟拉普拉斯能量和基尔霍夫指标分别定义为LEL=∑n-1i=1√μi和Kf=n∑n-1i=11/μi.本文研究半正则图的线图及正则图细分图的线图,给出这两类图的拟拉普拉斯能量和基尔霍夫指标的界,同时获得它们的基尔霍夫指标公式.     

Bubble-sort网络的连通度和超连通度

Bubble-sort网络Bn是(n-1)-正则,点传递的二部图.在这篇文章中,我们确定了当n≥2时,Bn的(边)-连通度为n-1;当n≥3时,Bn的超(边)-连通度为2n-4.     

Orientations of infinite graphs with prescribed edge-connectivity

We prove a decomposition result for locally finite graphs which can be used to extend results on edge-connectivity from finite to infinite graphs. It implies that every 4k-edge-connected graph G contains an immersion of some finite 2k-edge-connected Eulerian graph containing any prescribed vertex set (while planar graphs show that G need not containa subdivision of a simple finite graph of large edge-connectivity). Also, every 8k-edge connected infinite graph has a k-arc-connected orientation, as conjectured in 1989.     

Upper bound of the third edge-connectivity of graphs

Let G be a simple connected graph of order n≥6. The third edge-connectivity of G is defined as the minimum cardinality over all the sets of edges, if any, whose deletion disconnects G and every component of the resulting graph has at least 3 vertices. In this paper, we first characterize those graphs whose third-edge connectivity is well defined, then establish the tight upper bound for the third edge-connectivity.     

On the edge-connectivity of graphs with two orbits of the same size

It is well known that the edge-connectivity of a simple, connected, vertex-transitive graph attains its regular degree. It is then natural to consider the relationship between the graph’s edge-connectivity and the number of orbits of its automorphism group. In this paper, we discuss the edge connectedness of graphs with two orbits of the same size, and characterize when these double-orbit graphs are maximally edge connected and super-edge-connected. We also obtain a sufficient condition for some double-orbit graphs to be λ^′-optimal. Furthermore, by applying our results we obtain some results on vertex/edge-transitive bipartite graphs, mixed Cayley graphs and half vertex-transitive graphs.     

On restricted edge-connectivity of replacement product graphs

This paper considers the edge-connectivity and the restricted edge-connectivity of replacement product graphs, gives some bounds on edge-connectivity and restricted edge-connectivity of replacement product graphs and determines the exact values for some special graphs. In particular, the authors further confirm that under certain conditions, the replacement product of two Cayley graphs is also a Cayley graph, and give a necessary and sufficient condition for such Cayley graphs to have maximum restricted edge-connectivity. Based on these results, we construct a Cayley graph with degree d whose restricted edge-connectivity is equal to d + s for given odd integer d and integer s with d 5 and 1 s d- 3, which answers a problem proposed ten years ago.     

Non-zero component union graph of a finite-dimensional vector space

In this paper, we introduce a graph structure, called non-zero component union graph on finite-dimensional vector spaces. We show that the graph is connected and find its domination number, clique number and chromatic number. It is shown that two non-zero component union graphs are isomorphic if and only if the base vector spaces are isomorphic. In case of finite fields, we study the edge-connectivity and condition under which the graph is Eulerian. Moreover, we provide a lower bound for the independence number of the graph. Finally, we come up with a structural characterization of non-zero component union graph.     

Super restricted edge connectivity of regular graphs with two orbits

It is well known that the edge-connectivity of a simple, connected, vertex transitive graph attains its regular degree. It is then natural to consider the relationship between the graph’s edge connectivity and the number of orbits of its automorphism group. In [6], Liu and Meng (2008) studied the edge connectivity of regular double-orbits graphs. Later, Lin et al. (in press) [10] characterized the λ′-optimal 3-regular double-orbit graph and given a sufficient condition for the k-regular double-orbit graphs to be optimal. In this note, we characterize the super restricted edge connected k-regular double-orbit graphs with grith at least 6.     

On defect-d matchings in graphs

A defect-d matching in a graph G is a matching which covers all but d vertices of G. G is d-covered if each edge of G belongs to a defect-d matching. Here we characterise d-covered graphs and d-covered connected bipartite graphs. We show that a regular graph G of degree r which is (r ? 1)-edge-connected is 0-covered or 1-covered depending on whether G has an even or odd number of vertices, but, given any non-negative integers r and d, there exists a graph regular of degree r with connectivity and edge-connectivity r ? 2 which does not even have a defect-d matching. Finally, we prove that a vertex-transitive graph is 0-covered or 1-covered depending on whether it has an even or odd number of vertices.     

Forcing matching numbers of fullerene graphs

The forcing number or the degree of freedom of a perfect matching M of a graph G is the cardinality of the smallest subset of M that is contained in no other perfect matchings of G. In this paper we show that the forcing numbers of perfect matchings in a fullerene graph are not less than 3 by applying the 2-extendability and cyclic edge-connectivity 5 of fullerene graphs obtained recently, and Kotzig’s classical result about unique perfect matching as well. This lower bound can be achieved by infinitely many fullerene graphs.     

SUPER EDGE-CONNECTIVITY OF DE BRUIJN AND KAUTZ UNDIRECTED GRAPHS

The super edge-connectivity of a graph is an important parameter to measure fault-tolerance of interconnection networks. This note shows that the Kautz undirected graph is super edge-connected,and provides a short proof of Lue and Zhang‘s result on super edge-connectivity of the de Bruijn undirected graph.