Due to their importance in practice, dominating set problems in graphs have been greatly studied in past and different formulations of these problems are presented in literature. This paper's focus is on two problems: weakly convex dominating set problem (WCVXDSP) and convex dominating set problem (CVXDSP). It introduces two integer linear programming (ILP) formulation for CVXDSP and one ILP mode for WCVXDSP, as well as proof for equivalency between ILP models for CVXDSP. The proof of correctness for all introduced ILP formulations is provided by showing that optimal solution to the each ILP formulation is equal to the optimal solution of the original problem.
The edge subdivision influence on the convex domination number is discussed in @cite_8 . In that paper it is shown that, in general, the convex domination number can be arbitrarily increased and decreased by an edge subdivision. Study of weakly convex domination subdivision number and its upper bounds is presented in @cite_1 .
@cite_1 @cite_8
2740018852 1954707945 2017926358 1515157528
We study the influence of edge subdivision on the convex domination number. We show that in general an edge subdivision can arbitrarily increase and arbitrarily decrease the convex domination number. We also find some bounds for unicyclic graphs and we investigate graphs G for which the convex domination number changes after subdivision of any edge in G. A set @math is weakly convex in @math if for any two vertices @math there exists an @math --geodesic such that all of its vertices belong to @math . A set @math is a weakly convex dominating set if @math is weakly convex and dominating. The weakly convex domination number @math of a graph @math equals the minimum cardinality of a weakly convex dominating set in @math . The weakly convex domination subdivision number sd @math is the minimum number of edges that must be subdivided (each edge in @math can be subdivided at most once) in order to increase the weakly convex domination number. In this paper we initiate the study of weakly convex domination subdivision number and we establish upper bounds for it. In 1985, Fink and Jacobson gave a generalization of the concepts of domination and independence in graphs. For a positive integer k, a subset S of vertices in a graph G = (V, E) is k-dominating if every vertex of V − S is adjacent to at least k vertices in S. The subset S is k-independent if the maximum degree of the subgraph induced by the vertices of S is less or equal to k − 1. In this paper we survey results on k-domination and k-independence. A set of vertices in a graph is a dominating set if every vertex outside the set has a neighbor in the set. The domatic number problem is that of partitioning the vertices of a graph into the maximum number of disjoint dominating sets. Let n denote the number of vertices, @math the minimum degree, and @math the maximum degree. We show that every graph has a domatic partition with @math dominating sets and, moreover, that such a domatic partition can be found in polynomial-time. This implies a @math -approximation algorithm for domatic number, since the domatic number is always at most @math . We also show this to be essentially best possible. Namely, extending the approximation hardness of set cover by combining multiprover protocols with zero-knowledge techniques, we show that for every @math , a @math -approximation implies that @math . This makes domatic number the first natural maximization problem (known to the authors) that is provably approximable to within polylogarithmic factors but no better. We also show that every graph has a domatic partition with @math dominating sets, where the "o(1)" term goes to zero as @math increases. This can be turned into an efficient algorithm that produces a domatic partition of @math sets.