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]

The problems of recognizing series–parallel graphs, outerplanar graphs, and generalized series–parallel graphs have been studied separately in the past. Efficient algorithms have been presented. However, none of the algorithms are certifying. A certifying algorithm generates, in addition to its answer, a certificate that can be used by a checker (a separate algorithm) to verify the correctness of the answer. The certificate is positive if the answer is 'yes', and is negative if the answer is 'no'. In this paper, an O (| E | + | V |) -time certifying algorithm that simultaneously determines if a graph G = (V , E) is series–parallel, outerplanar, or generalized series–parallel is presented. The positive certificates are a construction sequence for constructing G if G is series–parallel, a generalized construction sequence for constructing G if G is generalized series–parallel but not series–parallel, and the edge set of the exterior boundary of an outerplanar embedding of G if G is outerplanar. The negative certificates are forbidden subgraphs or forbidden structures of G. All these certificates are generated by making only one pass over G after a preprocessing step decomposing G into its biconnected components. [ABSTRACT FROM AUTHOR]

In this paper, we study the complexity of the edge monitoring problem. A vertex v monitors an edge e if both endpoints together with v form a triangle in the graph. Given a graph G = (V , E) and a weight function on edges c where c (e) is the number of monitors that needs the edge e , the problem is to seek a minimum subset of monitors S such that every edge e in the graph is monitored by at least c (e) vertices in S. Therefore, we study the edge monitoring problem on several graph classes such as complete graphs, block graphs, cographs, split graphs, interval graphs and planar graphs. We also generalize the problem by adding weights on vertices. [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]

A double Roman dominating function (DRDF) on a graph G = (V , E) is a function f : V ⟶ { 0 , 1 , 2 , 3 } such that every vertex v ∈ V with f (v) = 0 is either adjacent to a vertex u with f (u) = 3 or two distinct vertices x and y with f (x) = f (y) = 2 , and every vertex v ∈ V with f (v) = 1 is adjacent to a vertex u with f (u) ≥ 2. The weight of f is the sum f (V) = ∑ v ∈ V f (v). The minimum weight of a DRDF on G is the double Roman domination number of G , denoted by γ d R (G). A graph G is a double Roman Graph if γ d R (G) = 3 γ (G) , where γ (G) is the domination number of G. In this paper, we first show that the decision problem associated to double Roman domination is NP-complete even when restricted to planar graphs. Then, we study the complexity issue of a problem posed in [R.A. Beeler, T.W. Haynesa and S.T. Hedetniemi, Double Roman domination, Discrete Appl. Math. 211 (2016), 23–29], and show that the problem of deciding whether a given graph is double Roman is NP-hard even when restricted to bipartite or chordal graphs. Then, we give linear algorithms that compute the domination number and the double Roman domination number of a given unicyclic graph. Finally, we give a linear algorithm that decides whether a given unicyclic graph is double Roman. [ABSTRACT FROM AUTHOR]

Abstract A planar graph can be drawn without edge crossings in the plane. It is well known that testing planarity of a graph can be solved in linear time. A graph is 1-planar, if it admits a 1-planar embedding, where each edge has at most one crossing. Testing 1-planarity of a graph is known to be NP-complete. This paper initiates the problem of testing 2-planarity of a graph, in particular, testing "full-outer-2-planarity" of a graph. A graph is outer- k -planar for an integer k ≥ 0 , if it admits an outer- k -planar embedding , that is, every vertex is on the outer boundary and no edge has more than k crossings. A graph is full-outer- k -planar , if it admits a full-outer- k -planar embedding , that is, an outer- k -planar embedding such that no crossing appears along the outer boundary. We present several structural properties of triconnected outer-2-planar graphs and full-outer-2-planar graphs, and prove that every triconnected full-outer-2-planar graph has a constant number of full-outer-2-planar embeddings. Based on these properties, we present linear-time algorithms for testing full-outer-2-planarity of a graph G , where G is connected, biconnected or triconnected. The algorithm also produces a full-outer-2-planar embedding of a graph, if it exists. Moreover, we show that every outer- k -planar embedding admits a straight-line drawing. [ABSTRACT FROM AUTHOR]