Connected domatic number of a graph
Connected domatic number of a graph
复制标题
图的连通域数
作者：
B. Zelinka
本文所考虑的图都是无环多边的有限图。图的定义数是由E.J.Cockayne和S.T.Hedeniemi[1]定义的。后来又引入了一些相关概念。同样的作者和R.M.Dawes[2]引入了全域数，R.Laskar和S.T.Hederniemi[3]引入了连通域数。无向图G的控制集(或全控制集)是G的顶点集V(G)的子集D，其性质是对每个顶点x e V(G)-D(或每个顶点xev(G))都存在一个与x相邻的顶点y e D.G的连通控制集是G的一个控制集，其性质是G的子图是连通的.G的定域(或全定域，或连通定域)划分是V(G)的划分，其所有类分别是G的支配(或全定域，或连通支配)集。G的定域(或全定域，或连通定域)划分的最大类数称为G的定域(或全定域，或连通定域)数。G的定域数由d(G)表示，其总定域数由-lt；4(G)表示，其连通定域数由DC(G)表示。图的连通论域数仅对连通图有很好的定义，在不连通图中不存在连通支配集，因此不存在连通论域划分，而在每个连通图中至少存在一个连通论域划分，即由一类组成的连通论域划分。G的连通连通数与G的顶点连通数密切相关。如果G是连通图，则G的一个顶点割是V(G)的子集R，其性质是由V(G)-R诱导的G的子图是不连通的。如果G不是完全图，则点连通数x(G)是G的一个顶点割的最小基数。如果G是一个有n个顶点的完全图(即没有顶点割)，则我们设x(G)=n-1引理。设G是一个不完全的连通图，R是它的顶点割，D是它的连通支配集。然后是DNR^0。
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.