Total domination in interval graphs

A total dominating set of a graph G is a subset S of nodes such that each node of G is adjacent to some node of S. We present an O(n²) time algorithm for finding a minimum cardinality total dominating set in an interval graph (one which represents intersecting intervals on the line) by reducing it to a shortest path problem on an appropriate acyclic directed network.     

On the complexity of signed and minus total domination in graphs

In this paper we present unified methods to solve the minus and signed total domination problems for chordal bipartite graphs and trees in O(n²) and O(n+m) time, respectively. We also prove that the decision problem for the signed total domination problem on doubly chordal graphs is NP-complete. Note that bipartite permutation graphs, biconvex bipartite graphs, and convex bipartite graphs are subclasses of chordal bipartite graphs.     

Total coloring of planar graphs with maximum degree 7

In the paper, it is proved that a planar graph of maximum degree Δ?7 is (Δ+1)-totally-colorable if no 3-cycle has a common vertex with a 4-cycle or no 3-cycle is adjacent to a cycle of length less than 6.     

Efficient dominating sets in circulant graphs with domination number prime

Cayley graphs of finite cyclic group ${\mathbb{Z}}_n$ are called circulant graphs and denoted by $\mathrm{Cay}({\mathbb{Z}}_n,S)$. For $\mathrm{Cay}({\mathbb{Z}}_n,S)$ with $\frac{n}{|S|+1}$ prime, we give a necessary and sufficient condition for the existence of efficient dominating sets and characterize completely all its efficient dominating sets.     

完全支配集的规约算法

完全支配集是一个著名的NP难解问题,在无线传感器网络中具有重要应用。主要研究了能降低问题规模的规约化算法设计。通过对问题结构进行深入分析并对图中顶点进行着色,得到图中顶点之间的新的组合特性,在此基础上提出一系列高效的多项式时间的局部规约规则。证明了规约规则的正确性,并通过仿真实验验证了规约规则的有效性。     

APX-hardness of domination problems in circle graphs

We show that the problem of finding a minimum dominating set in a circle graph is APX-hard: there is a constant δ>0 such that there is no (1+δ)-approximation algorithm for the minimum dominating set problem on circle graphs unless P=NP. Hence a PTAS for this problem seems unlikely. This hardness result complements the (2+?)-approximation algorithm for the problem [M. Damian, S.V. Pemmaraju, A (2+?)-approximation scheme for minimum domination on circle graphs, J. Algorithms 42 (2) (2002) 255-276].     

Ranking numbers of graphs

Given a graph G, a vertex ranking (or simply, ranking) of G is a mapping f from V(G) to the set of all positive integers, such that for any path between two distinct vertices u and v with f(u)=f(v), there is a vertex w in the path with f(w)>f(u). If f is a ranking of G, the ranking number of G under f, denoted γf(G), is defined by , and the ranking number of G, denoted γ(G), is defined by . The vertex ranking problem is to determine the ranking number γ(G) of a given graph G. This problem is a natural model for the manufacturing scheduling problem. We study the ranking numbers of graphs in this paper. We consider the relation between the ranking numbers and the minimal cut sets, and the relation between the ranking numbers and the independent sets. From this, we obtain the ranking numbers of the powers of paths and the powers of cycles, the Cartesian product of P₂ with Pn or Cn, and the caterpilars. And we also find the vertex ranking numbers of the composition of two graphs in this paper.     

求解圆盘图中最小连通支配集的近似算法

针对无线传感器网络常用的拓扑模型单位圆盘图,提出了基于分布式贪心策略的近似算法DDT,在算法执行的每一轮中,根据一跳邻域范围内的权值和邻居的状态信息,选举出节点并和已确定的节点连接,逐步构造出网络图中的一个支配树。用概率方法研究了支配树中的节点度的性质,通过对极大独立集和最小连通支配集之间关系的分析,得到单位圆盘图中最小连通支配集问题一个新的近似比。计算结果表明,和相关的分布式算法相比,DDT产生的连通支配集在规模上更优。     

The greedy algorithm for domination in graphs of maximum degree 3

We show that for a connected graph with n nodes and e edges and maximum degree at most 3, the size of the dominating set found by the greedy algorithm is at most if , if , and if .     

Dominating set is fixed parameter tractable in claw-free graphs

We show that the Dominating Set problem parameterized by solution size is fixed-parameter tractable (FPT) in graphs that do not contain the claw (K_1,3, the complete bipartite graph on four vertices where the two parts have one and three vertices, respectively) as an induced subgraph. We present an algorithm that uses 2^O(k2)n^O(1) time and polynomial space to decide whether a claw-free graph on n vertices has a dominating set of size at most k. Note that this parameterization of Dominating Set is W[2]-hard on the set of all graphs, and thus is unlikely to have an FPT algorithm for graphs in general.The most general class of graphs for which an FPT algorithm was previously known for this parameterization of Dominating Set is the class of K_i,j-free graphs, which exclude, for some fixed i,j∈N, the complete bipartite graph K_i,j as a subgraph. For i,j≥2, the class of claw-free graphs and any class of K_i,j-free graphs are not comparable with respect to set inclusion. We thus extend the range of graphs over which this parameterization of Dominating Set is known to be fixed-parameter tractable.We also show that, in some sense, it is the presence of the claw that makes this parameterization of the Dominating Set problem hard. More precisely, we show that for any t≥4, the Dominating Set problem parameterized by the solution size is W[2]-hard in graphs that exclude the t-claw K_1,t as an induced subgraph. Our arguments also imply that the related Connected Dominating Set and Dominating Clique problems are W[2]-hard in these graph classes.Finally, we show that for any t∈N, the Clique problem parameterized by solution size, which is W[1]-hard on general graphs, is FPT in t-claw-free graphs. Our results add to the small and growing collection of FPT results for graph classes defined by excluded subgraphs, rather than by excluded minors.     

Dominating sets in directed graphs

We consider the problem of incrementally computing a minimal dominating set of a directed graph after the insertion or deletion of a set of arcs. Earlier results have either focused on the study of the properties that minimum (not minimal) dominating sets preserved or lacked to investigate which update affects a minimal dominating set and in what ways. In this paper, we first show how to incrementally compute a minimal dominating set on arc insertions. We then reduce the case of computing a minimal dominating set on arc deletions to the case of insertions. Some properties on minimal dominating sets are provided to support the incremental strategy. Lastly, we give a new bound on the size of minimum dominating sets based on those results.     

A general method in the theory of domination in graphs

In this article, we present a method to derive inequalities involving various domination parameters in graphs. As an application, we determine several lower bounds for these domination parameters in trees in terms of the order and the number of leaves. Finally, we characterize the classes of extremal trees.     

Perfect secret sharing scheme based on vertex domination set

Due to the fast development in data communication systems and computer networks in recent years, the necessity to protect the secret data has become extremely imperative. Several methods have been proposed to protect the secret data; one of them is the secret sharing scheme. It is a method of distributing a secret K among a finite set of participants, in such a way that only predefined subset of participant is enabled to reconstruct a secret from their shares. A secret sharing scheme realizing uniform access structure described by a graph has received a considerable attention. In this scheme, each vertex represents a participant and each edge represents a minimum authorized subset. In this paper, an independent dominating set of vertices in a graph G is introduced and applied as a novel idea to construct a secret sharing scheme such that the vertices of the graph represent the participants and the dominating set of vertices in G represents the minimal authorized set. While most of the previous schemes were based on the principle of adjacent vertices, the proposed scheme is based upon the principle of non-adjacent vertices. We prove that the scheme is perfect, and the lower bound of the information rate of this new construction is improved when compared to some well-known previous constructions. We include an experiment involving security threats to demonstrate the effectiveness of the proposed scheme.     

Vertex-neighbour-integrity of composition graphs of paths and cycles

A vertex subversion strategy of a graph G is a set of vertices X? V(G) whose closed neighbourhood is deleted from G. The survival subgraph is denoted by G/X. The vertex-neighbour-integrity of G is defined to be VNI(G)=min{|X|+τ(G/X):X? V(G)}, where τ(G/X) is the maximum order of the components of G/X. This graph parameter was introduced by Cozzens and Wu to measure the vulnerability of spy networks. Gambrell proved that the decision problem of computing the vertex-neighbour-integrity of a graph is 𝒩𝒫-complete. In this paper we evaluate the vertex-neighbour-integrity of the composition graphs of paths and cycles.