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

图的超常边连通度是图的边连通度概念的推广.对于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.     

点可迁图的限制边连通度

设Ｓ是连通图Ｇ的边子集．如果Ｇ－Ｓ不连通而且不含孤立点,那么称Ｓ是Ｇ的一个限制边割,Ｇ中所有限制边割中最小边数称为Ｇ的限制边连通度,记为λ＇（Ｇ）．限制边连通度是对传统边连通度的推广,而且是计算机互连网络容错性的一个重要度量．点可迁图是一类重要的网络模型．本文证明了如下结论： 设 Ｇ是连通的点可迁图．如果 Ｇ的点数ｎ≥ ４,而且点度ｋ≥ ２,那么或者λ＇（Ｇ）＝ ２ｋ－２,或者ｎ是偶数,Ｇ含三角形且存在整数ｍ≥２,使得ｋ≥λ＇（Ｇ）＝ｎ／ｍ≤２ｋ－３．关     

点可迁图的限制边连通性

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

正则图的限制性边连通度

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

极小Cayley图的限制性边连通度

一个连通图X的边集的一个子集C称为一个限制性边割,如果它是一个边割,且X／C不含孤立点。X的限制性边连通度λ′（X）定义为所有限制性边割的最小基数。本文完全决定了极小Cayley图的限制性边连通度。     

2n-正则简单图的边连通度

图的各种连通度概念被先后用来研究网络可靠性问题.对于0到2n之间的任意一个偶数2m,构造了一个2n-正则简单图,使得其边连通度的值为2m.从而得到:2n-正则简单图的边连通度能够取{0,2,4,…,2n}中的任何一个偶数.     

连通的顶点可迁图的色唯一性

本文给出从一个已知的顶点可迁的非色唯一图出发,构造无穷多个顶点可迁的非色唯一图的一种方法,据此给出若干类无穷多个连通的顶点可迁,但不是色唯一的图簇,从而进一步否定地回答了Chia在[1]中提出的问题.     

拟顶点可迁图上简单随机游走的切割点

证明了体积增长不低于5次多项式的拟顶点可迁图上的简单随机游走几乎处处有无穷多个切割时,从而有无穷多个切割点.该结论在所论情形下肯定了Benjamini,Gurel-Gurevich和Schramm在文[2011,Cutpoints and resistance of random walk paths,Ann.Probab.,39(3):1122-1136]中提出的猜想:顶点可迁图上暂留简单随机游走几乎处处有无穷多个切割点.     

一类无向Kautz图的k限制边连通度的上界

在Moor-Shannon网络模型中,k限制边连通度较大的网络一般有较好的可靠性和容错性.本文在无向Kautz图UK(2,n)中研究k限制边连通度的上界ξk,证明了ξ5(UK(2,3))=6,ξ5(UK(2,n))=8,n≥4,且当4≤k≤n时,ξk(UK(2,n))≤2(k-「k/3」).     

Distance-residual subgraphs

For a connected finite graph G and a subset V₀ of its vertex set, a distance-residual subgraph is a subgraph induced on the set of vertices at the maximal distance from V₀. Some properties and examples of distance-residual subgraphs of vertex-transitive, edge-transitive, bipartite and semisymmetric graphs are presented. The relations between the distance-residual subgraphs of product graphs and their factors are explored.     

On cyclic edge-connectivity of transitive graphs

A cyclic edge-cut of a graph G is an edge set, the removal of which separates two cycles. If G has a cyclic edge-cut, then it is said to be cyclically separable. For a cyclically separable graph G, the cyclic edge-connectivity cλ(G) is the cardinality of a minimum cyclic edge-cut of G. In this paper, we first prove that for any cyclically separable graph G, , where ω(X) is the number of edges with one end in X and the other end in V(G)?X. A cyclically separable graph G with cλ(G)=ζ(G) is said to be cyclically optimal. The main results in this paper are: any connected k-regular vertex-transitive graph with k≥4 and girth at least 5 is cyclically optimal; any connected edge-transitive graph with minimum degree at least 4 and order at least 6 is cyclically optimal.     

关于图的子着色

本文主要讨论了子色唯一图的结构，并给出了唯一k-子色图、最大子色图的边临界子色图的特征．     

完全图与完全n部图的完全多部图分解

§ 1　IntroductionLet V(G) and E(G) be the vertex setand the edge setof a graph G,respectively.Fori=1 ,...,p,if V(Gi) V(G) ,E(Gi)∩ E(Gj) = for i≠ j,and∪pi=1 E(Gi) =E(G) ,then wecall{ G1 ,...,GP} a decomposition of G.Let[i,j] be the integer interval including i and j.Let Knbe a complete graph with the vertex set[1 ,n] .For m disjointsubsets A1 ,...Amof[1 ,n] ,let K(A1 ,...,Am) be a complete m-partite graph having partite-sets A1 ,...,Am.If| Ai| =1 ,Ai is called a S-set;otherwi…     

Mycielski图的循环色数

通过引入一类点集划分的概念,研究了Mylielski图循环染色的性质,证明了当完全图的点数足够大时,它的Mycielski图的循环色数与其点色数相等.     

PROPERTIES OF FRACTIONAL κ-FACTORS OF GRAPHS

In this paper the properties of some maximum fractional [0, κ]-factors of graphs are presented. And consequently some results on fractional matchings and fractional 1-factors are generalized and a characterization of fractional κ-factors is obtained.     

A note on vertex-transitive non-Cayley graphs from Cayley graphs generated by involutions

We show that the result of Watkins (1990) [19] on constructing vertex-transitive non-Cayley graphs from line graphs yields a simple method that produces infinite families of vertex-transitive non-Cayley graphs from Cayley graphs generated by involutions. We also prove that the graphs arising this way are hamiltonian provided that their valency is at least six.