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.     

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.     

Finding an anti-risk path between two nodes in undirected graphs

Given a weighted graph G=(V,E) with a source s and a destination t, a traveler has to go from s to t. However, some of the edges may be blocked at certain times, and the traveler only observes that upon reaching an adjacent site of the blocked edge. Let ℘={P _G (s,t)} be the set of all paths from s to t. The risk of a path is defined as the longest travel under the assumption that any edge of the path may be blocked. The paper will propose the Anti-risk Path Problem of finding a path P _G (s,t) in ℘ such that it has minimum risk. We will show that this problem can be solved in O(mn+n ²log n) time suppose that at most one edge may be blocked, where n and m denote the number of vertices and edges in G, respectively. This research is supported by NSF of China under Grants 70525004, 60736027, 70121001 and Postdoctoral Science Foundation of China under Grant 20060401003.     

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.     

Approximation algorithms and hardness results for labeled connectivity problems

Let G=(V,E) be a connected multigraph, whose edges are associated with labels specified by an integer-valued function ℒ:E→ℕ. In addition, each label ℓ∈ℕ has a non-negative cost c(ℓ). The minimum label spanning tree problem (MinLST) asks to find a spanning tree in G that minimizes the overall cost of the labels used by its edges. Equivalently, we aim at finding a minimum cost subset of labels I⊆ℕ such that the edge set {e∈E:ℒ(e)∈I} forms a connected subgraph spanning all vertices. Similarly, in the minimum label s – t path problem (MinLP) the goal is to identify an s–t path minimizing the combined cost of its labels. The main contributions of this paper are improved approximation algorithms and hardness results for MinLST and MinLP.     

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.     

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.     

On cubic 2-independent Hamiltonian connected graphs

A graph G=(V,E) is Hamiltonian connected if there exists a Hamiltonian path between any two vertices in G. Let P ₁=(u ₁,u ₂,…,u _|V|) and P ₂=(v ₁,v ₂,…,v _|V|) be any two Hamiltonian paths of G. We say that P ₁ and P ₂ are independent if u ₁=v ₁,u _|V|=v _|V|, and u _i ≠v _i for 1<i<|V|. A cubic graph G is 2-independent Hamiltonian connected if there are two independent Hamiltonian paths between any two different vertices of G. A graph G is 1-Hamiltonian if G−F is Hamiltonian for any F⊆V∪E with |F|=1. A graph G is super 3^*-connected if there exist i internal disjoint paths spanning G for i=1,2,3. It is proved that every super 3^*-connected graph is 1-Hamiltonian. In this paper, we prove that every cubic 2-independent Hamiltonian connected graph is also 1-Hamiltonian. We present some cubic 2-independent Hamiltonian connected graphs that are super 3^*-connected, some cubic 2-independent Hamiltonian connected graphs that are not super 3^*-connected, some super 3^*-connected graphs that are not 2-independent Hamiltonian connected, and some cubic 1-Hamiltonian graphs that are Hamiltonian connected but neither 2-independent Hamiltonian connected nor super 3^*-connected. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. This work was supported in part by the National Science Council of the Republic of China under Contract NSC 94-2213-E-233-011.     

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.     

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

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.     

An Edge-Splitting Algorithm in Planar Graphs

For a multigraph G = (V, E), let s V be a designated vertex which has an even degree, and let _G (V – s) denote min{c _G(X) | Ø X V – s}, where c _G(X) denotes the size of cut X. Splitting two adjacent edges (s, u) and (s, v) means deleting these edges and adding a new edge (u, v). For an integer k, splitting two edges e ₁ and e ₂ incident to s is called (k, s)-feasible if _G(V – s) k holds in the resulting graph G. In this paper, we prove that, for a planar graph G and an even k or k = 3 with k _G (V – s), there exists a complete (k, s)-feasible splitting at s such that the resulting graph G is still planar, and present an O(n ³ log n) time algorithm for finding such a splitting, where n = |V|. However, for every odd k 5, there is a planar graph G with a vertex s which has no complete (k, s)-feasible and planarity-preserving splitting. As an application of this result, we show that for an outerplanar graph G and an even integer k the problem of optimally augmenting G to a k-edge-connected planar graph can be solved in O(n ³ log n) time.     

Strongly chordal and chordal bipartite graphs are sandwich monotone

A graph class is sandwich monotone if, for every pair of its graphs G ₁=(V,E ₁) and G ₂=(V,E ₂) with E ₁⊂E ₂, there is an ordering e ₁,…,e _k of the edges in E ₂∖E ₁ such that G=(V,E ₁∪{e ₁,…,e _i }) belongs to the class for every i between 1 and k. In this paper we show that strongly chordal graphs and chordal bipartite graphs are sandwich monotone, answering an open question by Bakonyi and Bono (Czechoslov. Math. J. 46:577–583, 1997). So far, very few classes have been proved to be sandwich monotone, and the most famous of these are chordal graphs. Sandwich monotonicity of a graph class implies that minimal completions of arbitrary graphs into that class can be recognized and computed in polynomial time. For minimal completions into strongly chordal or chordal bipartite graphs no polynomial-time algorithm has been known. With our results such algorithms follow for both classes. In addition, from our results it follows that all strongly chordal graphs and all chordal bipartite graphs with edge constraints can be listed efficiently.     

A fast exact algorithm for the problem of optimum cooperation and the structure of its solutions

Given a graph G=(V,E) with edge weights w _e ∈ℝ, the optimum cooperation problem consists in determining a partition of the graph that maximizes the sum of weights of the edges with nodes in the same class plus the number of the classes of the partition. The problem is also known in the literature as the optimum attack problem in networks. Furthermore, a relevant physics application exists.     

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.     

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.     

On the union of intermediate nodes of shortest paths

Consider a connected graph G=(V,E). For a pair of nodes u and v, denote by M _uv the set of intermediate nodes of a shortest path between u and v. We are intertested in minimization of the union ? _u,v∈V M _uv . We will show that this problem is NP-hard and cannot have polynomial-time ρlnδ-approximation for 0<ρ<1 unless NP?DTIME(n ^O(loglogn)) where δ is the maximum node degree of input graph. We will also construct a polynomial-time $H(\frac{\delta (\delta -1)}{2})$ -approximation for the problem where H(?) is the harmonic function.     

On the upper total domination number of Cartesian products of graphs

In this paper we continue the investigation of total domination in Cartesian products of graphs first studied in (Henning, M.A., Rall, D.F. in Graphs Comb. 21:63–69, 2005). A set S of vertices in a graph G is a total dominating set of G if every vertex in G is adjacent to some vertex in S. The maximum cardinality of a minimal total dominating set of G is the upper total domination number of G, denoted by Γ _t (G). We prove that the product of the upper total domination numbers of any graphs G and H without isolated vertices is at most twice the upper total domination number of their Cartesian product; that is, Γ _t (G)Γ _t (H)≤2Γ _t (G □ H). Research of M.A. Henning supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.