Three conjectures on the signed cycle domination in graphs

Let G=(V,E) be a graph, a function g:E→{?1,1} is said to be a signed cycle dominating function (SCDF for short) of G if ∑ _e∈E(C) g(e)≥1 holds for any induced cycle C of G. The signed cycle domination number of G is defined as γ _sc (G)=min{∑ _e∈E(G) g(e)∣g is an SCDF of G}. Xu (Discrete Math. 309:1007–1012, 2009) first researched the signed cycle domination number of graphs and raised the following conjectures: (1) Let G be a maximal planar graphs of order n≥3. Then γ _sc (G)=n?2; (2) For any graph G with δ(G)=3, γ _sc (G)≥1; (3) For any 2-connected graph G, γ _sc (G)≥1. In this paper, we present some results about these conjectures.     

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.     

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.     

Profile minimization on compositions of graphs

The profile minimization problem arose from the study of sparse matrix technique. In terms of graphs, the problem is to determine the profile of a graph G which is defined as $$P(G)=\min\limits_{f}\sum\limits_{v\in V(G)}\max\limits_{x\in N[v]}(f(v)-f(x)),$$ where f runs over all bijections from V(G) to {1,2,…,|V(G)|} and N[v]={v}∪{x∈V(G):xv∈E(G)}. This is equivalent to the interval graph completion problem, which is to find a super-graph of a graph G with as few number of edges as possible. The purpose of this paper is to study the profiles of compositions of two graphs.     

The broadcast median problem in heterogeneous postal model

We propose the problem of finding broadcast medians in heterogeneous networks. A heterogeneous network is represented by a graph G=(V,E), in which each edge has a weight that denotes the communication time between its two end vertices. The overall delay of a vertex v∈V(G), denoted as b(v,G), is the minimum sum of the communication time required to send a message from v to all vertices in G. The broadcast median problem consists of finding the set of vertices v∈V(G) with minimum overall delay b(v,G) and determining the value of b(v,G). In this paper, we consider the broadcast median problem following the heterogeneous postal model. Assuming that the underlying graph G is a general graph, we show that computing b(v,G) for an arbitrary vertex v∈V(G) is NP-hard. On the other hand, assuming that G is a tree, we propose a linear time algorithm for the broadcast median problem in heterogeneous postal model.     

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.     

On the mod sum number of H m,n

Let N denote the set of all positive integers. The sum graph G ⁺(S) of a finite subset S?N is the graph (S,E) with uv∈E if and only if u+v∈S. A graph G is said to be an mod sum graph if it is isomorphic to the sum graph of some S?Z _M \{0} and all arithmetic performed modulo M where M≥|S|+1. The mod sum number ρ(G) of G is the smallest number of isolated vertices which when added to G result in a mod sum graph. It is known that the graphs H _m,n (n>m≥3) are not mod sum graphs. In this paper we show that H _m,n are not mod sum graphs for m≥3 and n≥3. Additionally, we prove that ρ(H _m,3)=m for m≥3, H _m,n ∪ρK ₁ is exclusive for m≥3 and n≥4 and $m(n-1) \leq \rho(H_{m,n})\leq \frac{1}{2} mn(n-1)$ for m≥3 and n≥4.     

The minimum vulnerability problem on specific graph classes

Suppose that each edge e of an undirected graph G is associated with three nonnegative integers \(\mathsf{cost}(e)\), \(\mathsf{vul}(e)\) and \(\mathsf{cap}(e)\), called the cost, vulnerability and capacity of e, respectively. Then, we consider the problem of finding \(k\) paths in G between two prescribed vertices with the minimum total cost; each edge e can be shared without any cost by at most \(\mathsf{vul}(e)\) paths, and can be shared by more than \(\mathsf{vul}(e)\) paths if we pay \(\mathsf{cost}(e)\), but cannot be shared by more than \(\mathsf{cap}(e)\) paths even if we pay the cost for e. This problem generalizes the disjoint path problem, the minimum shared edges problem and the minimum edge cost flow problem for undirected graphs, and it is known to be NP-hard. In this paper, we study the problem from the viewpoint of specific graph classes, and give three results. We first show that the problem is NP-hard even for bipartite outerplanar graphs, 2-trees, graphs with pathwidth two, complete bipartite graphs, and complete graphs. We then give a pseudo-polynomial-time algorithm for bounded treewidth graphs. Finally, we give a fixed-parameter algorithm for chordal graphs when parameterized by the number \(k\) of required paths.     

Generalized perfect domination in graphs

Let k be a positive integer and G=(V,E) be a graph. A vertex subset D of a graph G is called a perfect k-dominating set of G, if every vertex v of G, not in D, is adjacent to exactly k vertices of D. The minimum cardinality of a perfect k-dominating set of G is the perfect k-domination number γ _kp (G). In this paper, we give characterizations of graphs for which γ _kp (G)=γ(G)+k?2 and prove that the perfect k-domination problem is NP-complete even when restricted to bipartite graphs and chordal graphs. Also, by using dynamic programming techniques, we obtain an algorithm to determine the perfect k-domination number of trees.     

Hardness results and approximation algorithm for total liar’s domination in graphs

In this paper, we initiate the study of total liar’s domination of a graph. A subset L?V of a graph G=(V,E) is called a total liar’s dominating set of G if (i) for all v∈V, |N _G (v)∩L|≥2 and (ii) for every pair u,v∈V of distinct vertices, |(N _G (u)∪N _G (v))∩L|≥3. The total liar’s domination number of a graph G is the cardinality of a minimum total liar’s dominating set of G and is denoted by γ _TLR (G). The Minimum Total Liar’s Domination Problem is to find a total liar’s dominating set of minimum cardinality of the input graph G. Given a graph G and a positive integer k, the Total Liar’s Domination Decision Problem is to check whether G has a total liar’s dominating set of cardinality at most k. In this paper, we give a necessary and sufficient condition for the existence of a total liar’s dominating set in a graph. We show that the Total Liar’s Domination Decision Problem is NP-complete for general graphs and is NP-complete even for split graphs and hence for chordal graphs. We also propose a 2(lnΔ(G)+1)-approximation algorithm for the Minimum Total Liar’s Domination Problem, where Δ(G) is the maximum degree of the input graph G. We show that Minimum Total Liar’s Domination Problem cannot be approximated within a factor of $(\frac{1}{8}-\epsilon)\ln(|V|)$ for any ?>0, unless NP?DTIME(|V|^loglog|V|). Finally, we show that Minimum Total Liar’s Domination Problem is APX-complete for graphs with bounded degree 4.     

Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs

A set D?V of a graph G=(V,E) is a dominating set of G if every vertex in V?D has at least one neighbor in D. A dominating set D of G is a paired-dominating set of G if the induced subgraph, G[D], has a perfect matching. Given a graph G=(V,E) and a positive integer k, the paired-domination problem is to decide whether G has a paired-dominating set of cardinality at most k. The paired-domination problem is known to be NP-complete for bipartite graphs. In this paper, we, first, strengthen this complexity result by showing that the paired-domination problem is NP-complete for perfect elimination bipartite graphs. We, then, propose a linear time algorithm to compute a minimum paired-dominating set of a chordal bipartite graph, a well studied subclass of bipartite graphs.     

An Algorithm for the Maximum Likelihood Problem on Evolutionary Trees

We investigate the problem of reconstructing evolutionary trees with maximum likelihood (MLET). In the MLET problem, a set of genetic sequences is given and a feasible solution is sought, consisting of an evolutionary tree (where general nodes correspond to sequences and input sequences occur as leaves) along with assignments for the interior nodes. Due to the difficulty of solving the MLET directly, we consider two restricted versions of the problem: the ancestral maximum likelihood (AML) and the maximum parsimony (MP) problems. If we let d_e denote the number of different characters occurring in two nodes linked by edge e, then the objective function of the AML problem is min ∑_{eσ E(T)} H(d_e/k), where H is the entropy function and k is the length of each sequence. In the MP we consider the objective function min σ_{e∊ E(T)} d_e/k. Both the AML and the MP are NP-hard. We propose a new approach for computing solutions for these problems, based on genetic algorithms.     

Max-coloring paths: tight bounds and extensions

The max-coloring problem is to compute a legal coloring of the vertices of a graph G=(V,E) with vertex weights w such that $\sum_{i=1}^{k}\max_{v\in C_{i}}w(v_{i})$ is minimized, where C ₁,??,C _k are the various color classes. For general graphs, max-coloring is as hard as the classical vertex coloring problem, a special case of the former where vertices have unit weight. In fact, in some cases it can even be harder: for example, no polynomial time algorithm is known for max-coloring trees. In this paper we consider the problem of max-coloring paths and its generalization, max-coloring skinny trees, a broad class of trees that includes paths and spiders. For these graphs, we show that max-coloring can be solved in time O(|V|+time for sorting the vertex weights). When vertex weights are real numbers, we show a matching lower bound of ??(|V|log?|V|) in the algebraic computation tree model.     

Approximating capacitated tree-routings in networks

Let G=(V,E) be a connected graph such that each edge e∈E is weighted by a nonnegative real w(e). Let s be a vertex designated as a sink, M?V be a set of terminals with a demand function q:M→R ⁺, κ>0 be a routing capacity, and λ≥1 be an integer edge capacity. The capacitated tree-routing problem (CTR) asks to find a partition ?={Z ₁,Z ₂,…,Z _? } of M and a set \({\mathcal{T}}=\{T_{1},T_{2},\ldots,T_{\ell}\}\) of trees of G such that each T _i contains Z _i ∪{s} and satisfies \(\sum_{v\in Z_{i}}q(v)\leq \kappa\). A single copy of an edge e∈E can be shared by at most λ trees in \({\mathcal{T}}\); any integer number of copies of e are allowed to be installed, where the cost of installing a copy of e is w(e). The objective is to find a solution \(({\mathcal{M}},{\mathcal{T}})\) that minimizes the total installing cost. In this paper, we propose a (2+ρ _ST )-approximation algorithm to CTR, where ρ _ST is any approximation ratio achievable for the Steiner tree problem.     

Some results on the target set selection problem

In this paper we consider a fundamental problem in the area of viral marketing, called Target Set Selection problem. We study the problem when the underlying graph is a block-cactus graph, a chordal graph or a Hamming graph. We show that if G is a block-cactus graph, then the Target Set Selection problem can be solved in linear time, which generalizes Chen’s result (Discrete Math. 23:1400–1415, 2009) for trees, and the time complexity is much better than the algorithm in Ben-Zwi et al. (Discrete Optim., 2010) (for bounded treewidth graphs) when restricted to block-cactus graphs. We show that if the underlying graph G is a chordal graph with thresholds θ(v)≤2 for each vertex v in G, then the problem can be solved in linear time. For a Hamming graph G having thresholds θ(v)=2 for each vertex v of G, we precisely determine an optimal target set S for (G,θ). These results partially answer an open problem raised by Dreyer and Roberts (Discrete Appl. Math. 157:1615–1627, 2009).     

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.     

A polynomial time approximation scheme for?embedding a directed hypergraph on a weighted ring

Given a directed hypergraph H=(V,E _H ), we consider the problem of embedding all directed hyperedges on a weighted ring. The objective is to minimize the maximum congestion which is equal to the maximum product of the weight of a link and the number of times that the link is passed by the embedding. In this paper, we design a polynomial time approximation scheme for this problem.     

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.     

On minimum balanced bipartitions of triangle-free graphs

A balanced bipartition of a graph G is a partition of V(G) into two subsets V ₁ and V ₂ that differ in cardinality by at most 1. A minimum balanced bipartition of G is a balanced bipartition V ₁, V ₂ of G minimizing e(V ₁,V ₂), where e(V ₁,V ₂) is the number of edges joining V ₁ and V ₂ and is usually referred to as the size of the bipartition. In this paper, we show that every 2-connected graph G admits a balanced bipartition V ₁,V ₂ such that the subgraphs of G induced by V ₁ and by V ₂ are both connected. This yields a good upper bound to the size of minimum balanced bipartition of sparse graphs. We also present two upper bounds to the size of minimum balanced bipartitions of triangle-free graphs which sharpen the corresponding bounds of Fan et al. (Discrete Math. 312:1077–1083, 2012).     

On the total outer-connected domination in graphs

A set S of vertices of a graph G is a total outer-connected dominating set if every vertex in V(G) is adjacent to some vertex in S and the subgraph induced by V?S is connected. The total outer-connected domination number γ _toc (G) is the minimum size of such a set. We give some properties and bounds for γ _toc in general graphs and in trees. For graphs of order n, diameter 2 and minimum degree at least 3, we show that $\gamma_{toc}(G)\le \frac{2n-2}{3}$ and we determine the extremal graphs.