不含3,4,8-圈的平面图的2-距离染色（英文）

图G的k-2-距离染色是指映射c:V(G)→{1,2,…,k},使得对G中满足0d_G(u,v)≤2的点对u,v,有c(u)≠c(v).称χ_2(G)=min{k|G有一个k-2-距离染色}为G的2-距离色数.本文证明了不含3,4,8-圈,且△≥14的平面图是(△+5)-2-距离可染的.     

一个定理的简单证明

本文对文献[1]的部分结论给出了一个很简单的证明。本文讨论的图是无向简单图。用d_G(v)或者d(v)表示图G中顶点v的次或度。用G[U]表示点集U的导出子图。其余符号见[2]。设G是一个图,|V(G)|=p,若k是给定的非负整数,若对图G中每一对不相邻的顶点u和v,都有d(u) d(v)≥p k,则称图G为Ore-k型图。     

一个关于图是分数(k,n)-临界的邻域并条件

设G是一个图,以及k是满足1≤k的整数.一个图G在删除任意n个顶点后的子图均含有分数k-因子,则称G是一个分数(k,n)-临界图.给出了图是一个分数(k,n)-临界图的一个邻域并条件,并且该条件是最佳的.     

不含4-圈平面图的2-距离染色

图G的2-距离染色是指映射φ:V(G)→{1,2,…,k},使得距离不超过2的顶点染不同的颜色,即若0d_G(u,v)≤2,则φ(u)≠φ(v).图G的2-距离色数是使G有一个k-2-距离染色的最小正整数k,记为χ_2(G).本文证明了不含4-圈且△(G)≥10的平面图G是(△(G)+10)-2-距离可染的.     

含有给定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=(V,E)是一个n(n≥3)阶k-连通(k≥2)图,记X1,X2,…,Xk为V的子集,X=X1∪X2∪…∪Xk.若对每个I,I=1,2,…,k,满足:对任意的u,v∈Xi,有d(u) d(v)≥n或|N(u)∪N(v)|≥n-δ或|N(u)∩N(v)|≥α,这里δ是G的最小度,α是G的独立数,则G是X-可圈的.     

分数k-因子临界图的条件

设G是-个连通简单无向图,如果删去G的任意k个项点后的图有分数完美匹配,则称G是分数k-因子临界图．给出了G是分数k-因子临界图的韧度充分条件与度和充分条件,这些条件中的界是可达的,并给出G是分数k-因子临界图的一个关于分数匹配数的充分必要条件．     

关于连通图幂中边不交1-因子

本文讨论连通图幂G~n 存在 n 个边不交1-因子的条件.本文中所指图均为简单图.除特别强调外,所用术语、记号均与[1]中一致。定义.设 G 为简单连通图,n 为自然数,则 G~n 为 V(G~n)=V(G),E(G~n)={uv:d_G(u,v)≤n,u,v,∈V(G)}.对 G~n 的因子已有不少结果.主要有以下几个:     

关于分数因子两个开问题的解答

本文指出极小连通二部分数1-因子不一定是极小2-连通图.研究了σ₂（G）与分数k-因子存在性之间的关系,指出存在一个特例在满足阶数n≥4k-5,δ（G）≥k且σ₂（G）≥n条件下,图G不存在分数k-因子.     

若干图的强染色

图 G(V,E)的一正常 k-染色 σ称为 G(V,E)的 - k-强染色当且仅当对任何两个不同顶点 u和 v,只要d(u,v)≤ 2 ,则 u、v染不同颜色 (这里 d(u,v)表示 u,v之间的距离 ) ,并称 xs(G) =min{ k|存在 G的 - k-强染色 }为 G的强色数 ,本文得到 θ-图 ,Cm,n图 ,Halin图的强色数 xs(G)     

最大Randi(c)指标的k悬挂点化学树的性质

化学分子图G的Randic指标为R(G)=E(dG(u)dG(v))-(1/2).其中uv是G的边,dG(u)表示G的顶点u的度.本文刻画了具有最大Randic指标的K悬挂点化学树的一些性质.     

最大Randid指标的k悬挂点化学树的性质

化学分子图G的Randie指标为R（G）=∑wv（dG（u）dG（v））^2/1．其中uv是G的边，dG（u）表示的顶点u的度．本文刻画了具有最大Randie指标的k悬挂点化学树的一些性质．     

图的度和与扩路

本文讨论了两顶点的度和与路可扩之间的关系,得到了如下结果:设G是n阶图,如果G中任意一对不相邻的顶点u,v满足d(u)+d(v)≥n+n/k(2≤k≤n-2),则G中任意一个满足k+1≤|P|相似文献   

Remarks on Vertex-Distinguishing IE-Total Coloring of Complete Bipartite Graphs K4,n and Kn,n

Let G be a simple graph.An IE-total coloring f of G refers to a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color.Let C(u) be the set of colors of vertex u and edges incident to u under f.For an IE-total coloring f of G using k colors,if C(u)=C(v) for any two different vertices u and v of V(G),then f is called a k-vertex-distinguishing IE-total-coloring of G,or a k-VDIET coloring of G for short.The minimum number of colors required for a VDIET coloring of G is denoted by χ ie vt (G),and it is called the VDIET chromatic number of G.We will give VDIET chromatic numbers for complete bipartite graph K4,n (n≥4),K n,n (5≤ n ≤ 21) in this article.     

图K_(2n)\E(K_(2,m))(n≥9,m≥3)的点可区别边染色

对简单图G(V,E),设f是从E(G)到{1,2,…,κ}的映射,κ为自然数,如果f满足:1)对任意的uv,uw∈E(G),v≠w,有f(uv)≠f(uw);2)对任意的u,v∈V(G),u≠v,有C(u)≠C(v).则称f为图G的κ-点可区别边染色法,而最小的κ被称为点可区别边色数(其中C(u)={f(uv)|uv∈E(G)}).研究了图K_(2n)\E(K_(2,m))(n≥9,m≥3)的点可区别边色数.     

哈密尔顿性和部分平方图的独立集

设G是一个图,G的部分平方图G*满足V(G*)=V(G),E(G*)=E(G)∪{uv:uv■E(G),且J(u,v)≠■},这里J(u,v)={w∈N(u)∩N(v):N(w)■N[u]∪N[v]}.利用插点方法,证明了如下结果:设G是k-连通图(k2),b是整数,0min {k,(2b-1+k)/2}(n(Y)-1),则G是哈密尔顿图.同时给出图是1-哈密尔顿的和哈密尔顿连通的相关结果.     

退化图中的子图计数问题研究

令G表示n个顶点的图,如果G的每个子图中都包含一个度至多为k的顶点,则称G为k-退化图.令N(G,F)表示G中F子图的个数.主要研究了k-退化图中完全子图和完全二部子图的计数问题,给出了计数的上界以及相应的极图.首先,证明了Ν(G,K_t)≤(n-k)(k t-1)+(k t).其次,如果s,t≥1,n≥k+1且s+t≤k,我们证明了Ν(G,K_s,t)≤{(k s)(n-s s)-1/2(k s)(k-s s),t=s,(k s)(n-s t)+(k t)(n-t s)-(k t)(k-t s),t≠s.此外,还研究了在最大匹配和最小点覆盖为给定值的情况下,图G中的最大边数.记v(G),K(G)分别为图G的最大匹配数和最小点覆盖.证明了当v(G)≤k,K(G)=k+r且n≥2k+2r²+r+1时,有e(G)≤(k+r+1 2)+(k-r)(n-k-r-1).     

图K_(2n)\E(F_4)(n≥12)的点可区别边染色

对简单图G(V,E),设f是从E(G)到{1,2,…,k}的映射,k为自然数,如果.f满足:1)对任意的uv,uw∈E(G),v≠w,有.f(uv)≠f(uw);2)对任意的u,v∈V(G),u≠v,有C(u)≠C(v).则称f为图G的k-点可区别边染色法,而最小的k被称为点可区别边色数(其中C(u)={f(uv)|uv∈E(G)}.研究了图K_(2n)\E(F_4)(n≥12)的点可区别边色数.     

双圈连通图的L(2,1)-labelling

给定图G,G的一个L(2,1)-labelling是指一个映射f:V(G)→{0,1,2,…},满足:当dG(u,v)=1时,f(u)-f(v)≥2;当dG(u,v)=2时,f(u)-f(v)≥1.如果G的一个L(2,1)-labelling的像集合中没有元素超过k,则称之为一个k-L(2,1)-labelling.G的L(2,1)-labelling数记作l(G),是指使得G存在k-L(2,1)-labelling的最小整数k.如果G的一个L(2,1)-labelling中的像元素是连续的,则称之为一个no-holeL(2,1)-labelling.本文证明了对每个双圈连通图G,l(G)=△ 1或△ 2.这个工作推广了[1]中的一个结果.此外,我们还给出了双圈连通图的no-hole L(2,1)-labelling的存在性.