Tight bounds for eternal dominating sets in graphs

The eternal domination number of a graph is the number of guards needed at vertices of the graph to defend the graph against any sequence of attacks at vertices. We consider the model in which at most one guard can move per attack and a guard can move across at most one edge to defend an attack. We prove that there are graphs G for which , where γ_∞(G) is the eternal domination number of G and α(G) is the independence number of G. This matches the upper bound proved by Klostermeyer and MacGillivray.     

The dominating set problem is fixed parameter tractable for graphs of bounded genus

We describe an algorithm for the dominating set problem with time complexity O((4g+40)^kn²) for graphs of bounded genus g1, where k is the size of the set. It has previously been shown that this problem is fixed parameter tractable for planar graphs. We give a simpler proof for the previous O(8^kn²) result for planar graphs. Our method is a refinement of the earlier techniques.     

Finding minimum dominating cycles in permutation graphs

A dominating cycle for a graph G = (V, E) is a subset C of V which has the following properties: (i) the subgraph of G induced by C has a Hamiltonian cycle, and (ii) every vertex of V is adjacent to some vertex of C. In this paper, we develop an O(n²) algorithm for finding a minimum cardinality dominating cycle in a permutation graph. We also show that a minimum cardinality dominating cycle in a permutation graph always has an even number of vertices unless it is isomorphic to C₃.     

构建最小k 重控制集的概率算法

点集D ⊆ V (G) 称为图G 的k 重控制集, 如果D 满足V (G) - D 中任意结点在D 中至少有k 个邻居. 在无线网络中, 最小k 重控制集(MkDS) 用以构建健壮的虚拟骨干网. 构建虚拟骨干网是无线网络中最基本也是最重要的问题. 在本文中, 我们提出一种快速的分布式概率算法来构建k重控制集. 我们构建的k 重控制集的期望大小不超过最优解的O(k²) 倍. 算法的运行时间复杂度为O((Δ logΔ+log log n)n),其中Δ = max{|D(p)|}, D(p) 是以p 为中心半径为1 的圆盘中的结点, 最大值的比较范围是给定集合中所有的p 点.     

On finding augmenting graphs

Method of augmenting graphs is a general approach to solve the maximum independent set problem. As the problem is generally NP-hard, no polynomial time algorithms are available to implement the method. However, when restricted to particular classes of graphs, the approach may lead to efficient solutions. A famous example of this type is the maximum matching algorithm: it finds a maximum matching in a graph G, which is equivalent to finding a maximum independent set in the line graph of G. In the particular case of line graphs, the method reduces to finding augmenting (alternating) chains. Recent investigations of more general classes of graphs revealed many more types of augmenting graphs. In the present paper we study the problem of finding augmenting graphs different from chains. To simplify this problem, we introduce the notion of a redundant set. This allows us to reduce the problem to finding some basic augmenting graphs. As a result, we obtain a polynomial time solution to the maximum independent set problem in a class of graphs which extends several previously studied classes including the line graphs.     

A note on the complexity of minimum dominating set

The currently (asymptotically) fastest algorithm for minimum dominating set on graphs of n nodes is the trivial Ω(2ⁿ) algorithm which enumerates and checks all the subsets of nodes. In this paper we present a simple algorithm which solves this problem in O(1.81ⁿ) time.     

On the approximability of the maximum induced matching problem

In this paper we consider the approximability of the maximum induced matching problem (MIM). We give an approximation algorithm with asymptotic performance ratio d−1 for MIM in d-regular graphs, for each d3. We also prove that MIM is APX-complete in d-regular graphs, for each d3.     

The parameterized complexity of the induced matching problem

Given a graph G and an integer k≥0, the NP-complete Induced Matching problem asks whether there exists an edge subset M of size at least k such that M is a matching and no two edges of M are joined by an edge of G. The complexity of this problem on general graphs, as well as on many restricted graph classes has been studied intensively. However, other than the fact that the problem is W[1]-hard on general graphs, little is known about the parameterized complexity of the problem in restricted graph classes. In this work, we provide first-time fixed-parameter tractability results for planar graphs, bounded-degree graphs, graphs with girth at least six, bipartite graphs, line graphs, and graphs of bounded treewidth. In particular, we give a linear-size problem kernel for planar graphs.     

Maximum induced matching problem on hhd-free graphs

We show that the maximum induced matching problem can be solved on hhd-free graphs in O(m²) time; hhd-free graphs generalize chordal graphs and the previous best bound was O(m³). Then, we consider a technique used by Brandstädt and Hoàng (2008) [4] to solve the problem on chordal graphs. Extending this, we show that for a subclass of hhd-free graphs that is more general than chordal graphs the problem can be solved in linear time. We also present examples to demonstrate the tightness of our results.     

On restricted domination in graphs

The k-restricted domination number of a graph G is the minimum number d _k such that for any subset U of k vertices of G, there is a dominating set in G including U and having at most d _k vertices. Some new upper bounds in terms of order and degrees for this number are found.      

On the maximum number of minimum dominating sets in forests

Fricke, Hedetniemi, Hedetniemi, and Hutson asked whether every tree with domination number $\gamma$ has at most $2^{\gamma }$ minimum dominating sets. Bień gave a counterexample, which allows us to construct forests with domination number $\gamma$ and $2.0598^{\gamma }$ minimum dominating sets. We show that every forest with domination number $\gamma$ has at most $2.4606^{\gamma }$ minimum dominating sets, and that every tree with independence number $\alpha$ has at most $2^{\alpha -1}+1$ maximum independent sets.     

Independent domination in chordal graphs

A graph chordal if it does not contain any cycle of length greater than three as an induced subgraph. A set of S of vertices of a graph G = (V,E) is independent if not two vertices in S are adjacent, and is dominating if every vertex in V?S is adjacent to some vertex in S. We present a linear algorithm to locate a minimum weight independent dominating set in a chordal graph with 0–1 vertex weights.     

The complexity of the matching‐cut problem for planar graphs and other graph classes

The Matching‐Cut problem is the problem to decide whether a graph has an edge cut that is also a matching. Previously this problem was studied under the name of the Decomposable Graph Recognition problem, and proved to be ‐complete when restricted to graphs with maximum degree four. In this paper it is shown that the problem remains ‐complete for planar graphs with maximum degree four, answering a question by Patrignani and Pizzonia. It is also shown that the problem is ‐complete for planar graphs with girth five. The reduction is from planar graph 3‐colorability and differs from earlier reductions. In addition, for certain graph classes polynomial time algorithms to find matching‐cuts are described. These classes include claw‐free graphs, co‐graphs, and graphs with fixed bounded tree‐width or clique‐width. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 109–126, 2009