TITLE

L(p, q)-Labeling and Integer Flow on Planar Graphs

AUTHOR(S)
Zhang, Xiaoling; Qian, Jianguo
PUB. DATE
June 2013
SOURCE
Computer Journal;Jun2013, Vol. 56 Issue 6, p785
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
Given a graph G and two non-negative integers p and q, an L(p, q)-labeling c of G is an assignment of non-negative integers to the vertices of G such that, for any two vertices u and v, c(u) − c(v) ≥ p if d(u, v)=1 and c(u) − c(v) ≥ q if d(u, v)=2. The L(p, q)-labeling problem arises from a variation of the channel assignment problem. We establish a connection between the L(p, q)-labeling of the planar graph G and the integer flow on the dual graph of G. This provides us with an alternative and potentially more effective way to minimize the edge span of L(p, q)-labelings for planar graphs by using a graph flow approach. As examples, we apply this approach to determine the minimum edge spans of the L(p, q)-labelings for some typical finite planar lattices, including the square lattice, triangular lattice, hexagonal lattice as well as some other lattices consisting of various regular polygons, some of which arise from the design of planar regions for cellular phone networks. Our flow-based approach is also expected to have some further applications in optimizing the other measures for the L(p, q)-labeling problem.
ACCESSION #
87988119

 

Related Articles

  • Graphs with no K3,3 Minor Containing a Fixed Edge. Wagner, Donald K. // International Journal of Combinatorics;2013, p1 

    It is well known that every cycle of a graph must intersect every cut in an even number of edges. For planar graphs, Ford and Fulkerson proved that, for any edge e, there exists a cycle containing e that intersects every minimal cut containing e in exactly two edges. The main result of this...

  • A sufficient condition for planar graphs with maximum degree 8 to be 9-totally colorable. Cai, Jian; Teng, Chang; Yan, Gui // Acta Mathematica Sinica;Jun2014, Vol. 30 Issue 6, p993 

    A total k-coloring of a graph G is a coloring of V ( G) ∪ E( G) using k colors such that no two adjacent or incident elements receive the same color. The total chromatic number χ″( G) is the smallest integer k such that G has a total k-coloring. It is known that if a planar graph...

  • STRONG CHROMATIC INDEX OF PLANAR GRAPHS WITH LARGE GIRTH. CHANG, GERARD JENNHWA; MONTASSIER, MICKAEL; PÊCHER, ARNAUD; RASPAUD, ANDRÉ // Discussiones Mathematicae: Graph Theory;2014, Vol. 34 Issue 4, p723 

    Let Δ ≥ 4 be an integer. In this note, we prove that every planar graph with maximum degree Δ and girth at least 10Δ + 46 is strong (2Δ - 1)-edge-colorable, that is best possible (in terms of number of colors) as soon as G contains two adjacent vertices of degree Δ....

  • A MINIMAL PLANAR POINT SET CONTAINING A DISJOINT TRIPLE OF A 3-HOLE, A 4-HOLE AND A 5-HOLE. Liping Wu; Wanbing Lu // Far East Journal of Applied Mathematics;May2014, Vol. 87 Issue 2, p123 

    A subset of a finite set of points in the plane is called an empty convex polygon or a hole if it forms the set of vertices of a convex polygon whose interior contains no points of the set. Let n(k, l, s) be the smallest integer such that any set of n(k, l, s) points in the plane, no three...

  • r-REGULAR r-CONNECTED GRAPHS WITH LARGE GIRTH. Yoshimi Egawa // Advances & Applications in Discrete Mathematics;Oct2013, Vol. 12 Issue 2, p163 

    We show that for any integers r, g with r ≥ 2 and g ≥ 3, there exists an r-regular r-connected graph having girth at least g.

  • Computing Cartograms with Optimal Complexity. Alam, Md. Jawaherul; Biedl, Therese; Felsner, Stefan; Kaufmann, Michael; Kobourov, Stephen G.; Ueckerdt, Torsten // Discrete & Computational Geometry;Oct2013, Vol. 50 Issue 3, p784 

    In a rectilinear dual of a planar graph vertices are represented by simple rectilinear polygons, while edges are represented by side-contact between the corresponding polygons. A rectilinear dual is called a cartogram if the area of each region is equal to a pre-specified weight. The complexity...

  • A MINIMAL PLANAR POINT SET CONTAINING A DISJOINT PAIR OF A CONVEX 4-GON AND A CONVEX 6-GON. Liping Wu; Wanbing Lu // Advances & Applications in Discrete Mathematics;Oct2013, Vol. 12 Issue 2, p119 

    Let N(k, l) be the smallest positive integer such that any set of N(k, l) points in general position in the plane contains a disjoint pair of a convex k-gon and a convex l-gon. In this paper, we mainly prove that 17 ≤ N(4, 6) ≤ 21.

  • Constructions of Large Graphs on Surfaces. Feria-Puron, Ramiro; Pineda-Villavicencio, Guillermo // Graphs & Combinatorics;Jul2014, Vol. 30 Issue 4, p895 

    We consider the degree/diameter problem for graphs embedded in a surface, namely, given a surface Σ and integers Δ and k, determine the maximum order N(Δ, k,Σ) of a graph embeddable in Σ with maximum degree Δ and diameter k. We introduce a number of constructions which...

  • Edge coloring by total labelings of outerplanar graphs. Wang, Guang Hui; Yan, Gui Ying // Acta Mathematica Sinica;Nov2013, Vol. 29 Issue 11, p2129 

    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...

Share

Read the Article

Courtesy of VIRGINIA BEACH PUBLIC LIBRARY AND SYSTEM

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics