Edge connectivity and vertex connectivity are two fundamental concepts in graph theory. Although by now there is a good understanding of the structure of graphs based on their edge connectivity, our knowledge in the case of vertex connectivity is much more limited. An essential tool in capturing edge connectivity are edge-disjoint spanning trees. The famous results of Tutte and Nash-Williams show that a graph with edge connectivity @math contains @math edge-disjoint spanning trees. We present connected dominating set (CDS) partition and packing as tools that are analogous to edge-disjoint spanning trees and that help us to better grasp the structure of graphs based on their vertex connectivity. The objective of the CDS partition problem is to partition the nodes of a graph into as many connected dominating sets as possible. The CDS packing problem is the corresponding fractional relaxation, where CDSs are allowed to overlap as long as this is compensated by assigning appropriate weights. CDS partition and CDS packing can be viewed as the counterparts of the well-studied edge-disjoint spanning trees, focusing on vertex disjointedness rather than edge disjointness. We constructively show that every @math -vertex-connected graph with @math nodes has a CDS packing of size @math and a CDS partition of size @math . We prove that the @math CDS packing bound is existentially optimal. Using CDS packing, we show that if vertices of a @math -vertex-connected graph are independently sampled with probability @math , then the graph induced by the sampled vertices has vertex connectivity @math . Moreover, using our @math CDS packing, we get a store-and-forward broadcast algorithm with optimal throughput in the networking model where in each round, each node can send one bounded-size message to all its neighbors.
All graphs considered in this paper are finite graphs without loops and multiple edges. The domatic number of a graph was defined by E. J. Cockayne and S. T. Hedetniemi [1]. Later some related concepts were introduced. The same authors together with R. M. Dawes [2] have introduced the total domatic number; R. Laskar and S. T. Hedetniemi [3] have introduced the connected domatic number. A dominating set (or a total dominating set) in an undirected graph G is a subset D of the vertex set V(G) of G with the property that to each vertex x e V(G) — D (or to each vertex xeV(G) respectively) there exists a vertex y e D adjacent to x. A connected dominating set of G is a dominating set of G with the property that the subgraph of G induced by it is connected. A domatic (or total domatic, or connected domatic) partition of G is a partition of V(G), all of whose classes are dominating (or total dominating, or connected dominating, respectively) sets of G. The maximum number of classes of a domatic (or total domatic, or connected domatic) partition of G is called the domatic (or total domatic, or connected domatic, respectively) number of G. The domatic number of G is denoted by d(G), its total domatic number by <4(G), its connected domatic number by dc(G). The connected domatic number of a graph is well defined only for connected graphs; in a disconnected graph there exists no connected dominating set and thus no connected domatic partition, while in every connected graph there exists at least one connected domatic partition, namely that which consists of one class. The connected domatic number of G is closely related to the vertex connectivity number of G. If G is a connected graph, then a vertex cut of G is a subset R of V(G) with the property that the subgraph of G induced by V(G) — R is disconnected. If G is not a complete graph, then the vertex connectivity number x(G) is the minimum cardinality of a vertex cut of G. If G is a complete graph (i. e. without vertex cuts) with n vertices, then we put x(G) = n — 1. Lemma. Let G be a connected graph which is not complete, let R be its vertex cut, let D be its connected dominating set. Then DnR^0. A dominating set in a graph G is a connected dominating set of G if it induces a connected subgraph of G. The connected domatic number of G is the maximum number of pairwise disjoint, connected dominating sets in V(G). We establish a sharp lower bound on the number of edges in a connected graph with a given order and given connected domatic number. We also show that a planar graph has connected domatic number at most 4 and give a characterization of planar graphs having connected domatic number 3. A set of vertices in a graph is a dominating set if every vertex outside the set has a neighbor in the set. The domatic number problem is that of partitioning the vertices of a graph into the maximum number of disjoint dominating sets. Let n denote the number of vertices, @math the minimum degree, and @math the maximum degree. We show that every graph has a domatic partition with @math dominating sets and, moreover, that such a domatic partition can be found in polynomial-time. This implies a @math -approximation algorithm for domatic number, since the domatic number is always at most @math . We also show this to be essentially best possible. Namely, extending the approximation hardness of set cover by combining multiprover protocols with zero-knowledge techniques, we show that for every @math , a @math -approximation implies that @math . This makes domatic number the first natural maximization problem (known to the authors) that is provably approximable to within polylogarithmic factors but no better. We also show that every graph has a domatic partition with @math dominating sets, where the "o(1)" term goes to zero as @math increases. This can be turned into an efficient algorithm that produces a domatic partition of @math sets. Wireless ad hoc and sensor networks (WSNs) often require a connected dominating set (CDS) as the underlying virtual backbone for efficient routing. Nodes in a CDS have extra computation and communication load for their role as dominator, subjecting them to an early exhaustion of their battery. A simple mechanism to address this problem is to switch from one CDS to another fresh CDS, rotating the active CDS through a disjoint set of CDSs. This gives rise to the connected domatic partition (CDP) problem, which essentially involves partitioning the nodes V(G) of a graph G into node disjoint CDSs. We have developed a distributed algorithm for constructing the CDP using our maximal independent set (MlS)-based proximity heuristics, which depends only on connectivity information and does not rely on geographic or geometric information. We show that the size of a CDP that is identified by our algorithm is at least [delta+1 beta(c+1)] - f, where delta is the minimum node degree of G, beta les 2, c les 11 is a constant for a unit disk graph (UDG), and the expected value of f is epsidelta|V|, where epsi Lt 1 is a positive constant, and delta ges 48. Results of varied testing of our algorithm are positive even for a network of a large number of sensor nodes. Our scheme also performs better than other related techniques such as the ID-based scheme. In a data processing system comprising a plurality of systems each including a plurality of console type typewriters for establishing communications pertaining to data processing operations between an operator and the system, the communication information which is entered into and derived from a central processing unit in each system by the console type typewriter is stored in a character buffer unit corresponding to the console type typewriter in a monitor transfer control unit, and a buffer scanning unit scans the character buffers to transfer the contents therein into a statistical analyzer or processing unit so that communication information may be automatically analyzed and summarized to obtain the data per day or month required for determining whether or not the data processing system has been effectively operated. Introduction (S.T. Hedetniemi, R.C. Laskar). Theoretical. Chessboard Domination Problems (E.J. Cockayne). On the Queen Domination Problem (C.M. Grinstead, B. Hahne, D. Van Stone). Recent Problems and Results About Kernels in Directed Graphs (C. Berge, P. Duchet). Critical Concepts in Domination (D.P. Summer). The Bondage Number of a Graph (J.F. ). Chordal Graphs and Upper Irredundance, Upper Domination and Independence (M.S. Jacobson and K. Peters). Regular Totally Domatically Full Graphs (B. Zelinka). Domatically Critical and Domatically Full Graphs (D. Rall). On Generalised Minimal Domination Parameters for Paths (B. Bollobas, E.J. Cockayne, C.M. Mynhardt). New Models. Dominating Cliques in Graphs (M.B. Cozzens, L.L. Kelleher). Covering all Cliques of Graph (Z. Tuza). Factor Domination in Graphs (R.C. Brigham, R. Dutton). The Least Point Covering and Domination Numbers of a Graph (E. Sampathkumar). Algorithmic. Dominating Sets in Perfect Graphs (D.G. Corneil, L.K. Stewart). Unit Disk Graphs (B.N. Clark, C.J. Colbourn, D.S. Johnson). Permutation Graphs: Connected Domination and Steiner Trees (C.J. Colbourn, L.K. Stewart). The Discipline Number of a Graph (V. Chvatal, W.J. Cook). Best Location of Service Centers in a Tree-Like Network under Budget Constraints (J. McHugh, Y. Perl). Dominating Cycles in Halin Graphs (M. Skowronska, M.M. Syslo). Finding Dominating Cliques Efficiently, in Strongly Chordal Graphs and Undirected Path Graphs (D. Kratsch). On Minimum Dominating Sets with Minimum Intersection (D.L. Grinstead, P.J. Slater). Bibliography. Bibliography on Domination in Graphs and Some Basic Definitions of Domination Parameters (S.T. Hedetniemi, R.C. Laskar).