Circular L(j,k)-labeling number of direct product of path and cycle

Let j, k and m be positive numbers, a circular m-L(j,k)-labeling of a graph G is a function f:V(G)→[0,m) such that |f(u)?f(v)| _m ≥j if u and v are adjacent, and |f(u)?f(v)| _m ≥k if u and v are at distance two, where |a?b| _m =min{|a?b|,m?|a?b|}. The minimum m such that there exist a circular m-L(j,k)-labeling of G is called the circular L(j,k)-labeling number of G and is denoted by σ _j,k (G). In this paper, for any two positive numbers j and k with j≤k, we give some results about the circular L(j,k)-labeling number of direct product of path and cycle.     

Multiple L(j,1)-labeling of the triangular lattice

Let n,j,k be nonnegative integers. An n-fold L(j,k)-labeling of a graph G is an assignment f of sets of nonnegative integers of order n to the vertices of G such that, for any two vertices u,v and any two integers a∈f(u), b∈f(v), |a?b|≥j if uv∈E(G), and |a?b|≥k if u and v are distance two apart. The span of f is the absolute difference between the maximum and minimum integers used by f. The n-fold L(j,k)-labeling number of G is the minimum span over all n-fold L(j,k)-labelings of G. Let n,j,k and m be nonnegative integers. An n-fold circular m-L(j,k)-labeling of a graph G is an assignment f of subsets of {0,1,…,m?1} of order n to the vertices of G such that, for any two vertices u,v and any two integers a∈f(u), b∈f(v), min{|a?b|,m?|a?b|}≥j if uv∈E(G), and min{|a?b|,m?|a?b|}≥k if u and v are distance two apart. The minimum m such that G has an n-fold circular m-L(j,k)-labeling is called the n-fold circular L(j,k)-labeling number of G. This paper provides upper and lower bounds for the n-fold L(j,1)-labeling number and the n-fold circular L(j,1)-labeling number of the triangular lattice and determines the n-fold L(2,1)-labeling number and n-fold circular L(2,1)-labeling number of the triangular lattice for n≥3.     

Restricted domination parameters in graphs

In a graph G, a vertex dominates itself and its neighbors. A subset S ⊂eqV(G) is an m-tuple dominating set if S dominates every vertex of G at least m times, and an m-dominating set if S dominates every vertex of G−S at least m times. The minimum cardinality of a dominating set is γ, of an m-dominating set is γ _m , and of an m-tuple dominating set is mtupledom. For a property π of subsets of V(G), with associated parameter f_π, the k-restricted π-number r _k (G,f_π) is the smallest integer r such that given any subset K of (at most) k vertices of G, there exists a π set containing K of (at most) cardinality r. We show that for 1< k < n where n is the order of G: (a) if G has minimum degree m, then r _k (G,γ _m ) < (mn+k)/(m+1); (b) if G has minimum degree 3, then r _k (G,γ) < (3n+5k)/8; and (c) if G is connected with minimum degree at least 2, then r _k (G,ddom) < 3n/4 + 2k/7. These bounds are sharp. Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.     

On the equitable k *-laceability of hypercubes

Let G be a finite undirected bipartite graph. Let u, v be two vertices of G from different partite sets. A collection of k internal vertex disjoint paths joining u to v is referred as a k-container C _k (u,v). A k-container is a k ^*-container if it spans all vertices of G. We define G to be a k ^*-laceable graph if there is a k ^*-container joining any two vertices from different partite sets. A k ^*-container C _k ^*(u,v)={P ₁,…,P _k } is equitable if ||V(P _i )|−|V(P _j )||≤2 for all 1≤i,j≤k. A graph is equitably k ^*-laceable if there is an equitable k ^*-container joining any two vertices in different partite sets. Let Q _n be the n-dimensional hypercube. In this paper, we prove that the hypercube Q _n is equitably k ^*-laceable for all k≤n−4 and n≥5. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. The work of H.-M. Huang was supported in part by the National Science Council of the Republic of China under NSC94-2115-M008-013.     

On backbone coloring of graphs

Let G be a graph and H a subgraph of G. A backbone-k-coloring of (G,H) is a mapping f: V(G)→{1,2,…,k} such that |f(u)−f(v)|≥2 if uv∈E(H) and |f(u)−f(v)|≥1 if uv∈E(G)\E(H). The backbone chromatic number of (G,H) is the smallest integer k such that (G,H) has a backbone-k-coloring. In this paper, we characterize the backbone chromatic number of Halin graphs G=T∪C with respect to given spanning trees T. Also we study the backbone coloring for other special graphs such as complete graphs, wheels, graphs with small maximum average degree, graphs with maximum degree 3, etc.     

The total {k}-domatic number of a graph

For a positive integer k, a total {k}-dominating function of a graph G is a function f from the vertex set V(G) to the set {0,1,2,…,k} such that for any vertex v∈V(G), the condition ∑ _u∈N(v) f(u)≥k is fulfilled, where N(v) is the open neighborhood of v. A set {f ₁,f ₂,…,f _d } of total {k}-dominating functions on G with the property that ?_i=1^df_i(v) ￡ k\sum_{i=1}^{d}f_{i}(v)\le k for each v∈V(G), is called a total {k}-dominating family (of functions) on G. The maximum number of functions in a total {k}-dominating family on G is the total {k}-domatic number of G, denoted by d_t^{k}(G)d_{t}^{\{k\}}(G). Note that d_t^{1}(G)d_{t}^{\{1\}}(G) is the classic total domatic number d _t (G). In this paper we initiate the study of the total {k}-domatic number in graphs and we present some bounds for d_t^{k}(G)d_{t}^{\{k\}}(G). Many of the known bounds of d _t (G) are immediate consequences of our results.     

The L(2,1)-labelling problem for cubic Cayley graphs on dihedral groups

A k-L(2,1)-labelling of a graph G is a mapping f:V(G)→{0,1,2,…,k} such that |f(u)?f(v)|≥2 if uv∈E(G) and f(u)≠f(v) if u,v are distance two apart. The smallest positive integer k such that G admits a k-L(2,1)-labelling is called the λ-number of G. In this paper we study this quantity for cubic Cayley graphs (other than the prism graphs) on dihedral groups, which are called brick product graphs or honeycomb toroidal graphs. We prove that the λ-number of such a graph is between 5 and 7, and moreover we give a characterisation of such graphs with λ-number 5.     

Finding the anti-block vital edge of a shortest path between two nodes

Let P _G (s,t) denote a shortest path between two nodes s and t in an undirected graph G with nonnegative edge weights. A detour at a node u∈P _G (s,t)=(s,…,u,v,…,t) is defined as a shortest path P _G−e (u,t) from u to t which does not make use of (u,v). In this paper, we focus on the problem of finding an edge e=(u,v)∈P _G (s,t) whose removal produces a detour at node u such that the ratio of the length of P _G−e (u,t) to the length of P _G (u,t) is maximum. We define such an edge as an anti-block vital edge (AVE for short), and show that this problem can be solved in O(mn) time, where n and m denote the number of nodes and edges in the graph, respectively. Some applications of the AVE for two special traffic networks are shown. This research is supported by NSF of China under Grants 70471035, 70525004, 701210001 and 60736027, and PSF of China under Grant 20060401003.     

A study on cyclic bandwidth sum

Suppose G is a graph of p vertices. A proper labeling f of G is a one-to-one mapping f:V(G)→{1,2,…,p}. The cyclic bandwidth sum of G with respect to f is defined by CBS _f (G)=∑ _uv∈E(G)|f(v)−f(u)| _p , where |x| _p =min {|x|,p−|x|}. The cyclic bandwidth sum of G is defined by CBS(G)=min {CBS _f (G): f is a proper labeling of G}. The bandwidth sum of G with respect to f is defined by BS _f (G)=∑ _uv∈E(G)|f(v)−f(u)|. The bandwidth sum of G is defined by BS(G)=min {BS _f (G): f is a proper labeling of G}. In this paper, we give a necessary and sufficient condition for BS(G)=CBS(G), and use this to show that BS(T)=CBS(T) when T is a tree. We also find cyclic bandwidth sums of complete bipartite graphs. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. Supported in part by the National Science Council under grants NSC91-2115-M-156-001.     

Point sets in the unit square and large areas of convex hulls of subsets of points

In this paper generalizations of Heilbronn’s triangle problem to convex hulls of j points in the unit square [0,1]² are considered. By using results on the independence number of linear hypergraphs, for fixed integers k≥3 and any integers n≥k a deterministic o(n ^6k−4) time algorithm is given, which finds distributions of n points in [0,1]² such that, simultaneously for j=3,…,k, the areas of the convex hulls determined by any j of these n points are Ω((log n)^1/(j−2)/n ^{(j−1)/(j−2)}).     

On the total {k}-domination number of Cartesian products of graphs

Let γ _t ^{k}(G) denote the total {k}-domination number of graph G, and let denote the Cartesian product of graphs G and H. In this paper, we show that for any graphs G and H without isolated vertices, . As a corollary of this result, we have for all graphs G and H without isolated vertices, which is given by Pak Tung Ho (Util. Math., 2008, to appear) and first appeared as a conjecture proposed by Henning and Rall (Graph. Comb. 21:63–69, 2005). The work was supported by NNSF of China (No. 10701068 and No. 10671191).     

L(d,1)-labelings of the edge-path-replacement of a graph

For two positive integers j and k with j≥k, an L(j,k)-labeling of a graph G is an assignment of nonnegative integers to V(G) such that the difference between labels of adjacent vertices is at least j, and the difference between labels of vertices that are distance two apart is at least k. The span of an L(j,k)-labeling of a graph G is the difference between the maximum and minimum integers used by it. The L(j,k)-labelings-number of G is the minimum span over all L(j,k)-labelings of G. This paper focuses on L(d,1)-labelings-number of the edge-path-replacement G(P _k ) of a graph G. Note that G(P ₃) is the incidence graph of G. L(d,1)-labelings of the edge-path-replacement G(P _k ) of a graph, called (d,1)-total labeling of G, was introduced in 2002 by Havet and Yu (Workshop graphs and algorithms, 2003; Discrete Math 308:493–513, 2008). Havet and Yu (Discrete Math 308:498–513, 2008) obtained the bound $\Delta+ d-1\leq\lambda^{T}_{d}(G)\leq2\Delta+ d-1$ and conjectured $\lambda^{T}_{d}(G)\leq\Delta+2d-1$ . In (Lü in J Comb Optim, to appear; Zhejiang University, submitted), we worked on L(2,1)-labelings-number and L(1,1)-labelings-number of the edge-path-replacement G(P _k ) of a graph G, and obtained that λ(G(P _k ))≤Δ+2 for k≥5, and conjecture λ(G(P ₄))≤Δ+2 for any graph G with maximum degree Δ. In this paper, we will study L(d,1)-labelings-number of the edge-path-replacement G(P _k ) of a graph G for d≥3 and k≥4.     

Distance two edge labelings of lattices

Suppose G is a graph. Two edges e and e′ in G are said to be adjacent if they share a common end vertex, and distance two apart if they are nonadjacent but both are adjacent to a common edge. Let j and k be two positive integers. An L(j,k)-edge-labeling of a graph G is an assignment of nonnegative integers, called labels, to the edges of G such that the difference between labels of any two adjacent edges is at least j, and the difference between labels of any two edges that are distance two apart is at least k. The minimum range of labels over all L(j,k)-edge-labelings of a graph G is called the L(j,k)-edge-labeling number of G, denoted by $\lambda_{j,k}'(G)$ . Let m, j and k be positive integers. An m-circular-L(j,k)-edge-labeling of a graph G is an assignment f from {0,1,…,m?1} to the edges of G such that, for any two edges e and e′, |f(e)?f(e′)| _m ≥j if e and e′ are adjacent, and |f(e)?f(e′)| _m ≥k if e and e′ are distance two apart, where |a| _m =min{a,m?a}. The minimum m such that G has an m-circular-L(j,k)-edge-labeling is called the circular-L(j,k)-edge-labeling number of G, denoted by $\sigma_{j,k}'(G)$ . This paper investigates the L(1,1)-edge-labeling numbers, the L(2,1)-edge-labeling numbers and the circular-L(2,1)-edge-labeling numbers of the hexagonal lattice, the square lattice, the triangular lattice and the strong product of two infinite paths.     

L(2,1)-labelings of the edge-path-replacement of a graph

For two positive integers j and k with j≥k, an L(j,k)-labeling of a graph G is an assignment of nonnegative integers to V(G) such that the difference between labels of adjacent vertices is at least j, and the difference between labels of vertices that are distance two apart is at least k. The span of an L(j,k)-labeling of a graph G is the difference between the maximum and minimum integers used by it. The L(j,k)-labelings-number of G is the minimum span over all L(j,k)-labelings of G. This paper focuses on L(2,1)-labelings-number of the edge-path-replacement G(P _k ) of a graph G. Note that G(P ₃) is the incidence graph of G. L(2,1)-labelings of the edge-path-replacement G(P ₃) of a graph, called (2,1)-total labeling of G, was introduced by Havet and Yu in 2002 (Workshop graphs and algorithms, Dijon, France, 2003; Discrete Math. 308:498–513, 2008). They (Havet and Yu, Discrete Math. 308:498–513, 2008) obtain the bound $\Delta+1\leq\lambda^{T}_{2}(G)\leq2\Delta+1$ and conjectured $\lambda^{T}_{2}(G)\leq\Delta+3$ . In this paper, we obtain that λ(G(P _k ))≤Δ+2 for k≥5, and conjecture λ(G(P ₄))≤Δ+2 for any graph G with maximum degree Δ.     

On total weight choosability of graphs

For a graph G with vertex set V and edge set E, a (k,k′)-total list assignment L of G assigns to each vertex v a set L(v) of k real numbers as permissible weights, and assigns to each edge e a set L(e) of k′ real numbers as permissible weights. If for any (k,k′)-total list assignment L of G, there exists a mapping f:V∪E→? such that f(y)∈L(y) for each y∈V∪E, and for any two adjacent vertices u and v, ∑ _y∈N(u) f(uy)+f(u)≠∑ _x∈N(v) f(vx)+f(v), then G is (k,k′)-total weight choosable. It is conjectured by Wong and Zhu that every graph is (2,2)-total weight choosable, and every graph with no isolated edges is (1,3)-total weight choosable. In this paper, it is proven that a graph G obtained from any loopless graph H by subdividing each edge with at least one vertex is (1,3)-total weight choosable and (2,2)-total weight choosable. It is shown that s-degenerate graphs (with s≥2) are (1,2s)-total weight choosable. Hence planar graphs are (1,10)-total weight choosable, and outerplanar graphs are (1,4)-total weight choosable. We also give a combinatorial proof that wheels are (2,2)-total weight choosable, as well as (1,3)-total weight choosable.     

On minimum <Emphasis Type="Italic">m</Emphasis>-connected <Emphasis Type="Italic">k</Emphasis>-dominating set problem in unit disc graphs

Minimum m-connected k-dominating set problem is as follows: Given a graph G=(V,E) and two natural numbers m and k, find a subset S⊆V of minimal size such that every vertex in V∖S is adjacent to at least k vertices in S and the induced graph of S is m-connected. In this paper we study this problem with unit disc graphs and small m, which is motivated by the design of fault-tolerant virtual backbone for wireless sensor networks. We propose two approximation algorithms with constant performance ratios for m≤2. We also discuss how to design approximation algorithms for the problem with arbitrarily large m. This work was supported in part by the Research Grants Council of Hong Kong under Grant No. CityU 1165/04E, the National Natural Science Foundation of China under Grant No. 70221001, 10531070 and 10771209.     

Super cyclically edge connected transitive graphs

A cyclic edge-cut of a graph G is an edge set, the removal of which separates two cycles. If G has a cyclic edge-cut, then it is called cyclically separable. For a cyclically separable graph G, the cyclic edge-connectivity λ _c (G) is the cardinality of a minimum cyclic edge-cut of G. We call a graph super cyclically edge-connected, if the removal of any minimum cyclic edge-cut results in a component which is a shortest cycle. In this paper, we show that a connected vertex-transitive or edge-transitive graph is super cyclically edge-connected if either G is cubic with girth g(G)≥7, or G has minimum degree δ(G)≥4 and girth g(G)≥6.     

Near automorphisms of trees with small total relative displacements

For a permutation f of the vertex set V(G) of a connected graph G, let δ _f (x,y)=|d(x,y)−d(f(x),f(y))|. Define the displacement δ _f (G) of G with respect to f to be the sum of δ _f (x,y) over all unordered pairs {x,y} of distinct vertices of G. Let π(G) denote the smallest positive value of δ _f (G) among the n! permutations f of V(G). In this note, we determine all trees T with π(T)=2 or 4. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday.     

On the distance paired domination of generalized Petersen graphs <Emphasis Type="Italic">P</Emphasis>(<Emphasis Type="Italic">n</Emphasis>,1) and <Emphasis Type="Italic">P</Emphasis>(<Emphasis Type="Italic">n</Emphasis>,2)

Let G=(V,E) be a graph without an isolated vertex. A set D⊆V(G) is a k -distance paired dominating set of G if D is a k-distance dominating set of G and the induced subgraph 〈D〉 has a perfect matching. The minimum cardinality of a k-distance paired dominating set for graph G is the k -distance paired domination number, denoted by γ _p ^k (G). In this paper, we determine the exact k-distance paired domination number of generalized Petersen graphs P(n,1) and P(n,2) for all k≥1.     

Integer-magic spectra of sun graphs

Let A be a non-trivial Abelian group. A graph G=(V,E) is A-magic if there exists a labeling f:E→A∖{0} such that the induced vertex set labeling f ⁺:V→A, defined by f ⁺(v)=∑f(uv) where the sum is over all uv∈E, is a constant map. The integer-magic spectrum of a graph G is the set IM(G)={k∈ℕ∣G is ℤ _k -magic}. A sun graph is obtained from an n-cycle, by attaching paths to each pair of adjacent vertices in the cycle. In this paper, we investigate the integer-magic spectra of some sun graphs. Dedicated to Prof. Frank K. Hwang, on the occasion of his 65th birthday. Supported by Faculty Research Grant, Hong Kong Baptist University.