An edge coloring total k-labeling is a labeling of the vertices and the edges of a graph G with labels {1,2,..., k} such that the weights of the edges define a proper edge coloring of G. Here the weight of an edge is ...An edge coloring total k-labeling is a labeling of the vertices and the edges of a graph G with labels {1,2,..., k} such that the weights of the edges define a proper edge coloring of G. Here the weight of an edge is the sum of its label and the labels of its two end vertices. This concept was introduce by Brandt et al. They defined Xt＇（G） to be the smallest integer k for which G has an edge coloring total k-labeling and proposed a question： Is there a constant K with X^t（G） ≤△（G）＋1/2 K for all graphs G of maximum degree A（G）？ In this paper, we give a positive answer for outerplanar graphs ≤△（G）＋1/2 by showing that X＇t（G） ≤△（G）＋1/2 for each outerplanar graph G with maximum degree A（G）.展开更多
An （a, d）-edge-antimagic total labeling of a graph G is a bijection f from V（G） ∪ E（G） onto {1, 2,..., ｜V（G）｜ ＋ ｜E（G）｜} with the property that the edge-weight set {f（x） ＋ f（xy） ＋ f（y） ｜ xy ∈ ...An （a, d）-edge-antimagic total labeling of a graph G is a bijection f from V（G） ∪ E（G） onto {1, 2,..., ｜V（G）｜ ＋ ｜E（G）｜} with the property that the edge-weight set {f（x） ＋ f（xy） ＋ f（y） ｜ xy ∈ E（G）} is equal to {a, a ＋ d, a ＋ 2d,... ,a ＋ （｜E（G）｜ - 1）d} for two integers a 〉 0 and d ≥ 0. An （a,d）-edge- antimagic total labeling is called super if the smMlest possible labels appear on the vertices. In this paper, we completely settle the problem of the super （a, d）-edge-antimagic total labeling of the complete bipartite graph [（m,n and obtain the following results： the graph t（m,n has a super （a, d）-edge-antimagic total labeling if and only if either （i） m = 1, n = 1, and d ≥ 0, or （ii） m = 1, n≥2 （orn=1 and m≥2）,and d ∈{0,1,2},or （iii） m=l,n=2 （orn=1 and m = 2）, and d= 3, or （iv） m,n≥2, and d=1展开更多
Let G = （V, E） be a finite, simple and undirected graph with p vertices and q edges. An （a, d）-vertex-antimagic total labeling of G is a bijection f from V（G） t2 E（G） onto the set of consecutive integers 1, 2,...Let G = （V, E） be a finite, simple and undirected graph with p vertices and q edges. An （a, d）-vertex-antimagic total labeling of G is a bijection f from V（G） t2 E（G） onto the set of consecutive integers 1, 2,... ,p ＋ q, such that the vertex-weights form an arithmetic progression with the initial term a and difference d, where the vertex-weight of x is the sum of the value f（x） assigned to the vertex x together with all values f（xy） assigned to edges xy incident to x. Such labeling is called super if the smallest possible labels appear on the vertices. In this paper, we study the properties of such labelings and examine their existence for 2r-regular graphs when the difference d is 0, 1,..., r ＋ 1.展开更多
A labeling f of a graph G is a bijection from its edge set E（G） to the set {1, 2,……, E（G） }, which is antimagic if for any distinct vertices x and y, the sum of the labels on edges incident to x is different fro...A labeling f of a graph G is a bijection from its edge set E（G） to the set {1, 2,……, E（G） }, which is antimagic if for any distinct vertices x and y, the sum of the labels on edges incident to x is different from the sum of the labels on edges incident to y. A graph G is antimagic if G has an f which is antimagic. Hartsfield and Ringel conjectured in 1990 that every connected graph other than 2K is antimagic. In this paper, we show that some graphs with even factors are antimagic, which generalizes some known results.展开更多
基金Supported by National Natural Science Foundation of China(Grant Nos.61070230 and 11101243)Doctoral Fund of Ministry of Education of China(Grant No.20100131120017)the Scientific Research Foundation for the Excellent Middle-Aged and Young Scientists of Shandong Province(Grant No.BS2012SF016)
文摘An edge coloring total k-labeling is a labeling of the vertices and the edges of a graph G with labels {1,2,..., k} such that the weights of the edges define a proper edge coloring of G. Here the weight of an edge is the sum of its label and the labels of its two end vertices. This concept was introduce by Brandt et al. They defined Xt＇（G） to be the smallest integer k for which G has an edge coloring total k-labeling and proposed a question： Is there a constant K with X^t（G） ≤△（G）＋1/2 K for all graphs G of maximum degree A（G）？ In this paper, we give a positive answer for outerplanar graphs ≤△（G）＋1/2 by showing that X＇t（G） ≤△（G）＋1/2 for each outerplanar graph G with maximum degree A（G）.
文摘An （a, d）-edge-antimagic total labeling of a graph G is a bijection f from V（G） ∪ E（G） onto {1, 2,..., ｜V（G）｜ ＋ ｜E（G）｜} with the property that the edge-weight set {f（x） ＋ f（xy） ＋ f（y） ｜ xy ∈ E（G）} is equal to {a, a ＋ d, a ＋ 2d,... ,a ＋ （｜E（G）｜ - 1）d} for two integers a 〉 0 and d ≥ 0. An （a,d）-edge- antimagic total labeling is called super if the smMlest possible labels appear on the vertices. In this paper, we completely settle the problem of the super （a, d）-edge-antimagic total labeling of the complete bipartite graph [（m,n and obtain the following results： the graph t（m,n has a super （a, d）-edge-antimagic total labeling if and only if either （i） m = 1, n = 1, and d ≥ 0, or （ii） m = 1, n≥2 （orn=1 and m≥2）,and d ∈{0,1,2},or （iii） m=l,n=2 （orn=1 and m = 2）, and d= 3, or （iv） m,n≥2, and d=1
基金Supported by Slovak VEGA Grant 1/0130/12Higher Education Commission Pakistan (Grant No.HEC(FD)/2007/555)the Ministry of Education of the Czech Republic (Grant No. MSM6198910027)
文摘Let G = （V, E） be a finite, simple and undirected graph with p vertices and q edges. An （a, d）-vertex-antimagic total labeling of G is a bijection f from V（G） t2 E（G） onto the set of consecutive integers 1, 2,... ,p ＋ q, such that the vertex-weights form an arithmetic progression with the initial term a and difference d, where the vertex-weight of x is the sum of the value f（x） assigned to the vertex x together with all values f（xy） assigned to edges xy incident to x. Such labeling is called super if the smallest possible labels appear on the vertices. In this paper, we study the properties of such labelings and examine their existence for 2r-regular graphs when the difference d is 0, 1,..., r ＋ 1.
基金Supported by the National Natural Science Foundation of China(11371052,11271267,10971144,11101020)the Fundamental Research Fund for the Central Universities(2011B019,3142013104,3142014127 and 3142014037)the North China Institute of Science and Technology Key Discipline Items of Basic Construction(HKXJZD201402)
文摘A labeling f of a graph G is a bijection from its edge set E（G） to the set {1, 2,……, E（G） }, which is antimagic if for any distinct vertices x and y, the sum of the labels on edges incident to x is different from the sum of the labels on edges incident to y. A graph G is antimagic if G has an f which is antimagic. Hartsfield and Ringel conjectured in 1990 that every connected graph other than 2K is antimagic. In this paper, we show that some graphs with even factors are antimagic, which generalizes some known results.
