首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到10条相似文献,搜索用时 78 毫秒
1.
Dense trees are undirected graphs defined as natural extensions of trees. They are already known in the realm of graph coloring under the name of k-degenerate graphs. For a given integer k1, a k-dense cycle is a connected graph, where the degree of each vertex is greater than k. A k-dense forest F=(V,E) is a graph without k-dense cycles as subgraphs. If F is connected, then is a k-dense tree. 1-dense trees are standard trees. We have |E|k|V|−k(k+1)/2. If equality holds F is connected and is called a maximal k-dense tree. k-trees (a subfamily of triangulated graphs) are special cases of maximal k-dense trees.We review the basic theory of dense trees in the family of graphs and show their relation with k-trees. Vertex and edge connectivity is thoroughly investigated, and the role of maximal k-dense trees as “reinforced” spanning trees of arbitrary graphs is presented. Then it is shown how a k-dense forest or tree can be decomposed into a set of standard spanning trees connected through a common “root” of k vertices. All sections include efficient construction algorithms. Applications of k-dense trees in the fields of distributed systems and data structures are finally indicated.  相似文献   

2.
The concepts of k-systems, k-networks and k-covers were defined by A. Arhangel’skii in 1964, P. O’Meara in 1971 and R. McCoy, I. Ntantu in 1985, respectively. In this paper the relationships among k-systems, k-networks and k-covers are further discussed and are established by mk-systems. As applications, some new characterizations of quotients or closed images of locally compact metric spaces are given by means of mk-systems.  相似文献   

3.
Let k be a positive integer, and let G be a simple graph with vertex set V (G). A k-dominating set of the graph G is a subset D of V (G) such that every vertex of V (G)-D is adjacent to at least k vertices in D. A k-domatic partition of G is a partition of V (G) into k-dominating sets. The maximum number of dominating sets in a k-domatic partition of G is called the k-domatic number d k (G). In this paper, we present upper and lower bounds for the k-domatic number, and we establish Nordhaus-Gaddum-type results. Some of our results extend those for the classical domatic number d(G) = d 1(G).   相似文献   

4.
In this note we study the relation between k R -spaces and k-spaces and prove that a k R -space with a σ-hereditarily closure-preserving k-network consisting of compact subsets is a k-space, and that a k R -space with a point-countable k-network consisting of compact subsets need not be a k-space. This work was supported by the NSF of China (10271056).  相似文献   

5.
The following results are proved. In Theorem 1, it is stated that there exist both finitely presented and not finitely presented 2-generated nonfree groups which are k-free-like for any k ⩾ 2. In Theorem 2, it is claimed that every nonvirtually cyclic (resp., noncyclic and torsion-free) hyperbolic m-generated group is k-free-like for every k ⩾ m + 1 (resp., k ⩾ m). Finally, Theorem 3 asserts that there exists a 2-generated periodic group G which is k-free-like for every k ⩾ 3. Supported by NSF (grant Nos. DMS 0455881 and DMS-0700811). (A. Yu. Olshanskii, M. V. Sapir) Supported by RFBR project No. 08-01-00573. (A. Yu. Olshanskii) Supported by BSF grant (USA–Israel). (M. V. Sapir) Translated from Algebra i Logika, Vol. 48, No. 2, pp. 245–257, March–April, 2009.  相似文献   

6.
Sang-Eon Han 《Acta Appl Math》2008,104(2):177-190
In order to study digital topological properties of a k-surface in Z n , we generalize the topological number in Bertrand (Pattern Recogn. Lett. 15:1003–1011, 1994). Furthermore, we show that a local (k 0,k 1)-isomorphism preserves some digital-topological properties, such as a generalized topological number and a simple k 0-point, and prove that a local (k 0,k 1)-isomorphism takes a simple k 0-surface in into a simple k 1-surface in .   相似文献   

7.
A multiparameter negative binomial distribution of order k is obtained by compounding the extended (or multiparameter) Poisson distribution of order k by the gamma distribution. A multiparameter logarithmic series distribution of order k is derived next, as the zero truncated limit of the first distribution. Finally a few genesis schemes and interrelationships are established for these three multiparameter distributions of order k. The present work extends several properties of distributions of order k.  相似文献   

8.
We prove that a bounded open set U in has k-width less than C(n) Volume(U) k/n . Using this estimate, we give lower bounds for the k-dilation of degree 1 maps between certain domains in . In particular, we estimate the smallest (n – 1)-dilation of any degree 1 map between two n-dimensional rectangles. For any pair of rectangles, our estimate is accurate up to a dimensional constant C(n). We give examples in which the (n – 1)-dilation of the linear map is bigger than the optimal value by an arbitrarily large factor. Received: January 2006, Revision: May 2006, Accepted: June 2006  相似文献   

9.
It is shown in [4] that if a normal matrix,A satisfies some conditions then |C,1| k summability implies |A| k summability wherek≥1. In the present paper, we consider the converse implication.  相似文献   

10.
Thek-Centrum Shortest Path Problem (kCSP[s, t]) is to minimize the sum of thek longest arcs in any (simple)s−t path containing at leastk arcs, wherek is a positive integer.kCSP is introduced and is shown to be NP-Hard, although it is polynomially solvable ifk is constrained to be no greater than the number of arcs in ans−t path with fewest arcs. Some properties of the problem are studied and a new weakly dual problem is also introduced.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号