Home  About us  Contact
 

Dominating Set (dominating + set)

Distribution by Scientific Domains
Mathematics and Statistics60%

Selected Abstracts

Dispersion of Nodes Added to a Network

GEOGRAPHICAL ANALYSIS, Issue 4 2005
Michael Kuby
For location problems in which optimal locations can be at nodes or along arcs but no finite dominating set has been identified, researchers may desire a method for dispersing p additional discrete candidate sites along the m arcs of a network. This article develops and tests minimax and maximin models for solving this continuous network location problem, which we call the added-node dispersion problem (ANDP). Adding nodes to an arc subdivides it into subarcs. The minimax model minimizes the maximum subarc length, while the maximin model maximizes the minimum subarc length. Like most worst-case objectives, the minimax and maximin objectives are plagued by poorly behaved alternate optima. Therefore, a secondary MinSumMax objective is used to select the best-dispersed alternate optima. We prove that equal spacing of added nodes along arcs is optimal to the MinSumMax objective. Using this fact we develop greedy heuristic algorithms that are simple, optimal, and efficient (O(mp)). Empirical results show how the maximum subarc, minimum subarc, and sum of longest subarcs change as the number of added nodes increases. Further empirical results show how using the ANDP to locate additional nodes can improve the solutions of another location problem. Using the p-dispersion problem as a case study, we show how much adding ANDP sites to the network vertices improves the p-dispersion objective function compared with (a) network vertices only and (b) vertices plus randomly added nodes. The ANDP can also be used by itself to disperse facilities such as stores, refueling stations, cell phone towers, or relay facilities along the arcs of a network, assuming that such facilities already exist at all nodes of the network. [source]

A new distributed approximation algorithm for constructing minimum connected dominating set in wireless ad hoc networks

INTERNATIONAL JOURNAL OF COMMUNICATION SYSTEMS, Issue 8 2005
Bo Gao
Abstract In recent years, constructing a virtual backbone by nodes in a connected dominating set (CDS) has been proposed to improve the performance of ad hoc wireless networks. In general, a dominating set satisfies that every vertex in the graph is either in the set or adjacent to a vertex in the set. A CDS is a dominating set that also induces a connected sub-graph. However, finding the minimum connected dominating set (MCDS) is a well-known NP-hard problem in graph theory. Approximation algorithms for MCDS have been proposed in the literature. Most of these algorithms suffer from a poor approximation ratio, and from high time complexity and message complexity. In this paper, we present a new distributed approximation algorithm that constructs a MCDS for wireless ad hoc networks based on a maximal independent set (MIS). Our algorithm, which is fully localized, has a constant approximation ratio, and O(n) time and O(n) message complexity. In this algorithm, each node only requires the knowledge of its one-hop neighbours and there is only one shortest path connecting two dominators that are at most three hops away. We not only give theoretical performance analysis for our algorithm, but also conduct extensive simulation to compare our algorithm with other algorithms in the literature. Simulation results and theoretical analysis show that our algorithm has better efficiency and performance than others. Copyright © 2005 John Wiley & Sons, Ltd. [source]

Total domination in 2-connected graphs and in graphs with no induced 6-cycles

JOURNAL OF GRAPH THEORY, Issue 1 2009
Michael A. Henning
Abstract A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number ,t(G) of G. It is known [J Graph Theory 35 (2000), 21,45] that if G is a connected graph of order n,>,10 with minimum degree at least 2, then ,t(G),,,4n/7 and the (infinite family of) graphs of large order that achieve equality in this bound are characterized. In this article, we improve this upper bound of 4n/7 for 2-connected graphs, as well as for connected graphs with no induced 6-cycle. We prove that if G is a 2-connected graph of order n,>,18, then ,t(G),,,6n/11. Our proof is an interplay between graph theory and transversals in hypergraphs. We also prove that if G is a connected graph of order n,>,18 with minimum degree at least 2 and no induced 6-cycle, then ,t(G),,,6n/11. Both bounds are shown to be sharp. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 55,79, 2009 [source]

On k -domination and minimum degree in graphs

JOURNAL OF GRAPH THEORY, Issue 1 2008
Odile Favaron
Abstract A subset S of vertices of a graph G is k -dominating if every vertex not in S has at least k neighbors in S. The k -domination number is the minimum cardinality of a k -dominating set of G. Different upper bounds on are known in terms of the order n and the minimum degree of G. In this self-contained article, we present an Erdös-type result, from which some of these bounds follow. In particular, we improve the bound for , proved by Chen and Zhou in 1998. Furthermore, we characterize the extremal graphs in the inequality , if , of Cockayne et al. This characterization generalizes that of graphs realizing . © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 33,40, 2008 [source]

Some remarks on domination

JOURNAL OF GRAPH THEORY, Issue 3 2004
D. Archdeacon
Abstract We prove a conjecture of Favaron et al. that every graph of order n and minimum degree at least three has a total dominating set of size at least n/2. We also present several related results about: (1) extentions to graphs of minimum degree two, (2) examining graphs where the bound is tight, and (3) a type of bipartite domination and its relation to transversals in hypergraphs. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 207,210, 2004 [source]

Matchings in 3-vertex-critical graphs: The even case

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2005
Nawarat Ananchuen
Abstract A subset of vertices D of a graph G is a dominating set for G if every vertex of G not in D is adjacent to one in D. The cardinality of any smallest dominating set in G is denoted by ,(G)and called the domination number of G. Graph G is said to be ,-vertex-critical if ,(G , v) < ,(G), for every v vertex in G. Comparatively little is known to date about the structure of ,-vertex-critical graphs, even in the case when , = 3. In the present article, we begin the study of matchings in 3-vertex-critical graphs. In particular, we show that any 3-vertex-critical graph on an even number of vertices, which has no induced subgraph isomorphic to the bipartite graph K1,5 much have a perfect matching, whereas 3-vertex-critical even graphs in general need not contain such a matching. We close with a conjecture. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(4), 210,213 2005 [source]

Independent dominating sets and hamiltonian cycles

JOURNAL OF GRAPH THEORY, Issue 3 2007
Penny Haxell
Abstract A graph is uniquely hamiltonian if it contains exactly one hamiltonian cycle. In this note we prove that there are no r -regular uniquely hamiltonian graphs when r,>,22. This improves upon earlier results of Thomassen. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 233,244, 2007 [source]