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.     

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.     

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.     

Hamiltonian numbers in oriented graphs

A hamiltonian walk of a digraph is a closed spanning directed walk with minimum length in the digraph. The length of a hamiltonian walk in a digraph D is called the hamiltonian number of D, denoted by h(D). In Chang and Tong (J Comb Optim 25:694–701, 2013), Chang and Tong proved that for a strongly connected digraph D of order n, \(n\le h(D)\le \lfloor \frac{(n+1)^2}{4} \rfloor \), and characterized the strongly connected digraphs of order n with hamiltonian number \(\lfloor \frac{(n+1)^2}{4} \rfloor \). In the paper, we characterized the strongly connected digraphs of order n with hamiltonian number \(\lfloor \frac{(n+1)^2}{4} \rfloor -1\) and show that for any triple of integers n, k and t with \(n\ge 5\), \(n\ge k\ge 3\) and \(t\ge 0\), there is a class of nonisomorphic digraphs with order n and hamiltonian number \(n(n-k+1)-t\).     

Upper paired-domination in claw-free graphs

A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The maximum cardinality of a minimal paired-dominating set of G is the upper paired-domination number of G, denoted by Γ_pr(G). We establish bounds on Γ_pr(G) for connected claw-free graphs G in terms of the number n of vertices in G with given minimum degree δ. We show that Γ_pr(G)≤4n/5 if δ=1 and n≥3, Γ_pr(G)≤3n/4 if δ=2 and n≥6, and Γ_pr(G)≤2n/3 if δ≥3. All these bounds are sharp. Further, if n≥6 the graphs G achieving the bound Γ_pr(G)=4n/5 are characterized, while for n≥9 the graphs G with δ=2 achieving the bound Γ_pr(G)=3n/4 are characterized.     

Restrained domination in cubic graphs

Let G=(V,E) be a graph. A set S⊆V is a restrained dominating set if every vertex in V−S is adjacent to a vertex in S and to a vertex in V−S. The restrained domination number of G, denoted γ _r (G), is the smallest cardinality of a restrained dominating set of G. A graph G is said to be cubic if every vertex has degree three. In this paper, we study restrained domination in cubic graphs. We show that if G is a cubic graph of order n, then g_r(G) 3 \fracn4\gamma_{r}(G)\geq \frac{n}{4} , and characterize the extremal graphs achieving this lower bound. Furthermore, we show that if G is a cubic graph of order n, then g_r(G) ￡ \frac5n11.\gamma _{r}(G)\leq \frac{5n}{11}. Lastly, we show that if G is a claw-free cubic graph, then γ _r (G)=γ(G).     

On broadcasting in unicyclic graphs

Broadcasting is an information dissemination problem in a connected network, in which one node, called the originator, disseminates a message to all other nodes by placing a series of calls along the communication lines of the network. Finding the broadcast time of a vertex in an arbitrary graph is NP-complete. The polynomial time solvability is shown only for trees. In this paper we present a linear algorithm that determines the broadcast time of any originator in an arbitrary unicyclic graph. As a byproduct, we find a broadcast center of the unicyclic graph. We also present an O(|V|+k ²) algorithm to find the broadcast time of an arbitrary unicyclic graph, where k is the length of the cycle. In the last section we give tight lower and upper bounds on broadcast time of a spanning tree based on the broadcast time of the unicyclic graph. The results of Sects. 2, 3 and most of the proofs in Sects. 2, 3 of this paper are presented by Harutyunyan and Maraachlian (Proceedings of 13th annual COCOON, pp. 372–383, 2007). All results in Sects. 4, 5 and the complete proof of Theorem 3 are new results.     

Disjunctive total domination in graphs

Let \(G\) be a graph with no isolated vertex. In this paper, we study a parameter that is a relaxation of arguably the most important domination parameter, namely the total domination number, \(\gamma _t(G)\). A set \(S\) of vertices in \(G\) is a disjunctive total dominating set of \(G\) if every vertex is adjacent to a vertex of \(S\) or has at least two vertices in \(S\) at distance \(2\) from it. The disjunctive total domination number, \(\gamma ^d_t(G)\), is the minimum cardinality of such a set. We observe that \(\gamma ^d_t(G) \le \gamma _t(G)\). We prove that if \(G\) is a connected graph of order \(n \ge 8\), then \(\gamma ^d_t(G) \le 2(n-1)/3\) and we characterize the extremal graphs. It is known that if \(G\) is a connected claw-free graph of order \(n\), then \(\gamma _t(G) \le 2n/3\) and this upper bound is tight for arbitrarily large \(n\). We show this upper bound can be improved significantly for the disjunctive total domination number. We show that if \(G\) is a connected claw-free graph of order \(n > 14\), then \(\gamma ^d_t(G) \le 4n/7\) and we characterize the graphs achieving equality in this bound.     

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.     

Signed Roman domination in graphs

In this paper we continue the study of Roman dominating functions in graphs. A signed Roman dominating function (SRDF) on a graph G=(V,E) is a function f:V→{?1,1,2} satisfying the conditions that (i) the sum of its function values over any closed neighborhood is at least one and (ii) for every vertex u for which f(u)=?1 is adjacent to at least one vertex v for which f(v)=2. The weight of a SRDF is the sum of its function values over all vertices. The signed Roman domination number of G is the minimum weight of a SRDF in G. We present various lower and upper bounds on the signed Roman domination number of a graph. Let G be a graph of order n and size m with no isolated vertex. We show that $\gamma _{\mathrm{sR}}(G) \ge\frac{3}{\sqrt{2}} \sqrt{n} - n$ and that γ _sR(G)≥(3n?4m)/2. In both cases, we characterize the graphs achieving equality in these bounds. If G is a bipartite graph of order n, then we show that $\gamma_{\mathrm{sR}}(G) \ge3\sqrt{n+1} - n - 3$ , and we characterize the extremal graphs.     

Independent domination in subcubic graphs

Journal of Combinatorial Optimization - A set S of vertices in a graph G is a dominating set if every vertex not in S is adjacent to a vertex in&nbsp;S. If, in addition, S is an independent...     

Paired-domination in generalized claw-free graphs

In this paper, we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks 32 (1998) 199–206). A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The paired-domination number of G, denoted by , is the minimum cardinality of a paired-dominating set of G. If G does not contain a graph F as an induced subgraph, then G is said to be F-free. Haynes and Slater (Networks 32 (1998) 199–206) showed that if G is a connected graph of order , then and this bound is sharp for graphs of arbitrarily large order. Every graph is -free for some integer a ≥ 0. We show that for every integer a ≥ 0, if G is a connected -free graph of order n ≥ 2, then with infinitely many extremal graphs.     

Well paired-dominated graphs

A paired-dominating set is a dominating set whose induced subgraph contains at least one perfect matching. This could model the situation of guards or police where each has a partner or backup. We are interested in those where all “minimal” paired-dominating sets are the same cardinality. In this case, we consider “minimal” to be with respect to the pairings. That is, the removal of any two vertices paired under the matching results in a set that is not dominating. We give a structural characterization of all such graphs with girth at least eight.     

Disconnected $$g_c$$-critical graphs

Every critical graph is connected on proper edge-colorings of simple graphs. In contrast, there not only exist connected critical graphs but exist disconnected critical graphs on \(g_c\)-colorings of simple graphs. In this article, disconnected \(g_c\)-critical graphs are studied firstly and their structure characteristics are depicted.     

On the outer-connected domination in graphs

A set S of vertices of a graph G is an outer-connected dominating set if every vertex not in S is adjacent to some vertex in S and the subgraph induced by V?S is connected. The outer-connected domination number $\widetilde{\gamma}_{c}(G)$ is the minimum size of such a set. We prove that if δ(G)≥2 and diam?(G)≤2, then $\widetilde{\gamma}_{c}(G)\le (n+1)/2$ , and we study the behavior of $\widetilde{\gamma}_{c}(G)$ under an edge addition.     

Independent dominating sets in regular graphs

Let G be a simple, regular graph of order n and degree δ. The independent domination number i(G) is defined to be the minimum cardinality among all maximal independent sets of vertices of G. We establish new upper bounds, as functions of n and δ, for the independent domination number of regular graphs with $n/6<\delta< (3-\sqrt{5})n/2$ . Our two main theorems complement recent results of Goddard et al. (Ann. Comb., 2011) for larger values of δ.     

The density maximization problem in graphs

We consider a framework for bi-objective network construction problems where one objective is to be maximized while the other is to be minimized. Given a host graph G=(V,E) with edge weights w _e ∈? and edge lengths ? _e ∈? for e∈E we define the density of a pattern subgraph H=(V′,E′)?G as the ratio ?(H)=∑ _e∈E′ w _e /∑ _e∈E′ ? _e . We consider the problem of computing a maximum density pattern H under various additional constraints. In doing so, we compute a single Pareto-optimal solution with the best weight per cost ratio subject to additional constraints further narrowing down feasible solutions for the underlying bi-objective network construction problem. First, we consider the problem of computing a maximum density pattern with weight at least W and length at most L in a host G. We call this problem the biconstrained density maximization problem. This problem can be interpreted in terms of maximizing the return on investment for network construction problems in the presence of a limited budget and a target profit. We consider this problem for different classes of hosts and patterns. We show that it is NP-hard, even if the host has treewidth 2 and the pattern is a path. However, it can be solved in pseudo-polynomial linear time if the host has bounded treewidth and the pattern is a graph from a given minor-closed family of graphs. Finally, we present an FPTAS for a relaxation of the density maximization problem, in which we are allowed to violate the upper bound on the length at the cost of some penalty. Second, we consider the maximum density subgraph problem under structural constraints on the vertex set that is used by the patterns. While a maximum density perfect matching can be computed efficiently in general graphs, the maximum density Steiner-subgraph problem, which requires a subset of the vertices in any feasible solution, is NP-hard and unlikely to admit a constant-factor approximation. When parameterized by the number of vertices of the pattern, this problem is W[1]-hard in general graphs. On the other hand, it is FPT on planar graphs if there is no constraint on the pattern and on general graphs if the pattern is a path.     

Signed total Roman domination in graphs

Let \(G\) be a finite and simple graph with vertex set \(V(G)\). A signed total Roman dominating function (STRDF) on a graph \(G\) is a function \(f:V(G)\rightarrow \{-1,1,2\}\) satisfying the conditions that (i) \(\sum _{x\in N(v)}f(x)\ge 1\) for each vertex \(v\in V(G)\), where \(N(v)\) is the neighborhood of \(v\), and (ii) every vertex \(u\) for which \(f(u)=-1\) is adjacent to at least one vertex \(v\) for which \(f(v)=2\). The weight of an SRTDF \(f\) is \(\sum _{v\in V(G)}f(v)\). The signed total Roman domination number \(\gamma _{stR}(G)\) of \(G\) is the minimum weight of an STRDF on \(G\). In this paper we initiate the study of the signed total Roman domination number of graphs, and we present different bounds on \(\gamma _{stR}(G)\). In addition, we determine the signed total Roman domination number of some classes of graphs.