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

The total {k}-domatic number of wheels and complete graphs

Let k be a positive integer and let G be a graph with vertex set V(G). The total {k}-dominating function (T{k}DF) of a graph G is a function f from V(G) to the set {0,1,2,??,k}, such that for each vertex v??V(G), the sum of the values of all its neighbors assigned by f is at least k. A set {f ₁,f ₂,??,f _d } of pairwise different T{k}DFs of G with the property that $\sum_{i=1}^{d}f_{i}(v)\leq k$ for each v??V(G), is called a total {k}-dominating family (T{k}D family) of G. The total {k}-domatic number of a graph G, denoted by $d_{t}^{\{k\}}(G)$ , is the maximum number of functions in a T{k}D family. In this paper, we determine the exact values of the total {k}-domatic numbers of wheels and complete graphs, which answers an open problem of Sheikholeslami and Volkmann (J. Comb. Optim., 2010) and completes a result in the same paper.     

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.     

Group testing in graphs

This paper studies the group testing problem in graphs as follows. Given a graph G=(V,E), determine the minimum number t(G) such that t(G) tests are sufficient to identify an unknown edge e with each test specifies a subset X⊆V and answers whether the unknown edge e is in G[X] or not. Damaschke proved that ⌈log ₂ e(G)⌉≤t(G)≤⌈log ₂ e(G)⌉+1 for any graph G, where e(G) is the number of edges of G. While there are infinitely many complete graphs that attain the upper bound, it was conjectured by Chang and Hwang that the lower bound is attained by all bipartite graphs. Later, they proved that the conjecture is true for complete bipartite graphs. Chang and Juan verified the conjecture for bipartite graphs G with e(G)≤2⁴ or for k≥5. This paper proves the conjecture for bipartite graphs G with e(G)≤2⁵ or for k≥6. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. J.S.-t.J. is supported in part by the National Science Council under grant NSC89-2218-E-260-013. G.J.C. is supported in part by the National Science Council under grant NSC93-2213-E002-28. Taida Institute for Mathematical Sciences, National Taiwan University, Taipei 10617, Taiwan. National Center for Theoretical Sciences, Taipei Office.     

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.     

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.     

Approximation algorithms for connected facility location problems

We study Connected Facility Location problems. We are given a connected graph G=(V,E) with nonnegative edge cost c _e for each edge e∈E, a set of clients D⊆V such that each client j∈D has positive demand d _j and a set of facilities F⊆V each has nonnegative opening cost f _i and capacity to serve all client demands. The objective is to open a subset of facilities, say , to assign each client j∈D to exactly one open facility i(j) and to connect all open facilities by a Steiner tree T such that the cost is minimized for a given input parameter M≥1. We propose a LP-rounding based 8.29 approximation algorithm which improves the previous bound 8.55 (Swamy and Kumar in Algorithmica, 40:245–269, 2004). We also consider the problem when opening cost of all facilities are equal. In this case we give a 7.0 approximation algorithm.     

L(j,k)- and circular L(j,k)-labellings for the products of complete graphs

Let j and k be two positive integers with j≥k. An L(j,k)-labelling of a graph G is an assignment of nonnegative integers to the vertices of G such that the difference between labels of any two adjacent vertices is at least j, and the difference between labels of any two vertices that are at distance two apart is at least k. The minimum range of labels over all L(j,k)-labellings of a graph G is called the λ _j,k -number of G, denoted by λ _j,k (G). A σ(j,k)-circular labelling with span m of a graph G is a function f:V(G)→{0,1,…,m−1} 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 apart, where |x| _m =min {|x|,m−|x|}. The minimum m such that there exists a σ(j,k)-circular labelling with span m for G is called the σ _j,k -number of G and denoted by σ _j,k (G). The λ _j,k -numbers of Cartesian products of two complete graphs were determined by Georges, Mauro and Stein ((2000) SIAM J Discret Math 14:28–35). This paper determines the λ _j,k -numbers of direct products of two complete graphs and the σ _j,k -numbers of direct products and Cartesian products of two complete graphs. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. This work is partially supported by FRG, Hong Kong Baptist University, Hong Kong; NSFC, China, grant 10171013; and Southeast University Science Foundation grant XJ0607230.     

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.     

A 6.55 factor primal-dual approximation algorithm for the connected facility location problem

In the connected facility location (ConFL) problem, we are given a graph G=(V,E) with nonnegative edge cost c _e on the edges, a set of facilities ??V, a set of demands (i.e., clients) $\mathcal{D}\subseteq VIn the connected facility location (ConFL) problem, we are given a graph G=(V,E) with nonnegative edge cost c _e on the edges, a set of facilities ℱ⊆V, a set of demands (i.e., clients) D í V\mathcal{D}\subseteq V , and a parameter M≥1. Each facility i has a nonnegative opening cost f _i and each client j has d _j units of demand. Our objective is to open some facilities, say F⊆ℱ, assign each demand j to some open facility i(j)∈F and connect all open facilities using a Steiner tree T such that the total cost, which is ?_{i ? F}f_i+?_{j ? D}d_jc_i(j)j+M?_{e ? T}c_e\sum_{i\in F}f_{i}+\sum_{j\in \mathcal{D}}d_{j}c_{i(j)j}+M\sum_{e\in T}c_{e} , is minimized. We present a primal-dual 6.55-approximation algorithm for the ConFL problem which improves the previous primal-dual 8.55-approximation algorithm given by Swamy and Kumar (Algorithmica 40:245–269, 2004).     

Packing cycles exactly in polynomial time

Let G=(V,E) be an undirected graph in which every vertex v∈V is assigned a nonnegative integer w(v). A w-packing is a collection of cycles (repetition allowed) in G such that every v∈V is contained at most w(v) times by the members of . Let 〈w〉=2|V|+∑ _v∈V ⌈log (w(v)+1)⌉ denote the binary encoding length (input size) of the vector (w(v): v∈V) ^T . We present an efficient algorithm which finds in O(|V|⁸〈w〉²+|V|¹⁴) time a w-packing of maximum cardinality in G provided packing and covering cycles in G satisfy the ℤ₊-max-flow min-cut property.     

Pooling designs associated with unitary space and ratio efficiency comparison

Let \mathbbF^(2n+d)_q²\mathbb{F}^{(2\nu+\delta)}_{q^{2}} be a (2ν+δ)-dimensional unitary space of \mathbbF_q²\mathbb{F}_{q^{2}} , where δ=0 or 1. In this paper we construct a family of inclusion matrices associated with subspaces of \mathbbF^(2n+d)_q²\mathbb{F}^{(2\nu+\delta)}_{q^{2}} , and exhibit its disjunct property. Moreover, we compare the ratio efficiency of this construction with others, and find it smaller under some conditions.     

Lower bounds and a tabu search algorithm for the minimum deficiency problem

An edge coloring of a graph G=(V,E) is a function c:E→ℕ that assigns a color c(e) to each edge e∈E such that c(e)≠c(e′) whenever e and e′ have a common endpoint. Denoting S _v (G,c) the set of colors assigned to the edges incident to a vertex v∈V, and D _v (G,c) the minimum number of integers which must be added to S _v (G,c) to form an interval, the deficiency D(G,c) of an edge coloring c is defined as the sum ∑ _v∈V D _v (G,c), and the span of c is the number of colors used in c. The problem of finding, for a given graph, an edge coloring with a minimum deficiency is NP-hard. We give new lower bounds on the minimum deficiency of an edge coloring and on the span of edge colorings with minimum deficiency. We also propose a tabu search algorithm to solve the minimum deficiency problem and report experiments on various graph instances, some of them having a known optimal deficiency.     

On the total domination subdivision number in some classes of graphs

A set S of vertices of a graph G=(V,E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γ _t (G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sd_gt(G)\mathrm {sd}_{\gamma_{t}}(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. In this paper we prove that sd_gt(G) ￡ g_t(G)+1\mathrm {sd}_{\gamma_{t}}(G)\leq\gamma_{t}(G)+1 for some classes of graphs.     

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.     

The max quasi-independent set problem

In this paper, we deal with the problem of finding quasi-independent sets in graphs. This problem is formally defined in three versions, which are shown to be polynomially equivalent. The one that looks most general, namely, f-max quasi-independent set, consists of, given a graph and a non-decreasing function f, finding a maximum size subset Q of the vertices of the graph, such that the number of edges in the induced subgraph is less than or equal to f(|Q|). For this problem, we show an exact solution method that runs within time O^*(2^{\fracd-27/23d+1n})O^{*}(2^{\frac{d-27/23}{d+1}n}) on graphs of average degree bounded by d. For the most specifically defined γ-max quasi-independent set and k-max quasi-independent set problems, several results on complexity and approximation are shown, and greedy algorithms are proposed, analyzed and tested.     

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.     

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.     

Roman domination on strongly chordal graphs

Given real numbers b≥a>0, an (a,b)-Roman dominating function of a graph G=(V,E) is a function f:V→{0,a,b} such that every vertex v with f(v)=0 has a neighbor u with f(u)=b. An independent/connected/total (a,b)-Roman dominating function is an (a,b)-Roman dominating function f such that {v∈V:f(v)≠0} induces a subgraph without edges/that is connected/without isolated vertices. For a weight function $w{:} V\to\Bbb{R}$ , the weight of f is w(f)=∑ _v∈V w(v)f(v). The weighted (a,b)-Roman domination number $\gamma^{(a,b)}_{R}(G,w)$ is the minimum weight of an (a,b)-Roman dominating function of G. Similarly, we can define the weighted independent (a,b)-Roman domination number $\gamma^{(a,b)}_{Ri}(G,w)$ . In this paper, we first prove that for any fixed (a,b) the (a,b)-Roman domination and the total/connected/independent (a,b)-Roman domination problems are NP-complete for bipartite graphs. We also show that for any fixed (a,b) the (a,b)-Roman domination and the total/connected/weighted independent (a,b)-Roman domination problems are NP-complete for chordal graphs. We then give linear-time algorithms for the weighted (a,b)-Roman domination problem with b≥a>0, and the weighted independent (a,b)-Roman domination problem with 2a≥b≥a>0 on strongly chordal graphs with a strong elimination ordering provided.