Search

In a graph, G = (V , E) without an isolated vertex, a dominating set D ⊆ V , is called a semitotal dominating set if for every vertex u ∈ D there is another vertex v ∈ D such that distance between u and v is at most two in G. Given a graph G = (V , E) without an isolated vertex, the Minimum Semitotal Domination problem is to find a minimum cardinality semitotal dominating set of G. The semitotal domination number , denoted by γ t 2 (G) , is the minimum cardinality of a semitotal dominating set of G. It is known that the decision version of the problem remains NP-complete even when restricted to chordal graphs, chordal bipartite graphs, and planar graphs. Galby et al. (2020) proved that the problem can be solved in polynomial time for bounded MIM-width graphs, which include many well known graph classes, but left the complexity of the problem in strongly chordal graphs unresolved. Henning and Pandey (2019) also asked to resolve the complexity status of the problem in strongly chordal graphs. In this paper, we resolve the complexity of the problem in strongly chordal graphs by designing a linear-time algorithm for the problem. [ABSTRACT FROM AUTHOR]

Zou et al. (2019) proposed an algorithm for calculating a minimum secure dominating set of a proper interval graph. However, we find a counterexample for which the algorithm outputs an incorrect subset of vertices. In this paper, we provide a modified algorithm and the proofs for the correctness. [ABSTRACT FROM AUTHOR]

Given a graph G = (V , E) and an integer k ≥ 1 , a k - hop dominating set D of G is a subset of V , such that, for every vertex v ∈ V , there exists a node u ∈ D whose distance from v is at most k. A k -hop dominating set of minimum cardinality is called a minimum k -hop dominating set. In this paper, we present a linear-time algorithm that finds a minimum k -hop dominating set in cactus graphs , which improves the O (n 3) -time algorithm of Borradaile and Le (2017). To achieve this, we show that the k -hop dominating set problem for unicyclic graphs reduces to the piercing circular arcs problem , and show a linear-time algorithm for piercing sorted circular arcs, which improves the best known O (n log n) -time algorithm. [ABSTRACT FROM AUTHOR]

A dominating set of a graph G is a set S ⊆ V (G) such that every vertex in G is either in S or adjacent to a vertex in S. A dominating set S is a connected dominating set if the subgraph of G induced by S is connected. The minimum cardinality of a connected dominating set of G is the connected domination number , denoted by γ c (G). Zhuang showed that γ c (G) of a maximal outerplanar graph G is bounded by min { ⌊ n + k 2 ⌋ − 2 , ⌊ 2 (n − k) 3 ⌋ } (Zhuang, 2020), where k is the number of 2-degree vertices in G. In this paper, we give an algorithm for finding a connected dominating set of maximal outerplanar graphs and get an upper bound γ c (G) ≤ ⌊ n − k + x 2 ⌋ , where x is a counter in the algorithm and x ≤ k − 2. As a corollary, the result that γ c (G) ≤ ⌊ n − 2 2 ⌋ for a maximal outerplanar G is gotten directly. This results is better than the above known bound for 3 < k < n + 6 4 . In addition, we complement some analysis with simulations to evaluate the advantages of our results. [ABSTRACT FROM AUTHOR]

A set S ⊂ V is a co-secure dominating set of a graph G = (V , E) if S is a dominating set, and for each u ∈ S there exists a vertex v ∈ V ∖ S such that u v ∈ E and (S ∖ { u }) ∪ { v } is a dominating set. Note that | V | > 1. The minimum cardinality of a co-secure dominating set in G is the co-secure domination number of G. In this paper, we propose a linear-time algorithm for finding the co-secure domination number of proper interval graphs. [ABSTRACT FROM AUTHOR]

A dominating set D of a graph G is a set of vertices such that any vertex in G is in D or its neighbor is in D. Enumeration of minimal dominating sets in a graph is one of the central problems in enumeration study since enumeration of minimal dominating sets corresponds to the enumeration of minimal hypergraph transversals. The output-polynomial time enumeration of minimal hypergraph transversals is an interesting open problem. On the other hand, enumeration of dominating sets including non-minimal ones has not been received much attention. In this paper, we address enumeration problems for dominating sets from sparse graphs which are degenerate graphs and graphs with large girth, and we propose two algorithms for solving the problems. The first algorithm enumerates all the dominating sets for a k -degenerate graph in O k time per solution using O n + m space, where n and m are respectively the number of vertices and edges in an input graph. That is, the algorithm is optimal for graphs with constant degeneracy such as trees, planar graphs, H -minor free graphs with some fixed H. The second algorithm enumerates all the dominating sets in constant time per solution for input graphs with girth at least nine. [ABSTRACT FROM AUTHOR]

In this paper, we study the dualization in distributive lattices, a generalization of the well-known hypergraph dualization problem. We in particular propose equivalent formulations of the problem in terms of graphs, hypergraphs, and posets. It is known that hypergraph dualization amounts to generate all minimal transversals of a hypergraph, or all minimal dominating sets of a graph. In this new framework, a poset on vertices is given together with the input (hyper)graph, and minimal "ideal solutions" are to be generated. This in particular allows us to study the complexity of the problem under various combined restrictions on graph classes and poset types, including bipartite, split, and co-bipartite graphs, and variants of neighborhood inclusion posets. For example, we show that while the enumeration of minimal dominating sets is possible with linear delay in split graphs, the problem, within the same class, gets as hard as for general graphs when generalized to this framework. More surprisingly, this result holds even when the poset is only comparing vertices with included neighborhoods in the graph. If both the poset and the graph class are sufficiently restricted, we show that the dualization is tractable relying on existing algorithms from the literature. [ABSTRACT FROM AUTHOR]