Search

We prove the following theorem. Given a planar graph $G$ and an integer $k$, it is possible in polynomial time to randomly sample a subset $A$ of vertices of $G$ with the following properties: (i) $A$ induces a subgraph of $G$ of treewidth $\mathcal{O}(\sqrt{k}\log k)$, and (ii) for every connected subgraph $H$ of $G$ on at most $k$ vertices, the probability that $A$ covers the whole vertex set of $H$ is at least $(2^{\mathcal{O}(\sqrt{k}\log^2 k)}\cdot n^{\mathcal{O}(1)})^{-1}$, where $n$ is the number of vertices of $G$. Together with standard dynamic programming techniques for graphs of bounded treewidth, this result gives a versatile technique for obtaining (randomized) subexponential parameterized algorithms for problems on planar graphs, usually with running time bound $2^{\mathcal{O}(\sqrt{k} \log^2 k)} n^{\mathcal{O}(1)}$. The technique can be applied to problems expressible as searching for a small, connected pattern with a prescribed property in a large host graph, examples of such problems include Directed $k$-Path, Weighted $k$-Path, Vertex Cover Local Search, and Subgraph Isomorphism, among others. Up to this point, it was open whether these problems can be solved in subexponential parameterized time on planar graphs, because they are not amenable to the classic technique of bidimensionality. Furthermore, all our results hold in fact on any class of graphs that exclude a fixed apex graph as a minor, in particular on graphs embeddable in any fixed surface.

12th International Symposium on Parameterized and Exact Computation (IPEC 2017); International audience; Given a graph G, we define bcg(G) as the minimum k for which G can be contracted to the uniformly triangulated grid Γk. A graph class G has the SQGC property if every graph G ∈ G has treewidth O(bcg(G)c) for some 1 ≤ c < 2. The SQGC property is important for algo- rithm design as it defines the applicability horizon of a series of meta-algorithmic results, in the framework of bidimensionality theory, related to fast parameterized algorithms, kernelization, and approximation schemes. These results apply to a wide family of problems, namely problems that are contraction-bidimensional. Our main combinatorial result reveals a general family of graph classes that satisfy the SQGC property and includes bounded-degree string graphs. This considerably extends the applicability of bidimensionality theory for several intersection graph classes of 2-dimensional geometrical objects.

It is widely accepted that necessity comes in different varieties, often called ‘kinds': metaphysical necessity, logical necessity, natural necessity, conceptual necessity, moral necessity, to name but a few – and the same goes for the varieties of possibility. What is usually not fully appreciated, however, is that modal variety is not simply ‘unidimensional': it does not only involve one main variable – kind, whose values are the particular kinds of necessity. Rather, I argue, it is ‘bidimensional', involving two distinct variables – domain and strength. In the first part of the paper, I introduce and develop the proposed bidimensional picture of modal variety, defending it against the common, unidimensional one. In the second part, I consider how the main available accounts of necessities and their relations rely, at least to a significant extent, on the latter picture, pointing out important limitations that they face as a result. I also show how, accordingly, alternative accounts based on a clear and systematic distinction between domain and strength would overcome those limitations. I conclude that, beyond the particular bidimensionalist view defended, our understanding of the modal realm may benefit from more direct debate on whether and how it is multidimensional.

Bidimensionality Theory was introduced by [E.D. Demaine, F.V. Fomin, M.Hajiaghayi, and D.M. Thilikos. Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free graphs, J. ACM, 52 (2005), pp.866--893] as a tool to obtain sub-exponential time parameterized algorithms on H-minor-free graphs. In [E.D. Demaine and M.Hajiaghayi, Bidimensionality: new connections between FPT algorithms and PTASs, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2005, pp.590--601] this theory was extended in order to obtain polynomial time approximation schemes (PTASs) for bidimensional problems. In this work, we establish a third meta-algorithmic direction for bidimensionality theory by relating it to the existence of linear kernels for parameterized problems. In particular, we prove that every minor (respectively contraction) bidimensional problem that satisfies a separation property and is expressible in Countable Monadic Second Order Logic (CMSO), admits a linear kernel for classes of graphs that exclude a fixed graph (respectively an apex graph) H as a minor. Our results imply that a multitude of bidimensional problems g graph classes. For most of these problems no polynomial kernels on H-minor-free graphs were known prior to our work., Comment: An an earlier version of this paper appeared in SODA 2010. That paper contained preliminary versions of some of the results of this paper

International audience; For a fixed connected graph H, the {H}-M-Deletion problem asks, given a graph G, for the minimum number of vertices that intersect all minor models of H in G. It is known that this problem can be solved in time f (tw) · n O(1) , where tw is the treewidth of G. We determine the asymptotically optimal function f (tw), for each possible choice of H. Namely, we prove that, under the ETH, f(tw) = 2Θ(tw) if H is a contraction of the chair or the banner, and f(tw) = 2Θ(tw·log tw) otherwise. Prior to this work, such a complete characterization was only known when H is a planar graph with at most five vertices. For the upper bounds, we present an algorithm in time 2Θ(tw·log tw) ·nO(1) for the more general problem where all minor models of connected graphs in a finite family F need to be hit. We combine several ingredients such as the machinery of boundaried graphs in dynamic programming via representatives, the Flat Wall Theorem, Bidimensionality, the irrelevant vertex technique, treewidth modulators, and protrusion replacement. In particular, this algorithm vastly generalizes a result of Jansen et al. [SODA 2014] for the particular case F = {K5, K3,3}. For the lower bounds, our reductions are based on a generic construction building on the one given by the authors in [IPEC 2018], which uses the framework introduced by Lokshtanov et al. [SODA 2011] to obtain superexponential lower bounds.

International audience; In parameterized complexity, a {\em kernelization algorithm} can be seen as a reduction of a parameterized problem to itself, so that the produced equivalent instance has size depending exclusively on the parameter. If this size is polynomial, then then we say that the parameterized problem in question admits a polynomial kernelization algorithm. Kernelization can be seen as a formalization of the notion of preprocessingand has occupied a big part of the research on Multi-variate Algorithmics. The first algorithmic meta-theorem on kernelizationappeared in \href{https://arxiv.org/pdf/0904.0727}{\green{[{\sl H.~L. Bodlaender, F.~V. Fomin, D.~Lokshtanov, E.~Penninkx, S.~Saurabh, and D.~M. Thilikos. (Meta) kernelization. J. {ACM}, 63(5):44:1--44:69, 2016}\,]}} and unified a large family of previously known kernelization results on problems defined on topologically embeddable graphs.In this exposition we present the central results of this paper. During our presentation we pay attention to the abstractions on which the results where founded and take into account the subsequent advancements on this topic.

Two of the most widely used approaches to obtain polynomial-time approximation schemes (PTASs) on planar graphs are the Lipton-Tarjan separator-based approach and Baker’s approach. In 2005, Demaine and Hajiaghayi strengthened both approaches using bidimensionality and obtained efficient polynomial-time approximation schemes (EPTASs) for several problems, including C onnected D ominating S et and F eedback V ertex S et . In this work, we unify the two strengthened approaches to combine the best of both worlds. We develop a framework allowing the design of EPTAS on classes of graphs with the subquadratic grid minor (SQGM) property. Roughly speaking, a class of graphs has the SQGM property if, for every graph G from the class, the fact that G contains no t × t grid as a minor guarantees that the treewidth of G is subquadratic in t . For example, the class of planar graphs and, more generally, classes of graphs excluding some fixed graph as a minor, have the SQGM property. At the heart of our framework is a decomposition lemma stating that for “most” bidimensional problems on a graph class G with the SQGM property, there is a polynomial-time algorithm that, given a graph G ϵ G as input and an ϵ > 0, outputs a vertex set X of size ϵ ċ OPT such that the treewidth of G - X is f (ϵ). Here, OPT is the objective function value of the problem in question and f is a function depending only on ϵ. This allows us to obtain EPTASs on (apex)-minor-free graphs for all problems covered by the previous framework as well as for a wide range of packing problems, partial covering problems and problems that are neither closed under taking minors nor contractions. To the best of our knowledge, for many of these problems—including C ycle P acking , F -P acking , F -D eletion , M ax L eaf S panning T ree , or P artial r -D ominating S et —no EPTASs, even on planar graphs, were previously known. We also prove novel excluded grid theorems in unit disk and map graphs without large cliques. Using these theorems, we show that these classes of graphs have the SQGM property. Based on the developed framework, we design EPTASs and subexponential time parameterized algorithms for various classes of problems on unit disk and map graphs.

Let G be a graph of order n . A subset S of V ( G ) is a dominating set of G if every vertex in V ( G ) ⧹ S is adjacent to at least one vertex of S . The domination polynomial of G is the polynomial D ( G , x ) = ∑ i = γ ( G ) n d ( G , i ) x i , where d ( G , i ) is the number of dominating sets of G of size i , and γ ( G ) is the size of a smallest dominating set of G , called the domination number of G . We say two graphs G and H are dominating equivalent if D ( G , x ) = D ( H , x ) . A graph G is said to be dominating unique , or simply D -unique, if D ( H , x ) = D ( G , x ) implies that H ≅ G . The goal of this paper is to find a new approach to determine the dominating uniqueness of graphs. In this paper, we define a new graph polynomial, called star polynomial, and introduced an analogy notion of star uniqueness of graphs. As an application, if G is a graph without isolated vertices, we show that a graph G is star unique if and only if G ‾ ∨ K m is dominating unique for each m ⩾ 0 . As a by-product, the dominating uniqueness of many families of dense graphs is also determined.

We consider boolean linear programming formulations of the independent set, the vertex and the edge dominating set problems and prove their polynomial-time solvability for classes of graphs with (augmented) constraint matrices having bounded minors in the absolute value.

A total dominating set of an undirected graph G=(V,E) is a set SV of vertices such that each vertex of G is adjacent to at least one vertex of S. A secure total dominating set of G is a set DV of vertices such that D is a total dominating set of G and each vertex vVD is adjacent to at least one vertex uD with the property that the set (D{u}){v} is a total dominating set of G. The secure total domination number st(G) of G is the minimum cardinality of a secure total dominating set of G. We establish bounds on the secure total domination number. In particular, we show that every graph G with no isolated vertices satisfies st(G)2(G), where (G) is the independence number of G. Further, we study the problem of finding the secure total domination number. We show that the decision version of the problem is NP-complete for chordal bipartite graphs, planar bipartite graphs with arbitrary large girth and maximum degree 3, split graphs and graphs of separability at most 2. Finally, we show that the optimisation version of the problem can be approximated in polynomial time within a factor of cln|V| for some constant c>1 and cannot be approximated in polynomial time within a factor of cln|V| for some constant c

A connected dominating set in a graph is a dominating set of vertices that induces a connected subgraph. Following analogous studies in the literature related to independent sets, dominating sets, and total dominating sets, we study in this paper the class of graphs in which the connected dominating sets can be separated from the other vertex subsets by a linear weight function. More precisely, we say that a graph is connected-domishold if it admits non-negative real weights associated to its vertices such that a set of vertices is a connected dominating set if and only if the sum of the corresponding weights exceeds a certain threshold. We characterize the graphs in this non-hereditary class in terms of a property of the set of minimal cutsets of the graph. We give several characterizations for the hereditary case, that is, when each connected induced subgraph is required to be connected-domishold. The characterization by forbidden induced subgraphs implies that the class properly generalizes two well known classes of chordal graphs, the block graphs and the trivially perfect graphs. Finally, we study certain algorithmic aspects of connected-domishold graphs. Building on connections with minimal cutsets and properties of the derived hypergraphs and Boolean functions, we show that our approach leads to new polynomially solvable cases of the weighted connected dominating set problem., 32 pages, 8 figures

A set D of vertices in a graph G = ( V , E ) is called a 2-point set dominating set of G if for every set T ⊆ V − D there exists a non-empty set S ⊆ D containing at most two vertices such that the induced subgraph 〈 S ∪ T 〉 is connected. A set D ⊆ V ( G ) is called a global 2-point set dominating set of G if D is a 2-point set dominating set of both G and G ‾ . The global 2-point set domination number (2-point set domination number) is the minimum cardinality of a global 2-point set dominating set (2-point set dominating set) in G. In this paper we determine bounds on the global 2-point set domination number of a graph in terms of other graph invariants. We have also given relation between global 2-point set domination number and 2-point set domination number for some classes of graphs.

Let G = ( V , E ) be a connected graph, and k a positive integer. A subset D ⊆ V is a k-hop connected dominating set (k-CDS) if the subgraph of G induced by D is connected and, for every vertex v in G, there is a vertex u in D such that the distance between v and u is at most k. We study the problem of finding a minimum k-hop connected dominating set, denoted by the acronym Min k-CDS. Firstly, we prove that Min k-CDS is NP -hard on planar bipartite graphs of maximum degree 4 and on planar biconnected graphs of maximum degree 5. We present an inapproximability threshold for Min k-CDS on bipartite and on (1, 2)-split graphs, and we also prove that Min k-CDS is APX -hard on bipartite graphs of maximum degree 4. These results are shown to hold for every positive integer k. For k = 1 , the classical minimum connected dominating set problem, we present an integer linear programming formulation and show some classes of inequalities that define facets of the corresponding polytope. We also present an approximation algorithm for this case.

Dominating set is a set of vertices of a graph such that all other vertices have a neighbour in the dominating set. We propose a new order-based randomised local search (RLS o) algorithm to solve minimum dominating set problem in large graphs. Experimental evaluation is presented for multiple types of problem instances. These instances include unit disk graphs, which represent a model of wireless networks, random scale-free networks, as well as samples from two social networks and real-world graphs studied in network science. Our experiments indicate that RLS o performs better than both a classical greedy approximation algorithm and two metaheuristic algorithms based on ant colony optimisation and local search. The order-based algorithm is able to find small dominating sets for graphs with tens of thousands of vertices. In addition, we propose a multi-start variant of RLS o that is suitable for solving the minimum weight dominating set problem. The application of RLS o in graph mining is also briefly demonstrated.

Dominating sets play a vital role in day-to-day life problems. For-providing effective services in a location, central points are to be identified. This can easily be achieved by graph theoretic techniques. Such graphs and relevant parameters are introduced and extensively studied. One such parameter is complementary nil vertex edge dominating set(cnved-set). A vertex edge dominating set(ved-set) of a connected graph G with vertex set V is said to be a complementary nil vertex edge dominating set(cnved-Set) of G if and only if V - D is not a ved-set of G. A cnved-set of minimum cardinality is called a minimum cnved-set(mcnved-set)of G and this minimum cardinality is called the complementary nil vertex-edge domination number of G and is denoted by &#947cnve(G). We have given a characterization result for a ved-set to be a cnved-set and also bounds for this parameter are obtained.

Several algorithmic meta-theorems on kernelization have appeared in the last years, starting with the result of Bodlaender et al. [FOCS 2009] on graphs of bounded genus, then generalized by Fomin et al. [SODA 2010] to graphs excluding a fixed minor, and by Kim et al. [ICALP 2013] to graphs excluding a fixed topological minor. Typically, these results guarantee the existence of linear or polynomial kernels on sparse graph classes for problems satisfying some generic conditions but, mainly due to their generality, it is not clear how to derive from them constructive kernels with explicit constants. In this paper we make a step toward a fully constructive meta-kernelization theory on sparse graphs. Our approach is based on a more explicit protrusion replacement machinery that, instead of expressibility in CMSO logic, uses dynamic programming, which allows us to find an explicit upper bound on the size of the derived kernels. We demonstrate the usefulness of our techniques by providing the first explicit linear kernels for $r$-Dominating Set and $r$-Scattered Set on apex-minor-free graphs, and for Planar-\mathcal{F}-Deletion on graphs excluding a fixed (topological) minor in the case where all the graphs in \mathcal{F} are connected., 32 pages

An independent dominating set of a graph G is a subset D of V such that every vertex not in D is adjacent to at least one vertex of D and no two vertices in D are adjacent. The independent dominating set (IDS) problem asks for an independent dominating set with minimum cardinality. First, we show that the independent dominating set problem and the dominating set problem on cubic bipartite graphs are both NP-complete. As an additional result, we give an alternative and more direct proof for the NP-completeness of both the independent dominating set problem and the dominating set problem on at-most-cubic grid graphs. Next, we show that there are fixed-parameter tractable algorithms for the independent dominating set problem and the dominating set problem on at-most-cubic graphs, which run in O ( 3.3028 k + n ) and O ( 4.2361 k + n ) time, respectively. Moreover, we consider the weighted independent dominating set problem on ( k , ? ) -graphs. We show that the problem on ( 2 , 1 ) -graphs is NP-complete. We also show that the problem can be solved in linear time for ( 1 , 1 ) -graphs and in polynomial time for ( 1 , ? ) -graphs for constant ?, respectively.

International audience; A dominating set in a graph is a subset of vertices such that each vertex is either in the dominating set or adjacent to some vertex in the dominating set. It is known that graphs have at most O(1.7159^n) minimal dominating sets. In this paper, we establish upper bounds on this maximum number of minimal dominating sets for split graphs, cobipartite graphs and interval graphs. For each of these graph classes, we provide an algorithm to enumerate them. For split and interval graphs, we show that the number of minimal dominating sets is at most 3^(n/3) \approx 1.4423^n, which is the best possible bound. This settles a conjecture by Couturier et al. (SOFSEM 2012). For cobipartite graphs, we lower the O(1.5875^n) upper bound from Couturier et al. to O(1.4511^n).

A 2-directional orthogonal ray graph is an intersection graph of rightward rays (half-lines) and downward rays in the plane. We show a dynamic programming algorithm that solves the weighted dominating set problem in O(n(3)) time for 2-directional orthogonal ray graphs, where n is the number of vertices of a graph.

A set $D$ of vertices of a graph $G$ is locating if every two distinct vertices outside $D$ have distinct neighbors in $D$; that is, for distinct vertices $u$ and $v$ outside $D$, $N(u) \cap D \neq N(v) \cap D$, where $N(u)$ denotes the open neighborhood of $u$. If $D$ is also a dominating set (total dominating set), it is called a locating-dominating set (respectively, locating-total dominating set) of $G$. A graph $G$ is twin-free if every two distinct vertices of $G$ have distinct open and closed neighborhoods. It is conjectured [D. Garijo, A. Gonzalez and A. Marquez, The difference between the metric dimension and the determining number of a graph. Applied Mathematics and Computation 249 (2014), 487--501] and [F. Foucaud and M. A. Henning. Locating-total dominating sets in twin-free graphs: a conjecture. The Electronic Journal of Combinatorics 23 (2016), P3.9] respectively, that any twin-free graph $G$ without isolated vertices has a locating-dominating set of size at most one-half its order and a locating-total dominating set of size at most two-thirds its order. In this paper, we prove these two conjectures for the class of line graphs. Both bounds are tight for this class, in the sense that there are infinitely many connected line graphs for which equality holds in the bounds., Comment: 23 pages, 2 figures

Given a vertex-weighted graph \(G=(V,E)\) and a set \(S \subseteq V\), a subset feedback vertex set X is a set of the vertices of G such that the graph induced by \(V \setminus X\) has no cycle containing a vertex of S. The Subset Feedback Vertex Set problem takes as input G and S and asks for the subset feedback vertex set of minimum total weight. In contrast to the classical Feedback Vertex Set problem which is obtained from the Subset Feedback Vertex Set problem for \(S=V\), restricted to graph classes the Subset Feedback Vertex Set problem is known to be NP-complete on split graphs and, consequently, on chordal graphs. Here we give the first polynomial-time algorithms for the problem on two subclasses of AT-free graphs: interval graphs and permutation graphs. Moreover towards the unknown complexity of the problem for AT-free graphs, we give a polynomial-time algorithm for co-bipartite graphs. Thus we contribute to the first positive results of the Subset Feedback Vertex Set problem when restricted to graph classes for which Feedback Vertex Set is solved in polynomial time.

The class of D - dotted interval ( d -DI) graphs is the class of intersection graphs of arithmetic progressions with jump (common difference) at most d . We consider various classical graph-theoretic optimization problems in d -DI graphs of arbitrarily, but fixed, d . We show that Maximum Independent Set , Minimum Vertex Cover , and Minimum Dominating Set can be solved in polynomial time in this graph class, answering an open question posed by Jiang (2006). We also show that Minimum Vertex Cover can be approximated within a factor of ( 1 + e ) , for any e > 0 , in linear time. This algorithm generalizes to a wide class of deletion problems including the classical Minimum Feedback Vertex Set and Minimum Planar Deletion problems. Our algorithms are based on classical results in algorithmic graph theory and new structural properties of d -DI graphs that may be of independent interest.

This paper deals with the FEEDBACK VERTEX SET problem on undirected graphs, which asks for the existence of a vertex set of bounded size that intersects all cycles. Due it is theoretical and practical importance, the problem has been the subject of intensive study. Motivated by the parameter ecology program we attempt to classify the parameterized and kernelization complexity of FEEDBACK VERTEX SET for a wide range of parameters. We survey known results and present several new complexity classifications. For example, we prove that FEEDBACK VERTEX SET is fixed-parameter tractable parameterized by the vertex-deletion distance to a chordal graph. We also prove that the problem admits a polynomial kernel when parameterized by the vertex-deletion distance to a pseudo forest, a graph in which every connected component has at most one cycle. In contrast, we prove that a slightly smaller parameterization does not allow for a polynomial kernel unless NP ⊆ coNP=poly and the polynomial-time hierarchy collapses.

We study dominating sets whose induced subgraphs have a bounded diameter. Such sets were used in recent papers by Kim et al. and Yu et al. to model virtual backbones in wireless networks where the number of hops required to forward messages within the backbone is minimized. We prove that for any fixed k>=1 it is NP-complete to decide whether a given graph admits a dominating set whose induced subgraph has diameter at most k. On the upside, we give a characterization of the chordal graphs that admit such a dominating set. It turns out that in this characterization, the dominating set X can be chosen such that any shortest path between two members of the dominating set is entirely contained in X. Moreover, the characterization yields an O(mn) algorithm to compute, for a given connected chordal graph G on n vertices and m edges, the minimum k for which G has a dominating set whose induced subgraph has diameter at most k. Such a dominating set can be efficiently computed.

An edge dominating set of a graph G=(V,E) is a subset [email protected]?E of edges in the graph such that each edge in E-M is incident with at least one edge in M. In an instance of the parameterized edge dominating set problem, we are given a graph G=(V,E) and an integer k, and we are asked to decide whether G has an edge dominating set of size at most k. In this paper, we show that the parameterized edge dominating set problem can be solved in O^*(2.3147^k) time and polynomial space. We also show that this problem can be reduced to a quadratic kernel with O(k^3) edges.

In this paper, we study the Planar Connected Dominating Set problem, which, given a planar graph G=(V,E) and a non-negative integer k, asks for a subset [email protected]?V with |D|@?k such that D forms a dominating set of G and induces a connected graph. Answering an open question posed at the 2nd Workshop on Kernelization (WorKer 2010), we provide a kernelization algorithm for this problem, leading to a problem kernel with at most 130k vertices, improving the previously best upper bound on the kernel size. To this end, we incorporate a vertex coloring technique with data reduction rules and introduce a type distinction of regions into the region decomposition framework, which allows a refined analysis of the region size.

In this paper, we present an O^*(2.1479^k)-time algorithm to decide whether a graph of maximum degree 3 has an edge dominating set of size at most k or not, which is based on enumeration of vertex covers and improves all previous results on this problem. We first enumerate partial vertex covers of size at most 2k and then construct an edge dominating set based on each vertex cover to find a required edge dominating set. To effectively enumerate vertex covers, we adopt a branch-and-reduce method, and use some techniques, such as 'pseudo-cliques' and 'amortized transfer of cliques,' to analyze the running time bound.

A dominating set is called a global dominating set if it is a dominating set for a graph G and its complement G. We investigate some general results for global dominating sets corresponding to the graphs Pn, Cn and Wn.

A simple partition of the vertex set of a graph is introduced to analyze kernels for planar graph problems in which vertices and edges not in a solution have small distance to the solution. This method directly leads to improved kernel sizes for several problems, without needing new reduction rules. Moreover, new kernelization algorithms are developed for Connected Vertex Cover, Edge Dominating Set, and Maximum Triangle Packing problems, further improving the kernel sizes for these problems. Highlights? We propose a vertex-partition method for deriving linear kernels for planar graph problems. ? We improve the linear kernel for Connected Vertex Cover on planar graphs from 14k to 4k. ? We improve the linear kernel for Edge Dominating Set on planar graphs from 28k to 12k. ? We improve the linear kernel for Maximum Triangle Packing on planar graphs from 624k to 75k.

Cayley graphs are graphs constructed out of a finite group @C and its generating set A. Circulant graphs are Cayley graphs corresponding to finite cyclic groups. In this paper, the value of the domination number for some circulant graphs is obtained and a corresponding dominating set is also determined. At last a necessary and sufficient condition for a subgroup to be an efficient dominating set in circulant graphs is also obtained.

A set S of vertices in a graph G is an independent dominating set of G if S is an independent set and every vertex not in S is adjacent to a vertex in S . In this paper, we offer a survey of selected recent results on independent domination in graphs.

Let G be a simple graph. A set S⊆V is a dominating set of G, if every vertex in V∖S is adjacent to at least one vertex in S. We denote the family of dominating sets of a graph G with cardinality i by 𝒟(G,i). In this paper we introduce graphs with specific constructions, which are denoted by G(m). We construct the dominating sets of G(m) by dominating sets of graphs G(m−1), G(m−2), and G(m−3). As an example of G(m), we consider 𝒟(Pn,i). As a consequence, we obtain the recursive formula for the number of dominating sets of G(m).

Given a graph G = (V, E) together with a nonnegative integer requirement on vertices r : V → Z+, the annotated edge dominating set problem is to find a minimum set M ⊆ E such that, each edge in E − M is adjacent to some edge in M, and M contains at least r(v) edges incident on each vertex v ∈ V . The annotated edge dominating set problem is a natural extension of the classical edge dominating set problem, in which the requirement on vertices is zero. The edge dominating set problem is an important graph problem and has been extensively studied. It is well known that the problem is NP-hard, even when the graph is restricted to a planar or bipartite graph with maximum degree 3. In this paper, we show that the annotated edge dominating set problem in graphs with maximum degree 3 can be solved in O∗(1.2721n) time and polynomial space, where n is the number of vertices in the graph. We also show that there is an O∗(2.2306k)-time polynomial-space algorithm to decide whether a graph with maximum degree 3 has an annotated edge dominating set of size k or not. key words: edge dominating sets, exact algorithms, cubic graphs

A dominating set is a subset of the nodes of a graph such that all nodes are in the set or adjacent to a node in the set. A minimum dominating set approximation is a dominating set that is not much larger than a dominating set with the fewest possible number of nodes. This article summarizes the state-of-the-art with respect to finding minimum dominating set approximations in distributed systems, where each node locally executes a protocol on its own, communicating with its neighbors in order to achieve a solution with good global properties. Moreover, we present a number of recent results for specific families of graphs in detail. A unit disk graph is given by an embedding of the nodes in the Euclidean plane, where two nodes are joined by an edge exactly if they are in distance at most one. For this family of graphs, we prove an asymptotically tight lower bound on the trade-off between time complexity and approximation ratio of deterministic algorithms. Next, we consider graphs of small arboricity, whose edge sets can be decomposed into a small number of forests. We give two algorithms, a randomized one excelling in its approximation ratio and a uniform deterministic one which is faster and simpler. Finally, we show that in planar graphs, which can be drawn in the Euclidean plane without intersecting edges, a constant approximation factor can be ensured within a constant number of communication rounds.

A dominating set D of a graph G = (V;E) is non-split dominating set ifhV n Di is connected. The non-split domination number of G is the minimum cardinality of a non-split dominating set inG. LetD be a minimum dominating set inG. If a subset D 0 of V n D is dominating in G, then D 0 is called an inverse dominating set with respect to D. Furthermore, if

A set S of vertices in a graph G is an independent dominating set of G if S is an independent set and every vertex not in S is adjacent to a vertex in S. In this paper, we consider questions about independent domination in regular graphs.

Let G = (V, E) be a simple graph. A set is a dominating set if every vertex in V(G) \ D is adjacent to a vertex of D. A dominating set D of a graph G is a complementary tree dominating set if induced sub graph (V \ D) is a tree. The domination (complementary tree domination, respectively) number of G is the minimum cardinality of a dominating (complementary tree dominating, respectively) set of G. We characterize all unicyclic graphs with equal domination and complementary tree domination numbers.

Given a vertex-coloured graph, a dominating set is said to be tropical if every colour of the graph appears at least once in the set. Here, we study minimum tropical dominating sets from structural and algorithmic points of view. First, we prove that the tropical dominating set problem is NP-complete even when restricted to a simple path. Last, we give approximability and inapproximability results for general and restricted classes of graphs, and establish a FPT algorithm for interval graphs.

Source: DOI: 10.1021/acs.jpcc.6b05309 The e ect of surfaces and interfaces on the structure and properties of molecules is of a great interest in a number of biological and technological applications. Nevertheless, such an investigation is extremely challenging from an experimental point of view, due to the bidimensionality of the environment. In recent years, we have developed a framework to study molecules at surfaces and interfaces, by means of a continuum approach. In the present study, we extend our model by showing the e ect of interfacial solvation on molecular properties and by re ning the description of the transfer process, making use of a proper Boltzmann averaging of the orientational degrees of freedom. Our ndings are in substantial agreement with previous simulations, for the energetics of the transfer process, but yield a somehow di erent description of the molecular electronic structure. Both the agreement on the energetics and the disagreement on the properties are motivated in light of the role played by non-electrostatic e ects in the solvation process.