极大非独立集可削去的因子临界图(英文)

如果对一个简单图G的每一个与G的顶点数同奇偶的独立集1,都有G-I有完美匹配,则称G是独立集可削去的因子临界图.如果图G不是独立集可削去的因子临界图,而对任意两个不相邻的顶点x与y,G+zy是独立集可削去的因子临界图,则称G是极大非独赢集可削去的因子临界图.本文刻画了极大非独立集可削去的因子临界图.

独立集可削去因子临界图和无爪的独立集可削去因子临界图的度条件

研究了不含开邻集是独立集或空集的小团(奇数个顶点)的独立集可削去因子临界图以及无爪的独立集可削去因子临界图的度条件.

分数ID-[a,b]-因子临界图的最小度与独立数条件(英文)

对图G的每个独立集I,若G-I有分数[a,b]-因子,则G是分数ID-[a,b]-因子临界图.本文证明了若α(G)≤(4b(δ(G)-b+1))/((a+1)2+4b),则G是分数ID-[a,b]-因子临界图.

ID-临界因子图的度和条件(英文)

本文研究ID-因子临界图的度和条件,得到使得图G是ID-因子临界图的任意两个不相邻的顶点的度和的下界,同时说明这些结果是最好可能的。

偶图中独立边集的1－因子扩张

Ｇ＝（Ａ，Ｂ；Ｅ）是偶图，｜Ａ｜＝｜Ｂ｜＝≥２，若ｅ，ｆ∈Ｅ，ｅ≠ｆ，有ｄ（ｅ）＋ｄ（ｆ）≥３ｎ＋ｋ（ｋ≥１），则Ｇ中所有ｋ个边的独立集Ｍ皆可扩张成Ｇ的１－因子．

边色临界图的1-因子和几乎1-因子的存在性

根据Vizing邻接引理和关于临界图的独立数的一个结论,利用图的1-因子和几乎1-因子存在的充要条件,采用结构图论的方法证明了:1)若G是2n阶Δ-临界图,且Δ≥n,δ≥n-2,则G存在1-因子;2)若G是2n+1阶Δ-临界图,且Δ≥n+1,δ≥n-2,则G存在几乎1-因子.

独立集可去的分数(k,m)-消去图的最小度条件

图G称为分数(k,m)-消去图,若从G中删除任意m条边的剩余子图依然存在分数k-因子.称G是一个独立集可去的分数(k,m)-消去图,如果对G中任意独立集I,G-I是分数(k,m)-消去图.本文给出独立集可去的分数(k,m)-消去图的最小度条件,并说明结论是最好的.

关于f因子的最小度与独立集条件的注记

讨论无ｆ＿ 因子图的结构性质及已知的保证图有ｆ＿因子的最小度与独立集条件之间的关系．

随机图中k-独立集的相变性质

相变性质是ER(Erdos-Renyi)随机图理论具有的重要性质,一个简单无向图G=(V,E)中的k-独立集是一个具有k个顶点的独立集.为更好地理解ER随机图中是一独立集的结构特性,提出并利用一阶矩和二阶矩方法严格证明了当2≤k=o(n^(1/2))时随机图G(n,p)中k-独立集出现相变的临界概率p_c=1-n^(-2/(k-1)).利用m≈pC_n^2时随机图G(n,p)和G(n,m)等价的性质给出了随机图G(n,m)中k-独立集出现相变的临界边数m_c=[((n(n-1))/2)(1-n^(-2/(k-1)))].实验结果表明:当2≤k=o(n^(1/2))时,随机图G(n,p)和G(n,m)中存在k-独立集的理论临界值和仿真得到的临界值一致且临界值与图节点总数n和独立集节点数k有关,而当k=ω(n^(1/2))时,随机图G(n,p)和G(n,m)中存在k-独立集的理论临界值和仿真临界值不一致.

关于独立集可去的分数(k,m)-消去图的度和条件的注记

图G称为分数(k,m)-消去图,若从G中删除任意m条边的剩余子图依然存在分数k-因子.称G是一个独立集可去的分数(k,m)-消去图,如果对G中任意独立集I,G-I是分数(k,m)-消去图.本文给出独立集可去的分数(k,m)-消去图的度和条件,并讨论了所得结论的最优性.

3正则的ID-因子临界图

如果对于G中任意和V|(G)|有相同奇偶性的独立集I,G-I有完美匹配,则称图G是ID-因子临界图,给出了3-正则的ID-因子临界图的刻画.

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)

若干色临界图和色极小图的构造

一个图Ｇ，若对任意的顶点Ｖ（边ｅ），Ｘ（Ｇ－ｖ）＜Ｘ（Ｇ）（Ｘ（Ｇ－ｅ）＜Ｘ（Ｇ）），则称Ｇ是色临界的（色极小的）．给出了色临界图和色极小图的几个构造方法，并探讨了这些构造方法的性质。

关于(a,b,s)-临界图的邻域条件(英文)

设G是一个n阶的图.设a,b和s是整数,使得b>a≥1.设δ(G)是G的最小度.证明了:如果δ(G)≥(k-1)a+s,n≥(a+b)(k(a+b)-2)/b,并且|NG(x1)∪NG(x2)∪…∪NG(xk)|≥an/(a+b)+s对V(G)任意的独立子集{x1,x2,…,xk}都成立,这里k≥2,则G是一个(a,b,s) 临界图.这个结果在某种意义上是最好的.

广义圈的同构因子分解

广义圈是一个简单图C二(V,E),其中点集V。VOU…UVn_1,IVO 二…=IVnll,边集E=u。I。E Vi,。E Vi+;,i二 0,…,n-l,i+l二 mod(川.证明了广义圈可以分解为I个同构因子的充要条件是 t可以整除该广义圈的边数.