On Graphs with Equal Connected Domination and 2-connected Domination Numbers

A subset S of V is called a k-connected dominating set if S is a dominating set and the induced subgraph S has at most k components.The k-connected domination number γck（G） of G is the minimum cardinality taken over all minimal k-connected dominating sets of G.In this paper,we characterize trees and unicyclic graphs with equal connected domination and 2-connected domination numbers.

补图为2-点或2-边连通的图的最小特征值(英文)

图的最小特征值定义为图的邻接矩阵的最小特征值,是刻画图结构性质的一个重要代数参数.在所有给定阶数的补图为2-点或2-边连通的图中,刻画了最小特征值达到极小的唯一图,并给出了这类图最小特征值的下界.

直径为2的图的超级边连通性质

Ｍ．Ａ．Ｆｉｏｌ在１９９２年给出了直径为２的无向简单图是超级边连通的三个充分条件（Ｆ１）、（Ｆ２）和（Ｆ３）．本文证明了：（１）条件（Ｆ１）也是必要条件，从而得到直径为２的图是超级边连通图的特征刻画；（２）（Ｆ３）（Ｆ２）（Ｆ１），但（Ｆ１）／（Ｆ２）／（Ｆ３）；（３）条件（Ｆ３）可进一步保证图是最优超级边连通的，但（Ｆ２）不能．这里的最优超级边连通的概念是通过限制性边连通度自然地定义的．最后提出两个有关的待解决的问题．

2-连通2-支配集的集中式构造

在无线传感器网络中,通常采用连通支配集来构成一个虚拟骨干网进行分层路由,对重要的目标或环境需要构造容错性高,可靠性好的虚拟骨干网。提出构造网络2-连通2-支配集的两种集中式算法,分别是先回路后支配和先支配后回路。前一种算法是先形成一个由支配点组成的回路,然后以此回路为基础不断地扩充此回路,直到不在回路中的节点为2-被支配为止;后一种算法是首先保证每个非支配点都要变成2-被支配点,然后再使图中所有支配点构成回路。

无线传感器网络中d-Hop 2-连通容错支配集的分布式构造算法

无线传感器网络随节点移动组成自我维持的自组织系统,采用连通支配集的虚拟骨干技术可使平面网络系统层次化而简化节点路由、管理和维护。但大规模无线传感器网络的连通支配集节点数目依然庞大,d-hop连通支配集可以大大减小支配集节点数目。另外,由于存在节点失效、链路断裂等无线特性,虚拟骨干网需要具备一定的容错性。在单位圆盘图网络模型中为构建精简且具有容错能力的虚拟骨干网,提出d-hop 2-连通支配集的分布式构造算法,先构造d-hop独立支配集后再连通形成d-hop 2-连通支配集。并从理论和仿真上对算法的复杂度、近似比和算法性能作了进一步探讨和验证。

连通、N_2-局部连通、K_(1,4)-受限图的哈密顿性

证明如下结论 :设G是连通、N2 -局部连通、δ≥ 6的K1 ,4 -受限图 ,如果G中不含有同构于G1 ,G2 或G3的导出子图H ,则G含哈密顿圈 .

关于几乎正则2-连通图的Hamilton性的注记

研究几乎正则图的Hamilton性,得到了定理1 设G是2连通的(k,k+1)图,并且k≥V(G)3+13,如果G是偶数阶的图,则G是Hamilton图.定理2 设G是(k,k+2)图,并且k≥n3+103,如果存在G的一个非空独立集B1,使得B1≥n3-133,而且对于G的所有独立集B,都有B≤n2-1,则G是Hamilton图.

2-连通外平面图的邻点可区别全染色

运用数学归纳法及换色技巧,探讨了Δ(G)=7的2-连通外平面图的邻点可区别全染色问题,使该问题在原有基础上得到了推广.

k正则的2.■_(1.3)图的周长

设G为k正则的2连通的不含K_(1.3)的图,则(ⅰ) c(G)≥min{|V(G)|,4k-2},且是最好可能的;(ⅱ)当|V(G)|≤5k-3时,G是哈密顿的。

2连通的k正则偶图的周长

本文证明2连通的k正则偶图G的周长至少为min{|V(G)|,4k+2},且是最好可能的。

泛连通图定理和Ore_2条件

记 Ore2 =min{ d(y) +d(x) |x,y∈ V(G) ,d(x,y) =2 } ,本文得到 :若 n阶图 G的 Ore2≥ n+1 ,则 G是 [5;n]泛连通图 .此是比 Faudree等人的定理进一步的结果 .

非基本最短欧几里德2-连通Steiner网络的几个性质

欧几里德2-连通Steiner网络问题是组合优化中的著名问题,在水、电供应网络等的设计中有非常广泛的应用.以块图为工具,证明了非基本最短欧几里德2-连通Steiner网络的一些结构性质.

(K_(1,4);2)-图的闭包和路长

为了推广无爪图G在闭包运算下是唯一确定的并且保持路长不变这一结论,对包含无爪图的(K_(1,4);2)-图进行研究,主要采用逐一讨论、排除的方法对此类图的路长在闭包运算下保持不变的性质进行证明。结果表明:在已知K_1∨P_4-free或T_3-free的(K_(1,4);2)-图在闭包运算下也唯一确定并且仍为(K_(1,4);2)-图的条件下,如果G是K_1∨P_4-free或T_3-free的(K_(1,4);2)-图,则在闭包的运算下保持路长不变;K1∨P4-free或T3-free的(K_(1,4);2)-图G可迹当且仅当其闭包是可迹的,其中K_1∨P_4为一个点与长为4的路的联图,T_3为K_(1,3)与K_2的并图。

一类极大临界2连通图的结构

引入图的粘合的概念,讨论了极大临界2连通图G的性质,给出了一个图是这类图的一个充要条件,由此给出该类图的一种新的构造方法,即G能按条件先粘合一系阶大于2的完全图的边,然后粘合四圈C4的t个拷贝得到.

关于非广义多边形路的2连通简单MCD图

令 Sn 是具有 n个顶点没有两个等长圈的简单图的集合 .若 Sn 中不存在图 G′使|E(G′) |>|E(G) |,则称图 G是简单 MCD图 .若简单 MCD图 G是 2连通的 ,则称 G是 2连通简单 MCD图 .若 G中一条路 P的每个内点 v都有 d G(v) =2 ,则称 P为 G的简单路 .一个 2连通可平面图 G称为广义多边形路 ,如果用下述方法得到图 G*是路 :对应于 G的每个内部面 f (G是G的平图 )有一个 G*的顶点 f * ,G*的两个顶点 f*和 g*在 G*中相邻当且仅当 G中相应的两个内部面的边界交于一条 G的简单路 .作者证明了下述结果 :当且仅当 n∈ {1 0 ,1 1 ,1 4,1 5,1 6,2 1 ,2 2 }时 ,存在 n个顶点的非广义多边形路的 2连通简单 MCD图 .

一个关于2─连通图周长的次条件

设Ｇ为ｎ阶２－连通图，顶点ｖ１，ｖ２，…，ｖｎ满足ｄ１≤ｄ２≤…≤ｄｎ，其中ｄｉ＝ｄ（ｖｉ），ｉ＝１，２，…，ｎ。给出ｃ（Ｇ）≥ｍｉｎ｛ｎ，ｍ｝的如下条件：

一类2-连通图的控制圈的圈长

在有限无向简单图中,引进控制圈的定义,得到了一类2-连通图的控制圈的圈长至少为2σ-2,在一定的条件下改进了田丰等人证明的控制圈的圈长至少为2σ-3的结果.

2－连通简单MCD图边数的一个新的下界

设Ｇ是具有ｎ个顶点的２－连通简单ＭＣＤ图，ｆ２（ｎ）表示Ｇ的边数．本文证明了当ｎ≥８时，其中ｘｍ＝ｕｍ－２ｕｍ－５，ｕｍ是Ｆｉｂｏｎａｃｃｉ数．

2─连通图中X─最长圈下界估计(英文)

给一个图Ｇ，ＸＶ（Ｇ），Ｇ［Ｘ］为Ｇ的Ｘ生成子图，ｒ为正整数。定义α（Ｘ）＝ｍａｘ｛｜Ｓ｜｝Ｓ是Ｇ［Ｘ］的顶点独立集｝，αｋ（Ｘ）＝ｍｉｎ｛∑ｄ（ｖｉ）｜｛ｖ１，ｖ２，…，ｖｋ｝是Ｇ［Ｘ］的顶点独立集｝，ＮＣｋ（Ｘ）＝ｍｉｎ｛｜Ｕｋｉ＝１；Ｎ（ｖｉ）｜（ｖ１，…，ｖｋ是Ｇ［ｘ］的独点独立集｝（ｋ≥２）．我们得到结论；对—任意的ｎ阶２─连通图Ｇ（ｎ≥３），ｘＧ，且σ３（Ｘ）≥ｎ＋ｒ≥ｎ＋２，则存在一个包含Ｘ的顶点数为ｍｉｎ｛｜Ｘ｜，｜Ｘ｜＋ＮＣｒ＋２＋ｅ（ｎ＋ｒ）（Ｘ）－α（Ｘ）｝的圈，ε（ｉ）＝３（ｉ）ｉ．该结论推广了Ｈ．Ｊ．Ｂｒｏｅｒｓｍａ在文献［１］中的结果．

2-连通图的一些等价定义

通过从不同角度深入理解并挖掘2-连通图的本质特征,给出了多种关于2-连通图的等价性命题.从最长圈及收缩点对等方面出发,提出了新的有关2-连通图的命题,并证明了其相互间的等价性.