关于图的L(d,1)-标号问题

图G的L(2,1)-标号是一个从顶点集V(G)到非负整数集的函数f(x),使得若d(x,y)=1,则|f(x)-f(y)|≥2;若d(x,y)=2,则|f(x)-f(y)|≥1.图G的L(2,1)-标号数λ(G)是使得G有max{f(v)v∈V(G)}=k的L(2,1)-标号中的最小数k.Griggs和Yeh猜想对最大度为△的一般图G,有λ(G)≤△2.此文研究了作为L(2,1)-标号问题的推广的L(d,1)-标号问题,并得出了平面三角剖分图、立体四面体剖分图、平面近四边形剖分图的L(d,1)-标号的上界,作为推论证明了对上述几类图该猜想成立.     

关于两类平面图及相关图的L(d1,d2)-标号问题

图G的L(2,1)标号是一个从顶点集V(G)到非负整数集的函数f(x),使得若d(x,y)=1,则|f(x)-f(y)|≥(2;若d(x,y)=2,则|f(x)-f(y)|≥1.图G的L(2,1)标号数λ(G)是使得G有max{f(v)V∈V(G)}=k的L(2,1)标号中的最小数k.Griggs和Yeh猜想对最大度为△的一般图G,有λ(G)≤△2.本文将L(2,1)-标号推广到L(d1,d2)-标号,并得出了平面三角剖分图、立体四面体剖分图、平面近四边形剖分图的L(d1,d2)-标号的上界,作为推论,本文证明了对上述几类图,有上述猜想成立.     

一类积图的局部边路替换图的L(2,1)-标号

图(i=0,1,…,n-1)的一个L(2,1)-标号就是从点集到非负整数集的一个函数,且满足任两个相邻顶点标号差至少为2,以及任两个距离为2的点标号不同.图(i=0,1,…,n-1)的一个(2,1)-全标号就是从点集和边集到非负整数集的一个函数且使得:任两个相邻顶点标号差至少为2;任两个相邻边标号标号差也至少为2;以及任两个关联的点和边标号也不同.本文研究路路的积图的局部边路替换图的L(2,1)-标号,基本得到了路路的Cartesian积的局部边路替换图的L(2,1)-标号数.     

仙人掌图的L（2，1）-标号

一个图G的L（2，1）-标号是给图G上的顶点分配非负整数标号，使得G上相邻的两个点的标号至少相差2，距离为2的两个点的标号则不同．G的L（2，1）-标号数λ（G）是所有能使图G正常标号的最小标号．如果一个图的任何两个圈不含有公共边，则称这个图为仙人掌图．显然树是它的一个子图类．对于任何树T，有△（T） ＋ 1 ≤λ（T） ≤△A（T）＋2．本文中我们证明了在一些条件下，这个界也适用于仙人掌图．     

不含5-圈和6-圈的平面图的(2,1)-全标号

图G的(2,1)-全标号是对图G的顶点和边的一个标号分配,使得:(1)任意两个相邻顶点标号不同;(2)任意两条相邻边标号不同;(3)任意顶点与其相关联的边标号至少相差2.两个标号的最大差值称为跨度,图G的所有(2,1)-全标号的最小跨度称为(2,1)-全标号数,记为λ_2~T(G).本文证明了如果G是一个?=p+5的平面图,且G不包含5-圈和6-圈,那么λ_2~T(G)=2?-p,p=1,2,3.     

双圈连通图的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的存在性.     

弦图的L(3,2,1)}-标号

图 G 的一个 L(3,2,1)- 标号是指从 V(G) 到非负整数集的一个映射 f, 满足: 当 d_G(u,v)=1 时, |f(u)-f(v)|\geq 3; 当 d_G(u,v)=2 时, |f(u)-f(v)|\geq 2; 当 d_G(u,v)=1 时, |f(u)-f(v)|\geq 1. L(3,2,1)-标号问题就是确定出最小的整数 \lambda_3(G) 使得 G存在最大标号不超过该数的 L(3,2,1)- 标号. 本文研究了弦图的 L(3,2,1)- 标号问题,获得了弦图及其一些子类, 如扇, r- 路,r- 树等的 \lambda_3 数的界.     

一个关于平面图的K-(2,1)-全可选性的结果

设图$G$的一个列表分配为映射$L: V(G)\bigcup E(G)\rightarrow2^{N}$. 如果存在函数$c$使得对任意$x\in V(G)\cup E(G)$有$c(x)\in L(x)$满足当$uv\in E(G)$时, $|c(u)-c(v)|\geq1$, 当边$e_{1}$和$e_{2}$相邻时, $|c(e_{1})-c(e_{2})|\geq1$, 当点$v$和边$e$相关联时, $|c(v)-c(e)|\geq 2$, 则称图$G$为$L$-$(p,1)$-全可标号的. 如果对于任意一个满足$|L(x)|=k,x\in V(G)\cup E(G)$的列表分配$L$来说, $G$都是$L$-$(2,1)$-全可标号的, 则称$G$是 $k$-(2,1)-全可选的. 我们称使得$G$为$k$-$(2,1)$-全可选的最小的$k$为$G$的$(2,1)$-全选择数, 记作$C_{2,1}^{T}(G)$. 本文, 我们证明了若$G$是一个$\Delta(G)\geq 11$的平面图, 则$C_{2,1}^{T}(G)\leq\Delta+4$.     

图的L(3,2,1)-标号

无向图G的L(3,2,1)-标号是指从顶点集V(G)到非负整数集Z*的一个映射,满足:对i=1,2,3,只要dG(x,y)=i,则f(x)-f(y)|≥4-i.若一个L(3,2,1)-标号中的所有像元素都不超过整数k,则称之为k-L(3,2,1)-标号.图G的L(3,2,1)-标号数,记作3λ(G),是使得图G存在k-L(3,2,1)-标号的最小整数k.文中给出了路、圈、树等特殊图的L(3,2,1)-标号数,并给出了一般图的L(3,2,1)-标号数的一个上界.     

点接手镯图的L(1,1,1)-标号

图的L(1,1,1)-标号定义为顶点集V(G)到非负整数集的映射f,且当d(u,v)=1,2,3时,均有|f(u)-f(v)|≥1.不妨设0为最小标号,则称图G的所有L(1,1,1)-标号中的最大跨度f(v)的最小数为图的L(1,1,1)-标号数,记为λ(G).基本给出了点接手镯图的L(1,1,1)-标号数的确切值.     

L(d1, d2,..., dt)-Number λ(Cn; d1, d2,...,dt) of Cycles

An L(d1,d2,...,dt)-labeling of a graph G is a function f from its vertex set V(G) to the set {0, 1,..., k} for some positive integer k such that {f(x) - f(y)| ≥ di, if the distance between vertices x and y in G is equal to i for i = 1,2,...,t. The L(d1,d2,...,dt)-number λ(G;d1,d2,... ,dt) of G is the smallest integer number k such that G has an L(d1,d2,... ,dt)labeling with max{f(x)|x ∈ V(G)} = k. In this paper, we obtain the exact values for λ(Cn; 2, 2,1) and λ(Cn; 3, 2, 1), and present lower and upper bounds for λ(Cn; 2,..., 2,1,..., 1)     

关于图的L(2,1)标号核图

图的L(2,1)标号核图来自频率分配问题而导致的图论问题.在本文中,我们证得(i)对任意简单图G,存在G的一个标号核图Gcore,使得L(G)=L(Gcore)和L(G)≥|V(Gcore)|-1;(ii)设图G有p个顶点且边集|E(G)|≠φ,存在路 Pi G(1≤i≤m)和路Hs G(1≤s≤n),其中在G中V(Pi)∩V(Pj)=φ(i≠j),在G中V(P,)∩V(Pt)=φ(s≠t),则有m∑t=1|V(Pt)|+n∑s=1|V(Hs)|-(m+n)≥p;(iii)G是p(p≥5)个顶点的简单图,则有p+3≤L(G)+L(G)≤3p-4.     

本刊英文版Vol.29(2013),No.8论文摘要(英文)

<正>L(j,k)-number of Direct Product of Path and Cycle Wai Chee SHIU Qiong WU Abstract For positive numbers j and k,an L(j,k)-labeling f of G is an assignment of numbers to vertices of G such that |f(u)-f(v)|≥j if uv∈E(G),and |f(u)-f(v)|≥k if d(u,v)=2.Then the span of f is the difference between the maximum and the minimum numbers assigned by f.The L(j,k)-number of G,denoted byλ_(j,k)(G),is the minimum span over     

两类图的L(2.1)-标号数

图G的一个L(2.1)-标号是从顶点集V(G)到非负整数的一个函数f,使得若d(u,v)=1时,有|f(u)-f(v)|≥2;若d(u,v)=2时,有|f(u)-f(v)|≥1.图G的L(2.1)-标号数λ(G)是G的所有L(2.1)-标号下的跨度max{f(v):v∈V(G)}的最小数.图Fn+1*为扇图的路上每个顶点增加一个悬挂边得到的图.图Hn为轮图的圈上每个顶点增加一个悬挂边得到的图.本文确定了图Fn+1*与Hn的L(2.1)-标号数.     

Total coloring of planar graphs without chordal 7-cycles

A k-total-coloring of a graph G is a coloring of vertices and edges of G using k colors such that no two adjacent or incident elements receive the same color.In this paper,it is proved that if G is a planar graph with Δ(G) ≥ 7 and without chordal 7-cycles,then G has a(Δ(G) + 1)-total-coloring.     

关于几类图的L(2,1)标号问题

图G的L( 2 ,1 )标号是一个从顶点集V(G)到非负整数集的函数f(x) ,使得若d(x ,y) =1 ,则｜f(x) -f(y) ｜≥ 2 ;若d(x ,y) =2 ,则｜f(x) -f(y) ｜≥ 1 .图G的L( 2 ,1 ) 标号数λ(G)是使得G有max{f(v) ∶v∈V(G) }=k的L( 2 ,1 )标号中的最小数k .Griggs和Yeh猜想对最大度为Δ的一般图G ,有λ(G) ≤Δ2 .本文给出了Kneser图 ,Mycieklski图 ,Descartes图 ,Halin图的λ值的上界 ,并证明了上述猜想对以上几类图成立     

On the hole index of L(2,1)-labelings of r-regular graphs

An L(2,1)-labeling of a graph G is an assignment of nonnegative integers to the vertices of G so that adjacent vertices get labels at least distance two apart and vertices at distance two get distinct labels. A hole is an unused integer within the range of integers used by the labeling. The lambda number of a graph G, denoted λ(G), is the minimum span taken over all L(2,1)-labelings of G. The hole index of a graph G, denoted ρ(G), is the minimum number of holes taken over all L(2,1)-labelings with span exactly λ(G). Georges and Mauro [On the structure of graphs with non-surjective L(2,1)-labelings, SIAM J. Discrete Math. 19 (2005) 208-223] conjectured that if G is an r-regular graph and ρ(G)?1, then ρ(G) must divide r. We show that this conjecture does not hold by providing an infinite number of r-regular graphs G such that ρ(G) and r are relatively prime integers.     

关于图的L(3,2,1)-标号问题

图G的L( 2 ,1 )标号是一个从顶点集V(G)到非负整数集的函数f(x) .使得若d(x ,y) =1 .则｜f(x) -f(y) ｜≥ 2 ;若d(x ,y) =2 ,则｜f(x) -f(y)｜≥ 1 .图G的L( 2 ,1 )标号数λ(G)是使得G有max{f(v) ∶v∈V(G) }=k的L( 2 ,1 )标号中的最小数k .本文将L( 2 ,1 ) 标号问题推广到更一般的情形即L( 3,2 ,1 ) 标号问题 .我们首先定义了图G的顶点 3 着色及图的 3 色数 χ3 (G)等有关概念 ,并推导出 3 色数 χ3 (G)的上界 ;然后根据 χ3 (G)与λ3 (G)的关系 ,得出了对一般图G ,有λ3 (G) ≤ 3maxH Gδ(H) (Δ2 -Δ 1 )这一一般关系式 ;最后证明了对一般平面图G ,有λ3 (G)≤ 1 5(Δ2 -Δ 1 ) ,并得出了其它几类平面图的λ3 (G)的上界 .