3限制边连通度与正则因子

设G是一个阶不小于6的k正则连通点可迁图. 如果G不含三角形, 那么图G是极大3限制边连通的, 或者G含有各连通分支都同构于同一个h阶点可迁图的k-1正则因子, 其中2k-2≤h≤3k-5. 唯一的例外是: G是围长等于4 的3正则图.     

围长为3的点可迁图的3限制边连通度

设G是阶至少为6的k正则连通图.如果G的围长等于3,那么它的3限制边连通度 λ3(G)≤3k-6.当G是3或者4正则连通点可迁图时等号成立,除非G是4正则图并且 λ3(G)=4.进一步,λ3(G)=4的充分必要条件是图G含有子图K4.     

点可迁图的限制边连通度

设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的k元点集X={x1,x2,…,xk}被称为G的k-可序子集,如果X的任意排列都按序排在G的某个圈上.称G是k-可序图,如果G的每一个k元子集都是G的k-可序子集.称G为k-可序Hamilton图,如果X的任意排列都位于G的Hamilton圈上.研究了3-连通3-正则图的可序子集的存在性问题.     

关于分数k-因子临界图与分数k-可扩图的若干结果

一个简单图G, 如果对于V(G)的任意k元子集S, 子图G-S都包含分数完美匹配, 那么称G为分数k-因子临界图. 如果图G的每个k-匹配M都包含在一个分数完美匹配中, 那么称图G为分数k-可扩图. 给出一个图是分数k-因子临界图和分数k-可扩图的充分条件, 并给出一个图是分数k-因子临界图的充分必要条件.     

点可迁图的限制边连通性

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

具有唯一K_k- 因子的最大图

这里考虑的是简单图.图 G 的 K_k-因子是 G 的这样一种支撑子图,它的每个连通片皆同构于 k 个节点的完全图 K_k.本文给出:如果 G 具有唯一的 K_k-因子,则|E(G)|≤n~2·k(k-1)/2;进而,对于|E(G)|=n~2·k(k-1)/2的图 G 完全确定了 G 的结构.     

关于图的星形因子覆盖

如果图 G 的支撑子图 M 的每个分支都同构于{K_(1,1)K_(1,2,)…,K_(1,k}(k≥2)中的某个 K_(1,i),则 M(?)叫做 G 的星形因子。进一步,如果对于图 G 的每一条边都存在一个星形因子包含这条边,则称图 G 是星形因子覆盖的。本文给出了图是{P_2,P_3}一因子覆盖的充要条件,并证明了任意正则图均存在星形因子覆盖。     

含有给定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-正则子图的度条件.进一步,指出这些度条件是最佳的.     

奇图的匹配可扩性

设G是一个图,n,k和d是三个非负整数,满足n+2k+d≤|V(G)|-2,|V(G)|和n+d有相同的奇偶性.如果删去G中任意n个点后所得的图有k-匹配,并且任一k-匹配都可以扩充为一个亏d-匹配,那么称G是一个(n,k,d)-图.Liu和Yu[1]首先引入了(n,k,d)-图的概念,并且给出了(n,k,d)-图的一个刻划和若干性质. (0,k,1)-图也称为几乎k-可扩图.在本文中,作者改进了(n,k,d)-图的刻划,并给出了几乎k-可扩图和几乎k-可扩二部图的刻划,进而研究了几乎k-可扩图与n-因子临界图之间的关系.     

一类Y~(SG)(γλ,n)∪βS_n~G形图簇的伴随分解及其补图的色等价性

设G是m阶连同图,我们用S_n~G(n=km+1)表示把kG的每个分支的d_i度点分别与星图S_k+1的k个1度点重迭后得到的图,Y~(SG)(r_1n,n)表示把r_1S_n~G中每个分支的k度点依次与图的k度点邻接后得到的图,Y~(SG)(r_2λ_1,n)表示把τ_2Y~(SG)(τ_1n,n)中每个分支的r_1+k度点依次与图S_n~G的k度点邻接后得到的图,若k≥3,用Y~(sG)(r_kλ__(k-1),n)表示把τ_kY~(sG)(r_(k-1)λ_(k-2),n)中每个分支的τ_(k-1)+k度顶点依次与图S_n~G的k度点邻接后得到的图,这里λ_k=r_kλ_(k-1)+n.运用图的伴随多项式的性质,证明了一类新的图簇Y~(sG)(r_kλ__(k-1),n)∪β_kS_n~G的伴随多项式的因式分解定理,进而得到了这类图的补图的色等价图.     

Super-Connectivity and Hyper-Connectivity of Vertex Transitive Bipartite Graphs

A graph is said to be super-connected if every minimum vertex cut isolates a vertex. A graph is said to be hyper-connected if the deletion of each minimum vertex cut creates exactly two components, one of which is an isolated vertex. In this note, we proved that a vertex transitive bipartite graph is not super-connected if and only if it is isomorphic to the lexicographic product of a cycle C_n(n ≥ 6) by a null graph N_m. We also characterized non-hyper-connected vertex transitive bipartite graphs.     

图的伴随多项式的两个因式分解定理及其应用

设G是m阶连通图,P_m是m个顶点的路.令S_km+1^G(i)表示把kG的每一个分支的第i(1≤i≤m)个顶点依次与星图S_k+1的k个1度顶点重迭后得到的图;令G_i1^S*(q,km)表示q阶图G的顶点V_i1与S_km+1^p(1)的k度顶点重迭后得到的图     

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.     

上连通和超连通三次点传递图(英)

图G称为上连通的,若对每个最小割集C,G-C有孤立点.G称为超连通的,若对每个最小割集G,G-C恰有两个连通分支,且其中之一为孤立点.本文刻划了上连通和超连通三次点传递图.     

上连通和超连通三次点传递图

图G称为上连通的,若对每个最小割集C,G-C有孤立点,G称为超连通的,若对每个最小割集C,G-C恰有两个连通分支,且其中之一为弧立点,本文刻划了上连通和超连通三次点传递图。     

3‐Factor‐Criticality of Vertex‐Transitive Graphs

A graph of order n is p ‐factor‐critical, where p is an integer of the same parity as n, if the removal of any set of p vertices results in a graph with a perfect matching. 1‐factor‐critical graphs and 2‐factor‐critical graphs are factor‐critical graphs and bicritical graphs, respectively. It is well known that every connected vertex‐transitive graph of odd order is factor‐critical and every connected nonbipartite vertex‐transitive graph of even order is bicritical. In this article, we show that a simple connected vertex‐transitive graph of odd order at least five is 3‐factor‐critical if and only if it is not a cycle.     

3-γ-临界图G中关于i(G)=γ(G)的一个充分条件

如果图G满足γ（G）＝k且对图G中任两个相邻的点x,y有γ（G＋xy)=k-1,则称图G为k-γ-临界图,如果图G满足γ（G）＝k且对图G中任何距离为d的两点x,y有γ（G＋xy)=k-1,则称图G为k-(γ,d)－临界图。Sumner和Blitch猜想在3－γ－临界图中有γ（G）＝i(G).Oellermann和Swart猜想3－（γ,2）－临界图中有γ（G）＝i(G),这篇文章中我们提出3－γ－临界图中使γ（G）＝i(G)的一个充分条件。