L（1, 2）-edge-labelings for lattices

For a graph G and two positive integers j and k, an m-L(j, k)-edge-labeling of G is an assignment on the edges to the set {0, 1, 2,..., m}, such that adjacent edges which receive labels differ at least by j, and edges which are distance two apart receive labels differ at least by kThe λ j,k-number of G is the minimum m such that an m-L(j, k)-edge-labeling is admitted by GIn this article, the L(1, 2)-edge-labeling for the hexagonal lattice, the square lattice and the triangular lattice are studied, and the bounds for λ j,k-numbers of these graphs are obtained.     

关于一些图类的L(1,2)-边标号

For a graph G and two positive integers j and k, an m-L(j, k)-edge-labeling of G is an assignment on the edges to the set {0,..., m}, such that adjacent edges receive labels differing by at least j, and edges which are distance two apart receive labels differing by at least k. The λ′j,k-number of G is the minimum m of an m-L(j, k)-edge-labeling admitted by G.In this article, we study the L(1, 2)-edge-labeling for paths, cycles, complete graphs, complete multipartite graphs, infinite ?-regular trees and wheels.     

L（j,k）-number of Direct Product of Path and Cycle

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 all L(j,k)-labelings of G. In this paper, we give some results about the L(j,k)-number of the direct product of a path and a cycle for j≤k.     

任意长圈覆盖指定的独立的点

An invariant σ2（G） of a graph is defined as follows： σ2（G） ：= min{d（u） ＋ d（v）｜u, v ∈V（G）,uv ∈ E（G）,u ≠ v} is the minimum degree sum of nonadjacent vertices （when G is a complete graph, we define σ2（G） = ∞）. Let k, s be integers with k ≥ 2 and s ≥ 4, G be a graph of order n sufficiently large compared with s and k. We show that if σ2（G） ≥ n ＋ k- 1, then for any set of k independent vertices v1,..., vk, G has k vertex-disjoint cycles C1,..., Ck such that ｜Ci｜ ≤ s and vi ∈ V（Ci） for all 1 ≤ i ≤ k.
The condition of degree sum σs（G） ≥ n ＋ k - 1 is sharp.     

The L（3,2, 1）-labeling on Bipartite Graphs

An L（3, 2, 1）-labeling of a graph G is a function from the vertex set V（G） to the set of all nonnegative integers such that ｜f（u）-f（v）｜≥3 if dG（u,v） = 1, ｜f（u）-f（v）｜≥2 if dG（u,v） = 2, and ｜f（u）-f（v）｜≥1 if dG（u,v） = 3. The L（3, 2,1）-labeling problem is to find the smallest number λ3（G） such that there exists an L（3, 2,1）-labeling function with no label greater than it. This paper studies the problem for bipartite graphs. We obtain some bounds of λ3 for bipartite graphs and its subclasses. Moreover, we provide a best possible condition for a tree T such that λ3（T） attains the minimum value.     

树的L(3,2,1)-标号问题

An L(3,2,1)-labeling of a graph G is a function f from the vertex set V(G) to the set of all non-negative integers(labels) such that |f(u)-f(v)|≥3 if d(u,v)=1,|f(u)-f(v)≥2 if d(u,v)=2 and |f(u)-f(v)|≥1 if d(u,v)=3.For a non-negative integer k,a k-L(3,2,1)-labeling is an L(3,2,1)-labeling such that no label is greater than k.The L(3,2,1)-labeling number of G,denoted by λ_(3,2,1)(G), is the smallest number k such that G has a k-L(3,2,1)-labeling.In this article,we characterize the L(3,2,1)-labeling numbers of trees with diameter at most 6.     

Frequency Assignment through Combinatorial Optimization Approach

An L(2,1)-labeling of a graph G is a function f from the vertex set V(G) to the set of all nonnegative integers such that |f(x)-f(y)|(?)2 if d(x, y)=1 and |f(x)-f(y)|(?)1 if d(x,y)=2. The L(2,1)-labeling numberλ(G) of G is the smallest number k such that G has an L(2,1)-labeling with max{f(v) : v∈V(G)}=k. We study the L(3,2,1)-labeling which is a generalization of the L(2,1)-labeling on the graph formed by the (Cartesian) product and composition of 3 graphs and derive the upper bounds ofλs(G) of the graph.     

Hamiltonicity of 4-connected graphs

Let σk（G） denote the minimum degree sum of k independent vertices in G and α（G） denote the number of the vertices of a maximum independent set of G. In this paper we prove that if G is a 4-connected graph of order n and σ5（G） 〉 n ＋ 3σ（G） ＋ 11, then G is Hamiltonian.     

无$K_{1,4}$子图的图的路覆盖

For a graph G, a path cover is a set of vertex disjoint paths covering all the vertices of G, and a path cover number of G, denoted by p(G), is the minimum number of paths in a path cover among all the path covers of G. In this paper, we prove that if G is a K_(1,4)-free graph of order n and σ_(k+1)(G) ≥ n-k, then p(G) ≤ k, where σ_(k+1)(G) = min{∑v∈S d(v) : S is an independent set of G with |S| = k + 1}.     

Vertex-distinguishing IE-total Colorings of Cycles and Wheels

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 χievt（G）, and is called the VDIET chromatic number of G. We get the VDIET chromatic numbers of cycles and wheels, and propose related conjectures in this paper.     

圈的$L(d_1,d_2,\ldots,d_t)$-数$\lambda(C_n;d_1,d_2,\ldots,d_t)$

An L（d0,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 If（x） - f（y）l ≥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,...,dr）- 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）     

一个关于平面图的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$.     

不含某些子图的k连通图中的k可收缩边

最近Ando等证明了在一个$k$($k\geq 5$ 是一个整数) 连通图 $G$ 中,如果 $\delta(G)\geq k+1$, 并且 $G$ 中既不含 $K^{-}_{5}$,也不含 $5K_{1}+P_{3}$, 则$G$ 中含有一条 $k$ 可收缩边.对此进行了推广,证明了在一个$k$连通图$G$中,如果 $\delta(G)\geq k+1$,并且 $G$ 中既不含$K_{2}+(\lfloor\frac{k-1}{2}\rfloor K_{1}\cup P_{3})$,也不含 $tK_{1}+P_{3}$ ($k,t$都是整数,且$t\geq 3$),则当 $k\geq 4t-7$ 时, $G$ 中含有一条 $k$ 可收缩边.     

半无爪可迹图的度和条件

可迹图即为一个含有Hamilton路的图.令$N[v]=N(v)\cup\{v\}$, $J(u,v)=\{w\in N(u)\cap N(v):N(w)\subseteq N[u]\cup N[v]\}$.若图中任意距离为2的两点$u,v$满足$J(u,v)\neq \emptyset$,则称该图为半无爪图.令$\sigma_{k}(G)=\min\{\sum_{v\in S}d(v):S$为$G$中含有$k$个点的独立集\},其中$d(v)$表示图$G$中顶点$v$的度.本论文证明了若图$G$为一个阶数为$n$的连通半无爪图,且$\sigma_{3}(G)\geq {n-2}$,则图$G$为可迹图; 文中给出一个图例,说明上述结果中的界是下确界; 此外,我们证明了若图$G$为一个阶数为$n$的连通半无爪图,且$\sigma_{2}(G)\geq \frac{2({n-2})}{3}$,则该图为可迹图.     

图的邻点可区别全色数的一个上界

Let G = （V, E） be a simple connected graph, and ｜V（G）｜ ≥ 2. Let f be a mapping from V（G） ∪ E（G） to {1,2…, k}. If arbitary uv ∈ E（G）,f（u） ≠ f（v）,f（u） ≠ f（uv）,f（v） ≠ f（uv）; arbitary uv, uw ∈ E（G）（v ≠ w）, f（uv） ≠ f（uw）;arbitary uv ∈ E（G） and u ≠ v, C（u） ≠ C（v）, where
C（u）={f（u）}∪{f（uv）｜uv∈E（G）}.
Then f is called a k-adjacent-vertex-distinguishing-proper-total coloring of the graph G（k-AVDTC of G for short）. The number min{k｜k-AVDTC of G} is called the adjacent vertex-distinguishing total chromatic number and denoted by χat（G）. In this paper we prove that if △（G） is at least a particular constant and δ ≥32√△ln△, then χat（G） ≤ △（G） ＋ 10^26 ＋ 2√△ln△.     

几乎无爪图的叶子数较少的生成树

A spanning tree with no more than 3 leaves is called a spanning 3-ended tree.In this paper, we prove that if G is a k-connected(k ≥ 2) almost claw-free graph of order n and σ_(k+3)(G) ≥ n + k + 2, then G contains a spanning 3-ended tree, where σk(G) =min{∑_(v∈S)deg(v) : S is an independent set of G with |S| = k}.