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...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.展开更多
A k-L(2,1)-labeling for a graph G is a function such that whenever and whenever u and v are at distance two apart. The λ-number for G, denoted by λ(G), is the minimum k over all k-L(2,1)-labelings of G. In this pape...A k-L(2,1)-labeling for a graph G is a function such that whenever and whenever u and v are at distance two apart. The λ-number for G, denoted by λ(G), is the minimum k over all k-L(2,1)-labelings of G. In this paper, we show that for or 11, which confirms Conjecture 6.1 stated in [X. Li, V. Mak-Hau, S. Zhou, The L(2,1)-labelling problem for cubic Cayley graphs on dihedral groups, J. Comb. Optim. (2013) 25: 716-736] in the case when or 11. Moreover, we show that? if 1) either (mod 6), m is odd, r = 3, or 2) (mod 3), m is even (mod 2), r = 0.展开更多
An L（2, 1）-labelling 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）│≥2 if dG（u, v） = 1 and │f（u） - f（v）│ ≥ 1 if dG（u, v） = 2. Th...An L（2, 1）-labelling 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）│≥2 if dG（u, v） = 1 and │f（u） - f（v）│ ≥ 1 if dG（u, v） = 2. The L（2, 1）-labelling problem is to find the smallest number, denoted by A（G）, such that there exists an L（2, 1）-labelling function with no label greater than it. In this paper, we study this problem for trees. Our results improve the result of Wang [The L（2, 1）-labelling of trees, Discrete Appl. Math. 154 （2006） 598-603].展开更多
An L(h,k)-labeling of a graph G is an assignment of non-negative integers to the vertices such that if two vertices u and v are adjacent then they receive labels that differ by at least h, and when u and v are not adj...An L(h,k)-labeling of a graph G is an assignment of non-negative integers to the vertices such that if two vertices u and v are adjacent then they receive labels that differ by at least h, and when u and v are not adjacent but there is a two-hop path between them, then they receive labels that differ by at least k. The span λ of such a labeling is the difference between the largest and the smallest vertex labels assigned. Let λ<sub>h</sub>k</sup> ( G )denote the least λ such that G admits an L(h,k) -labeling using labels from {0,1,...λ}. A Cayley graph of group is called circulant graph of order n, if the group is isomorphic to Z<sub>n.</sub> In this paper, initially we investigate the L(h,k) -labeling for circulant graphs with “large” connection sets, and then we extend our observation and find the span of L(h,k) -labeling for any circulants of order n. .展开更多
An L(0,1)-labelling of a graph G is an assignment of nonnegative integers to the vertices of G such that the difference between the labels assigned to any two adjacent vertices is at least zero and the difference betw...An L(0,1)-labelling of a graph G is an assignment of nonnegative integers to the vertices of G such that the difference between the labels assigned to any two adjacent vertices is at least zero and the difference between the labels assigned to any two vertices which are at distance two is at least one. The span of an L(0,1)-labelling is the maximum label number assigned to any vertex of G. The L(0,1)-labelling number of a graph G, denoted by λ0.1(G) is the least integer k such that G has an L(0,1)-labelling of span k. This labelling has an application to a computer code assignment problem. The task is to assign integer control codes to a network of computer stations with distance restrictions. A cactus graph is a connected graph in which every block is either an edge or a cycle. In this paper, we label the vertices of a cactus graph by L(0,1)-labelling and have shown that, △-1≤λ0.1(G)≤△ for a cactus graph, where △ is the degree of the graph G.展开更多
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 ifd（x, y） = 2. The ...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 ifd（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 λ3（G） of the graph.展开更多
Given two non-negative integers h and k, an L（h, k）-labeling of a graph G = （V, E） is a function from the set V to a set of colors, such that adjacent nodes take colors at distance at least h, and nodes at distanc...Given two non-negative integers h and k, an L（h, k）-labeling of a graph G = （V, E） is a function from the set V to a set of colors, such that adjacent nodes take colors at distance at least h, and nodes at distance 2 take colors at distance at least k. The aim of the L（h, k）-labeling problem is to minimize the greatest used color. Since the decisional version of this problem is NP-complete, it is important to investigate particular classes of graphs for which the problem can be efficiently solved. It is well known that the most common interconnection topologies, such as Butterfly-like, Beneg, CCC, Trivalent Cayley networks, are all characterized by a similar structure： they have nodes organized as a matrix and connections are divided into layers. So we naturally introduce a new class of graphs, called （l × n）-multistage graphs, containing the most common interconnection topologies, on which we study the L（h, k）-labeling. A general algorithm for L（h, k）-labeling these graphs is presented, and from this method an efficient L（2, 1）-labeling for Butterfly and CCC networks is derived. Finally we describe a possible generalization of our approach.展开更多
Let G be an outerplanar graph with maximum degree △. Let χ（G^2） and A（G） denote the chromatic number of the square and the L（2, 1）-labelling number of G, respectively. In this paper we prove the following resu...Let G be an outerplanar graph with maximum degree △. Let χ（G^2） and A（G） denote the chromatic number of the square and the L（2, 1）-labelling number of G, respectively. In this paper we prove the following results： （1） χ（G^2） = 7 if △= 6; （2） λ（G） ≤ △ ＋5 if △ ≥ 4, and ）,（G）≤ 7 if △ = 3; and （3） there is an outerplanar graph G with △ = 4 such that ）λ（G） = 7. These improve some known results on the distance two labelling of outerplanar graphs.展开更多
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 di...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.展开更多
基金The NSF (60673048) of China the NSF (KJ2009B002,KJ2009B237Z) of Education Ministry of Anhui Province.
文摘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.
基金National Natural Science Foundation of China(No.10671074 and No.60673048)Natural Science Foundation of Education Ministry of Anhui Province(No.KJ2007B124 and No.2006KJ256B)
文摘A k-L(2,1)-labeling for a graph G is a function such that whenever and whenever u and v are at distance two apart. The λ-number for G, denoted by λ(G), is the minimum k over all k-L(2,1)-labelings of G. In this paper, we show that for or 11, which confirms Conjecture 6.1 stated in [X. Li, V. Mak-Hau, S. Zhou, The L(2,1)-labelling problem for cubic Cayley graphs on dihedral groups, J. Comb. Optim. (2013) 25: 716-736] in the case when or 11. Moreover, we show that? if 1) either (mod 6), m is odd, r = 3, or 2) (mod 3), m is even (mod 2), r = 0.
基金Supported by the Natural Science Foundation of Education Ministry of Anhui Province (No.KJ2010B138)the Foundation for the Excellent Young Talents of Anhui Province(No.2010SQRL136ZD)the Natural Science Foundation of Chuzhou University(No.2008kj013B)
基金Supported by the National Natural Science Foundation of China (No. 10971248,11101057)Anhui Provincial Natural Science Foundation (No. 10040606Q45)Postdoctoral Science Foundation of Jiangsu Provinc (No.1102095C)
文摘An L（2, 1）-labelling 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）│≥2 if dG（u, v） = 1 and │f（u） - f（v）│ ≥ 1 if dG（u, v） = 2. The L（2, 1）-labelling problem is to find the smallest number, denoted by A（G）, such that there exists an L（2, 1）-labelling function with no label greater than it. In this paper, we study this problem for trees. Our results improve the result of Wang [The L（2, 1）-labelling of trees, Discrete Appl. Math. 154 （2006） 598-603].
文摘An L(h,k)-labeling of a graph G is an assignment of non-negative integers to the vertices such that if two vertices u and v are adjacent then they receive labels that differ by at least h, and when u and v are not adjacent but there is a two-hop path between them, then they receive labels that differ by at least k. The span λ of such a labeling is the difference between the largest and the smallest vertex labels assigned. Let λ<sub>h</sub>k</sup> ( G )denote the least λ such that G admits an L(h,k) -labeling using labels from {0,1,...λ}. A Cayley graph of group is called circulant graph of order n, if the group is isomorphic to Z<sub>n.</sub> In this paper, initially we investigate the L(h,k) -labeling for circulant graphs with “large” connection sets, and then we extend our observation and find the span of L(h,k) -labeling for any circulants of order n. .
文摘An L(0,1)-labelling of a graph G is an assignment of nonnegative integers to the vertices of G such that the difference between the labels assigned to any two adjacent vertices is at least zero and the difference between the labels assigned to any two vertices which are at distance two is at least one. The span of an L(0,1)-labelling is the maximum label number assigned to any vertex of G. The L(0,1)-labelling number of a graph G, denoted by λ0.1(G) is the least integer k such that G has an L(0,1)-labelling of span k. This labelling has an application to a computer code assignment problem. The task is to assign integer control codes to a network of computer stations with distance restrictions. A cactus graph is a connected graph in which every block is either an edge or a cycle. In this paper, we label the vertices of a cactus graph by L(0,1)-labelling and have shown that, △-1≤λ0.1(G)≤△ for a cactus graph, where △ is the degree of the graph G.
文摘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 ifd（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 λ3（G） of the graph.
基金Sapienza University of Rome(project"Parallel and Distributed Codes")
文摘Given two non-negative integers h and k, an L（h, k）-labeling of a graph G = （V, E） is a function from the set V to a set of colors, such that adjacent nodes take colors at distance at least h, and nodes at distance 2 take colors at distance at least k. The aim of the L（h, k）-labeling problem is to minimize the greatest used color. Since the decisional version of this problem is NP-complete, it is important to investigate particular classes of graphs for which the problem can be efficiently solved. It is well known that the most common interconnection topologies, such as Butterfly-like, Beneg, CCC, Trivalent Cayley networks, are all characterized by a similar structure： they have nodes organized as a matrix and connections are divided into layers. So we naturally introduce a new class of graphs, called （l × n）-multistage graphs, containing the most common interconnection topologies, on which we study the L（h, k）-labeling. A general algorithm for L（h, k）-labeling these graphs is presented, and from this method an efficient L（2, 1）-labeling for Butterfly and CCC networks is derived. Finally we describe a possible generalization of our approach.
基金Supported by the National Natural Science Foundation of China(No.10771197)
文摘Let G be an outerplanar graph with maximum degree △. Let χ（G^2） and A（G） denote the chromatic number of the square and the L（2, 1）-labelling number of G, respectively. In this paper we prove the following results： （1） χ（G^2） = 7 if △= 6; （2） λ（G） ≤ △ ＋5 if △ ≥ 4, and ）,（G）≤ 7 if △ = 3; and （3） there is an outerplanar graph G with △ = 4 such that ）λ（G） = 7. These improve some known results on the distance two labelling of outerplanar graphs.
基金Supported by Faculty Research Grant, Hong Kong Baptist University
文摘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.
