A decomposition approach for solving a broadcast domination network design problem

We consider an optimization problem that integrates network design and broadcast domination decisions. Given an undirected graph, a feasible broadcast domination is a set of nonnegative integer powers f _i assigned to each node i, such that for any node j in the graph, there exists some node k having a positive f _k -value whose shortest distance to node j is no more than f _k . The cost of a broadcast domination solution is the sum of all node power values. The network design problem constructs edges that decrease the minimum broadcast domination cost on the graph. The overall problem we consider minimizes the sum of edge construction costs and broadcast domination costs. We show that this problem is NP-hard in the strong sense, even on unweighted graphs. We then propose a decomposition strategy, which iteratively adds valid inequalities based on optimal broadcast domination solutions corresponding to the first-stage network design solutions. We demonstrate that our decomposition approach is computationally far superior to the solution of a single large-scale mixed-integer programming formulation.     

New bounds for the broadcast domination number of a graph

A dominating broadcast on a graph G = (V, E) is a function f: V → {0, 1, ..., diam G} such that f(v) ≤ e(v) (the eccentricity of v) for all v ∈ V and such that each vertex is within distance f(v) from a vertex v with f(v) > 0. The cost of a broadcast f is σ(f) = Σ _v∈V f(v), and the broadcast number λ _b (G) is the minimum cost of a dominating broadcast. A set X ? V(G) is said to be irredundant if each x ∈ X dominates a vertex y that is not dominated by any other vertex in X; possibly y = x. The irredundance number ir (G) is the cardinality of a smallest maximal irredundant set of G. We prove the bound λ_b(G) ≤ 3 ir(G)/2 for any graph G and show that equality is possible for all even values of ir (G). We also consider broadcast domination as an integer programming problem, the dual of which provides a lower bound for λ_b.     

The source location problem with local 3-vertex-connectivity requirements

Let G=(V,E) be a simple undirected graph with a set V of vertices and a set E of edges. Each vertex v∈V has an integer valued demand d(v)?0. The source location problem with vertex-connectivity requirements in a given graph G asks to find a set S of vertices with the minimum cardinality such that there are at least d(v) vertex-disjoint paths between S and each vertex v∈V-S. In this paper, we show that the problem with d(v)?3, v∈V can be solved in linear time. Moreover, we show that in the case where d(v)?4 for some vertex v∈V, the problem is NP-hard.     

Upper minus total domination in small-degree regular graphs

A function f:V(G)→{-1,0,1} defined on the vertices of a graph G is a minus total dominating function (MTDF) if the sum of its function values over any open neighborhood is at least one. An MTDF f is minimal if there does not exist an MTDF g:V(G)→{-1,0,1}, f≠g, for which g(v)?f(v) for every v∈V(G). The weight of an MTDF is the sum of its function values over all vertices. The minus total domination number of G is the minimum weight of an MTDF on G, while the upper minus domination number of G is the maximum weight of a minimal MTDF on G. In this paper we present upper bounds on the upper minus total domination number of a cubic graph and a 4-regular graph and characterize the regular graphs attaining these upper bounds.     

Outer-2-independent domination in graphs

We initiate the study of outer-2-independent domination in graphs. An outer-2-independent dominating set of a graph G is a set D of vertices of G such that every vertex of V(G)?D has a neighbor in D and the maximum vertex degree of the subgraph induced by V(G)?D is at most one. The outer-2-independent domination number of a graph G is the minimum cardinality of an outer-2-independent dominating set of G. We show that if a graph has minimum degree at least two, then its outer-2-independent domination number equals the number of vertices minus the 2-independence number. Then we investigate the outer-2-independent domination in graphs with minimum degree one. We also prove the Vizing-type conjecture for outer-2-independent domination and disprove the Vizing-type conjecture for outer-connected domination.     

Radial trees

A broadcast on a graph G is a function such that for each v∈V, f(v)≤e(v) (the eccentricity of v). The broadcast number of G is the minimum value of ∑_v∈Vf(v) among all broadcasts f for which each vertex of G is within distance f(v) from some vertex v having f(v)≥1. This number is bounded above by the radius of G as well as by its domination number. Graphs for which the broadcast number is equal to the radius are called radial; the problem of characterizing radial trees was first discussed in [J. Dunbar, D. Erwin, T. Haynes, S.M. Hedetniemi, S.T. Hedetniemi, Broadcasts in graphs, Discrete Appl. Math. (154) (2006) 59-75].We provide a characterization of radial trees as well as a geometrical interpretation of our characterization.     

Vertex insertion approximates the crossing number of apex graphs

An apex graph is a graph G from which only one vertex v has to be removed to make it planar. We show that the crossing number of such G can be approximated up to a factor of Δ(G−v)⋅d(v)/2 by solving the vertex inserting problem, i.e. inserting a vertex plus incident edges into an optimally chosen planar embedding of a planar graph. Since the latter problem can be solved in polynomial time, this establishes the first polynomial fixed-factor approximation algorithm for the crossing number problem of apex graphs with bounded degree.Furthermore, we extend this result by showing that the optimal solution for inserting multiple edges or vertices into a planar graph also approximates the crossing number of the resulting graph.     

Broadcasts and domination in trees

A broadcast on a graph G is a function f:V→Z⁺∪{0}. The broadcast number of G is the minimum value of ∑_v∈Vf(v) among all broadcasts f for which each vertex of G is within distance f(v) from some vertex v with f(v)≥1. This number is bounded above by the radius and the domination number of G. We show that to characterize trees with equal broadcast and domination numbers it is sufficient to characterize trees for which all three of these parameters coincide.     

Rainbow domination on trees

This paper studies a variation of domination in graphs called rainbow domination. For a positive integer k, a k-rainbow dominating function of a graph G is a function f from V(G) to the set of all subsets of {1,2,…,k} such that for any vertex v with f(v)=0? we have ∪_u∈NG(v)f(u)={1,2,…,k}. The 1-rainbow domination is the same as the ordinary domination. The k-rainbow domination problem is to determine the k-rainbow domination number of a graph G, that is the minimum value of ∑_v∈V(G)|f(v)| where f runs over all k-rainbow dominating functions of G. In this paper, we prove that the k-rainbow domination problem is NP-complete even when restricted to chordal graphs or bipartite graphs. We then give a linear-time algorithm for the k-rainbow domination problem on trees. For a given tree T, we also determine the smallest k such that .     

Minimum sum set coloring of trees and line graphs of trees

In this paper, we study the minimum sum set coloring (MSSC) problem which consists in assigning a set of x(v) positive integers to each vertex v of a graph so that the intersection of sets assigned to adjacent vertices is empty and the sum of the assigned set of numbers to each vertex of the graph is minimum. The MSSC problem occurs in two versions: non-preemptive and preemptive. We show that the MSSC problem is strongly NP-hard both in the preemptive case on trees and in the non-preemptive case in line graphs of trees. Finally, we give exact parameterized algorithms for these two versions on trees and line graphs of trees.     

A note on Roman domination in graphs

Let G=(V,E) be a simple graph. A subset S⊆V is a dominating set of G, if for any vertex u∈V-S, there exists a vertex v∈S such that uv∈E. The domination number of G, γ(G), equals the minimum cardinality of a dominating set. A Roman dominating function on graph G=(V,E) is a function f:V→{0,1,2} satisfying the condition that every vertex v for which f(v)=0 is adjacent to at least one vertex u for which f(u)=2. The weight of a Roman dominating function is the value f(V)=∑_v∈Vf(v). The Roman domination number of a graph G, denoted by γ_R(G), equals the minimum weight of a Roman dominating function on G. In this paper, for any integer k(2?k?γ(G)), we give a characterization of graphs for which γ_R(G)=γ(G)+k, which settles an open problem in [E.J. Cockayne, P.M. Dreyer Jr, S.M. Hedetniemi et al. On Roman domination in graphs, Discrete Math. 278 (2004) 11-22].     

A Greedy Partition Lemma for directed domination

A directed dominating set in a directed graph D is a set S of vertices of V such that every vertex u∈V(D)?S has an adjacent vertex v in S with v directed to u. The directed domination number of D, denoted by γ(D), is the minimum cardinality of a directed dominating set in D. The directed domination number of a graph G, denoted Γ_d(G), is the maximum directed domination number γ(D) over all orientations D of G. The directed domination number of a complete graph was first studied by Erd?s [P. Erd?s On a problem in graph theory, Math. Gaz. 47 (1963) 220–222], albeit in a disguised form. In this paper we prove a Greedy Partition Lemma for directed domination in oriented graphs. Applying this lemma, we obtain bounds on the directed domination number. In particular, if α denotes the independence number of a graph G, we show that α≤Γ_d(G)≤α(1+2ln(n/α)).     

Generalized Power Domination: Propagation Radius and Sierpiński Graphs

The recently introduced concept of k-power domination generalizes domination and power domination, the latter concept being used for monitoring an electric power system. The k-power domination problem is to determine a minimum size vertex subset S of a graph G such that after setting X=N[S], and iteratively adding to X vertices x that have a neighbour v in X such that at most k neighbours of v are not yet in X, we get X=V(G). In this paper the k-power domination number of Sierpiński graphs is determined. The propagation radius is introduced as a measure of the efficiency of power dominating sets. The propagation radius of Sierpiński graphs is obtained in most of the cases.     

Roman and Total Domination

Abstract

A set S of vertices is a total dominating set of a graph G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set is the total domination number ^γt(G). A Roman dominating function on a graph G is a function f : V (G) → {0, 1, 2} satisfying the condition that every vertex u with f (u)=0 is adjacent to at least one vertex v of G for which f (v)=2. The minimum of f (V (G))=∑_{u ∈ V (G)} f (u) over all such functions is called the Roman domination number γR (G). We show that γt(G) ≤ γR (G) with equality if and only if ^γt(G)=2γ(G), where γ(G) is the domination number of G. Moreover, we characterize the extremal graphs for some graph families.     

Geodetic and Steiner geodetic sets in 3-Steiner distance hereditary graphs

Let G be a connected graph and S⊆V(G). Then the Steiner distance of S, denoted by d_G(S), is the smallest number of edges in a connected subgraph of G containing S. Such a subgraph is necessarily a tree called a Steiner tree for S. The Steiner interval for a set S of vertices in a graph, denoted by I(S) is the union of all vertices that belong to some Steiner tree for S. If S={u,v}, then I(S) is the interval I[u,v] between u and v. A connected graph G is 3-Steiner distance hereditary (3-SDH) if, for every connected induced subgraph H of order at least 3 and every set S of three vertices of H, d_H(S)=d_G(S). The eccentricity of a vertex v in a connected graph G is defined as e(v)=max{d(v,x)|x∈V(G)}. A vertex v in a graph G is a contour vertex if for every vertex u adjacent with v, e(u)?e(v). The closure of a set S of vertices, denoted by I[S], is defined to be the union of intervals between pairs of vertices of S taken over all pairs of vertices in S. A set of vertices of a graph G is a geodetic set if its closure is the vertex set of G. The smallest cardinality of a geodetic set of G is called the geodetic number of G and is denoted by g(G). A set S of vertices of a connected graph G is a Steiner geodetic set for G if I(S)=V(G). The smallest cardinality of a Steiner geodetic set of G is called the Steiner geodetic number of G and is denoted by sg(G). We show that the contour vertices of 3-SDH and HHD-free graphs are geodetic sets. For 3-SDH graphs we also show that g(G)?sg(G). An efficient algorithm for finding Steiner intervals in 3-SDH graphs is developed.     

Graphs with small boundary

For a pair of vertices x and y in a graph G, we denote by d_G(x,y) the distance between x and y in G. We call x a boundary vertex of y if x and y belong to the same component and d_G(y,v)?d_G(y,x) for each neighbor v of x in G. A boundary vertex of some vertex is simply called a boundary vertex, and the set of boundary vertices in G is called the boundary of G, and is denoted by B(G).In this paper, we investigate graphs with a small boundary. Since a pair of farthest vertices are boundary vertices, |B(G)|?2 for every connected graph G of order at least two. We characterize the graphs with boundary of order at most three. We cannot give a characterization of graphs with exactly four boundary vertices, but we prove that such graphs have minimum degree at most six. Finally, we give an upper bound to the minimum degree of a connected graph G in terms of |B(G)|.     

A note on the (g,f)-coloring

In an ordinary edge-coloring of a graph, each color appears at each vertex v at most once. A (g,f)-coloring (factorization) is a generalized edge-coloring in which each color appears at each vertex v at least g(v) and at most f(v) times, where g(v) and f(v) are respectively nonnegative and positive integers assigned to v. Using coloring method, we give a new necessary and sufficient condition for a bipartite graph to have a (g,f)-coloring and we give some sufficient conditions for a general graph to have a (g,f)-coloring.     

Roman dominating influence parameters

A function f:V(G)→{0,1,2} is a Roman dominating function for a graph G=(V,E) if for every vertex v with f(v)=0, there exists a vertex w∈N(v) with f(w)=2. Emperor Constantine had the requirement that an army or legion could be sent from its home to defend a neighboring location only if there was a second army which would stay and protect the home. Thus, there are two types of armies, stationary and traveling. Each vertex with no army must have a neighboring vertex with a traveling army. Stationary armies then dominate their own vertices, and a vertex with two armies is dominated by its stationary army, and its open neighborhood is dominated by the traveling army. In this paper, we introduce Roman dominating influence parameters in which the interest is in dominating each vertex exactly once.     

Matchings in 3-vertex-critical graphs: The odd case

A subset of vertices D of a graph G is a dominating set for G if every vertex of G not in D is adjacent to one in D. The cardinality of any smallest dominating set in G is denoted by γ(G) and called the domination number of G. Graph G is said to be γ-vertex-critical if γ(G-v)<γ(G), for every vertex v in G. A graph G is said to be factor-critical if G-v has a perfect matching for every choice of v∈V(G).In this paper, we present two main results about 3-vertex-critical graphs of odd order. First we show that any such graph with positive minimum degree and at least 11 vertices which has no induced subgraph isomorphic to the bipartite graph K_1,5 must contain a near-perfect matching. Secondly, we show that any such graph with minimum degree at least three which has no induced subgraph isomorphic to the bipartite graph K_1,4 must be factor-critical. We then show that these results are best possible in several senses and close with a conjecture.     

Upper bounds on the upper signed total domination number of graphs

Let G=(V,E) be a graph. A function f:V→{−1,+1} defined on the vertices of G is a signed total dominating function if the sum of its function values over any open neighborhood is at least one. A signed total dominating function f is minimal if there does not exist a signed total dominating function g, f≠g, for which g(v)≤f(v) for every v∈V. The weight of a signed total dominating function is the sum of its function values over all vertices of G. The upper signed total domination number of G is the maximum weight of a minimal signed total dominating function on G. In this paper we present a sharp upper bound on the upper signed total domination number of an arbitrary graph. This result generalizes previous results for regular graphs and nearly regular graphs.