K连通图的k分割多项式算法

图G的K分割问题可描述为:输入(Ⅰ)G=(V,E),G为简单无向图,其中|V|=n,|E|= m;(Ⅱ)a_1,a_2,…,a_k k个G中不同的顶点;(Ⅲ)n_1,n_2,…,n_k k个正整数满足 n_1+n_2+…,+n_k= n.输出(V_1,V_2,…,V_k),对1≤i≤k,满足(Ⅰ)a_i∈V_i;(Ⅱ)G[V_i]是连通图;(Ⅲ)|V_i|=n_i.本文给出时间复杂性为O(knm)通用K连通图的k分割多项式算法.     

Corona图P_nｏF_(1,m)、C_nｏC_m与C_nｏF_(1,m)的b-染色数

在图G=(V,E)的一个正常染色{V_1,V_2,…,V_k}中,若i,j,1≤i≠j≤k,■u∈V_i,v∈V_j,使得uv∈E,称该染色为b-染色.令b(G)=max{k|V_1,V_2,…,V_k:i,j,1≤i≠j≤k,■u∈V_i,v∈V_j,uv∈E},称b(G)为图G的b-染色数.一个图G是b-连续的,如果k:χ(G)≤k≤b(G),用k种颜色可实现对G进行b-染色.通过构造特殊染色方案,研究了Corona图P_noF_(1,m)、C_noC_m与CnoF_(1,m)的b-染色数与b-连续性.     

Sm∨Fn的全色数

设G(V,E)是阶数至少是2的简单连通图,k是正整数,若f是从V(G)∪E(G)到{1,2,…,k}的一个映射,使得:对于任意的uv,vw∈E(G),u≠w,有f(uv)≠f(vw);且对于任意的uv∈E(G),u≠v,有f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv),则称f为G的一个k-全染色(简记成k-TC of G).而χt(G)=min{k|k-TC of G},称为G的全色数.设G和H是点边都不相交的简单图,V(G∨H)=V(G)∪V(H),E(G∨H)=E(G)∪E(H)∪{uv|u∈V(G),v∈V(H)},则称G∨H是G与H的联图.给出m 1阶星和n 1阶扇的联图的全色数.     

无K_(1,t)图的L(d,1)-T标号

给定一个连通图G=(V,E)及其一棵支撑树T,图G的一个L(d,1)-T标号即函数g:V(G)→{0,1,2,…},满足:(1)如果xy∈E(G),则|g(x)-g(y)|≥1;(2)如果dG(x,y)=2,则|g(x)-g(y)|≥1;(3)如果xy∈E(T),则|g(x)-g(y)|≥d.假设图G有一个L(d,1)-T标号函数g:g(V){0,1,2,…,k},则图G的所有L(d,1)-T标号函数中最小的整数k记为L(d,1)-T标号数λdT(G,T).本文证明了若G是无K1,t(3≤t≤n)的连通图,其最大度为Δ,|G|=n,T为G的任意支撑树,则λdT(G,T)≤tt--12Δ2+Δ+2d-2.     

图的代数连通度及其点连通度

G是一个简单图.a(G),k(G)分别为G的代数连通度和点连通度,该文刻画了满足a(G)=k(G)的图.G=(V,E)是一个n阶简单图,点连通度为k(G)≤[n/2].H是G的任意最小点割集,则a(G)=k(G)当且仅当对任意u∈H和v∈V\H,有uv∈E.     

图中顶点子集的边连通度与最优分级边连通图的构造问题

G =(V ,E)是无向连通图 ,无环允许有重边 .S是V的至少包含两个顶点的子集 ,S的边连通度λG(S)被定义为使S中的顶点不属于同一连通分支所需去掉的最少边数 .给定集合V和V的一个划分V =V1∪V2 ∪…∪Vr(|r|≥ 1,|V1|≥ 2 )以及正整数序列k1>k2 >… >kr≥ 2 .记Si=V1∪V2 ∪…∪Vi,1≤i≤r.构造一个连通图G =(V ,E)满足 :λG(Si)≥ki(1≤i≤r)且边数 |E|最小 .这种图G称为与所给划分和正整数序列相对应的最优分级边连通图 .在给出顶点子集的边连通度概念的基础上 ,本文提出并讨论了有关最优分级边连通图的构造问题     

完全图上的锥的D(2)-点可区别正常边染色

设G是顶点集合为V(G)={v_(0i)|i=1,2,…,p}的简单图,n是正整数,称M_n(G)为G上的锥(或广义Mycielski图),如果V(M_n(G)={v_(01),v_(02),…,v_(0p);v_(11),v_(12),…,v_(1p);…v_(n1),v_(n2),…,v_(np),w}) E(M_n(G))=E(G)∪{v_(ij)v_((i 1)k)|v_(0j)v_(0k)∈E(G),1≤j,k≤p,i=0,1,…,n-1}∪{v_(nj)w|1≤j≤p}.在这篇文章里,我们讨论了完全图上的锥的$D(2)$-点可区别的正常边染色,并给出了相应色数.     

图F_m ▽S_n的边色数和邻强边色数

对图G的一个正常的k边染色法f,若 e∈E(G),e = uv,{f(uw) | uw∈E(G)}≠{f(vw) | vw∈E(G)},则称f为G 的一个k 邻强边染色法,k的最小值称为G 的邻强边色数.V(Fm Sn) = {w}∪{ui | i =1,2,…,m}∪{vij | i =1,2,…,m;j =1,2,…,n},E(Fm Sn) = {wui | i =1,2,…,m}∪{uivij | i =1,2,…,m;j =1,2,…,n}∪{uiui+1 | i =1,2,…,m-1}.　　本文得到了Fm Sn 的边色数和邻强边色数.     

关于图的哈密尔顿性的一些新的结果

关于哈密尔顿图和哈密尔顿连通的两个基本结果是Ore给出的:设G是一个n(n≥3)阶图,如果对于G的任意一对不相邻顶点u,v,有d(u) d(v)≥n或n 1,则G是哈密尔顿图或哈密尔顿连通的.设G是一个图,对于任意u∈V(G),令N(u)表示u的邻点集;对于任意U∈V(G),令N(U)=∪u∈UN(u).本文利用插点方法,给出了关于k或(k 1)-连通图(k≥2)G是哈密尔顿的,哈密尔顿连通的或1-哈密尔顿的统一证明.其充分条件是关于|N(S)| |N(T)|与n(S ∪T)的不等式,这里S,T是图G的任意两个不交的独立集,并且|S|=s,|T|=1,S∪T也是一个独立集,这里n(S∪T)=|{v∈V(G):dist(v,S∪T)≤2}|.     

二分图中存在包含经过给定边的大圈的2-因子的度条件

该文主要证明了若G=(V1,V2;E)是一个满足|V1|=|V2|=n≥sk的二分图,其中k,s,n为3个正整数且k≥2,s≥4,如果σ1,1(G)≥2「(1-1/s)n k﹁,那么对G的任意k条独立边e1,…,ek,G有一个包含k个点不交的圈C1,…,Ck的2-因子,使得ei∈E(Ci),且|Ci|≥2s.     

2-连通图的最长圈

设 G是具有围长 g≥5 的 n 阶 2-连通简单图,P=v_1v_2…v_t 是 G的一条最长道路。若λ=min{d(u)+d(v)|u,v∈V(G),uv∈E(G)},δ~*=min{d(v_1),d(v_t)},则G的最长圈为:其中.δ= min{d(v)|v∈V(G)}。     

圈和扇的倍图的邻点可区别VE-全色数

对简单连通图G(V,E),存在一个正整数k,和映射f:V(G)∪E(G)→{1,2,…,k},使得对uv∈E(G),有f(u)≠f(uv),f(v)≠f(uv),且C(u)≠C(v),则称f是图G的邻点可区别VE-全染色,而χvate(G)=min{k|k-AVD-VETC},称为G的邻点可区别VE-全色数,其中色集合C(u)={f(u)}∪{f(uv)|uv∈E(G)}.给出圈的倍图D(Cm)和扇的倍图D(Fm)的邻点可区别VE-边全色数.     

2-连通图中点不交路的划分问题

给定一个阶为n的2-连通图G=(V;E)及一个正整数k,考虑在邻域并条件下G被分成k条点不交路的问题,得到下面的结果,对G中任何四个独立点x1,x2,y1,y2∈V,满足|NG(x1)∪NG(x2)| |NG(y1)∪NG(y2)|n-k,则G能被分划分k条点不交的路.     

关于图运算的和连通指标（英文）

设G=(V,E)是一个简单的连通图,V(G)和E(G)分别是图G的顶点集和边集,其中|V(G)|=n,|E(G)|=m.设d_i是点v_i的度数,i=1,2,…,n.Zhou和Trinajasti c′定义了一个新的拓扑指标,命名为和连通指标,记作X(G)并定义为X(G)=∑uv∈E(G)1/(d_u+d_v)~(1/2).该文得到了包括图的交,并,科罗纳积,笛卡尔积,和对称差的图运算的和连通指标.     

图的点强全染色

图G(V,E)的正常k—全染色f叫做G(V,E)的k—点强全染色,当且仅当对任意的w∈V(G),N[w]中元素染不同颜色,其中N[w]={x|wx∈E(G)}∪{w}.并称XvTs(G)=min{k|存在G的k—点强全染色}为图G(V,E)的点强全色数.本文研究了K4-minor free图和外平面图的点强全色数.     

每点都与3度点相邻的最大临界3棱连通图的结构

没G=(V,E)是3棱连通图,若对每个x∈V(G),G-x 不是3棱连通的,则称G 为临界3棱连通图.p 阶临界3棱连通图的全体记为(?)_3(p),G∈(?)_3(p)称为最大的,如果不存在H∈(?)_3(p),使|E(H)|>|E(G)|.本文给出每个点都与3度点相邻的p 阶最大临界3棱连通图的结构.     

图Fm(△)Fn的边色数和邻强边色数

V(Fm(△)Fn)={w}∪{ui|i=1,2,…,m}∪{vij|i=1,2,…,m;j=1,2,…,n},E(Fm(△)Fn)={wui|i=1,2,…,m}∪{uivij|i=1,2,…,m,j=1,2,…,n}∪{uiui+1|i=1,2,…,m-1}∪{vijvij+1|i=1,2,…,m;j=1,2,…,n-1}对图G的一个正常的k边染法f,若e∈E(G),e=uv,{f(uw)|uw∈E(G)}≠{f(uw)|uw∈E(G)}则称f为G的一个k-邻强边染色法,k的最小值称为G的邻强边色数.本文得到了Fm(△)Fn的边色数和邻强边色数.     

关于几类特殊图的Mycielski图的邻点可区别全色数

设G是一个简单图,f是一个从V(G)∪ E(G)到{1,2,…,k}的映射.对每个v∈V(G),令Cf(v)={f(v)}∪{f(vw)|w∈V(G),vw∈E(G)}.如果f是G的正常全染色且u,v∈V(G),一旦uv∈E(G),就有Cf(u)≠Cf(v),那么称f为G的邻点可区别全染色(简称为k-AVDTC).设xat(G)=min{k|G存在k-AVDTC},则称xat(G)为G的邻点可区别全色数.给出了路、圈、完全图、完全二分图、星、扇和轮的Mycielski图的邻点可区别全色数.     

多重联图Sm∨Pn∨Pn 的邻点可区别边色数

设G(V,E)为阶数至少是3的简单连通图,若f是图G的k-正常边染色,使得对任意的uv∈E(G),C(u)≠C(v),那么称f是图G的k-邻点可区别边染色(k-ASEC),其中C(u)={f(uw)|uw∈E(G)},而aχs′(G)=min{k|存在G的一个k-ASEC},称为G的邻点可区别边色数.给出多重联图Sm∨Pn∨Pn的邻点可区别边色数.     

若干Mycielski图邻点可区别Ⅰ-均匀全染色

图G的一个邻点可区别Ⅰ-均匀全染色是指对图G的邻点可区别的一个Ⅰ-全染色f,若f还满足||T_i|-|T_j||≤1(i≠j),其中T_i=V_i∪E_i={v|v∈V(G),f(v)=i}∪{e|e∈E(G),f(e)=i},则称f为图G的一个邻点可区别Ⅰ-均匀全染色,而图G的邻点可区别Ⅰ-均匀全染色中所用的最少颜色数称为图G的邻点可区别Ⅰ-均匀全色数.通过函数构造法,得到了M(Pn)、M(Cn)、M(Sn)的邻点可区别Ⅰ-均匀全色数,并且满足猜想.