共查询到19条相似文献,搜索用时 61 毫秒
1.
本文得到了无标号真严格(d)-连通无圈超图的计数公式,并得到了无标号真严格(d)-连通同胚k不可约无圈超图的计数公式. 相似文献
2.
3.
4.
5.
6.
图带宽和与其对偶超图带宽和的关系 总被引:1,自引:0,他引:1
设H=(E1,E2,…,Em)是集合X上的一个超图,一个1-1映射f:X→{1,2,…,|X|}称为H的一个标号,对H的任一标号f,BS(H,f)=∑(E∈H)max{|f(u)-f(v)|;u,v∈E}称为超图H的关于标号f的带宽和BS(H)=min{BS(H,f)|f是超图H的标号|}称为H的带宽和.论文研究图带宽和与其对偶超图的带宽和这两个参数间的关系. 相似文献
7.
1982年,毛经中对(k 1) p阶和q边的匀称超树的个数T_(k 1)(p,q)提出如下猜想:其余 易见,当k(?)1时,T(p, q) (q-1)~(?) p~p(?),故(*)成立将是标号树计数的Cayley公式在超图理论中的推广。 本书证明了上述猜想并得到一般超图的计数式。 定义 如果超图H (X,ε)是连通的且不含圈,则称H为一超树,若(?)E_i∈ε,|E_i|=M,则称H是匀称M秩超树。 相似文献
8.
9.
10.
11.
12.
Shonda Gosselin 《Discrete Mathematics》2010,310(8):1366-1372
13.
Peter Keevash 《Random Structures and Algorithms》2011,39(3):275-376
We obtain a hypergraph generalisation of the graph blow‐up lemma proved by Komlós, Sarközy and Szemerédi, showing that hypergraphs with sufficient regularity and no atypical vertices behave as if they were complete for the purpose of embedding bounded degree hypergraphs. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 39, 275–376, 2011 相似文献
14.
15.
Alon Noga; Bollobas Bela; Kim Jeong Han; Vu Van H. 《Proceedings London Mathematical Society》2003,86(2):273-301
A cover of a hypergraph is a collection of edges whose unioncontains all vertices. Let H = (V, E) be a k-uniform, D-regularhypergraph on n vertices, in which no two vertices are containedin more than o(D/e2k log D) edges as D tends to infinity. Ourresults include the fact that if k = o(log D), then there isa cover of (1 + o(1))n/k edges, extending the known result thatthis holds for fixed k. On the other hand, if k 4 log D thenthere are k-uniform, D-regular hypergraphs on n vertices inwhich no two vertices are contained in more than one edge, andyet the smallest cover has at least (nk) log (k log D)) edges.Several extensions and variants are also obtained, as well asthe following geometric application. The minimum number of linesrequired to separate n random points in the unit square is,almost surely, (n2/3 / (log n)1/3). 2000 Mathematical SubjectClassification: 05C65, 05D15, 60D05. 相似文献
16.
17.
The well‐known Friendship Theorem states that if G is a graph in which every pair of vertices has exactly one common neighbor, then G has a single vertex joined to all others (a “universal friend”). V. Sós defined an analogous friendship property for 3‐uniform hypergraphs, and gave a construction satisfying the friendship property that has a universal friend. We present new 3‐uniform hypergraphs on 8, 16, and 32 vertices that satisfy the friendship property without containing a universal friend. We also prove that if n ≤ 10 and n ≠ 8, then there are no friendship hypergraphs on n vertices without a universal friend. These results were obtained by computer search using integer programming. © 2008 Wiley Periodicals, Inc. J Combin Designs 16: 253–261, 2008 相似文献
18.
Csilla Bujtás 《Discrete Mathematics》2009,309(22):6391-6401
A color-bounded hypergraph is a hypergraph (set system) with vertex set X and edge set E={E1,…,Em}, together with integers si and ti (1≤si≤ti≤|Ei|) for i=1,…,m. A vertex coloring φ is feasible if the number of colors occurring in edge Ei satisfies si≤|φ(Ei)|≤ti, for every i≤m.In this paper we point out that hypertrees-hypergraphs admitting a representation over a (graph) tree where each hyperedge Ei induces a subtree of the underlying tree-play a central role concerning the set of possible numbers of colors that can occur in feasible colorings. We also consider interval hypergraphs and circular hypergraphs, where the underlying graph is a path or a cycle, respectively. Sufficient conditions are given for a ‘gap-free’ chromatic spectrum; i.e., when each number of colors is feasible between minimum and maximum. The algorithmic complexity of colorability is studied, too.Compared with the ‘mixed hypergraphs’-where ‘D-edge’ means (si,ti)=(2,|Ei|), while ‘C-edge’ assumes (si,ti)=(1,|Ei|−1)-the differences are rather significant. 相似文献
19.
We consider vertex colorings of hypergraphs in which lower and upper bounds are prescribed for the largest cardinality of a monochromatic subset and/or of a polychromatic subset in each edge. One of the results states that for any integers s≥2 and a≥2 there exists an integer f(s,a) with the following property. If an interval hypergraph admits some coloring such that in each edge Ei at least a prescribed number si≤s of colors occur and also each Ei contains a monochromatic subset with a prescribed number ai≤a of vertices, then a coloring with these properties exists with at most f(s,a) colors. Further results deal with estimates on the minimum and maximum possible numbers of colors and the time complexity of determining those numbers or testing colorability, for various combinations of the four color bounds prescribed. Many interesting problems remain open. 相似文献