共查询到19条相似文献，搜索用时 46 毫秒
1.
假设c是一个小于1/1152的常数,证明：对于每个充分大的偶数n,如果一个具有n个顶点的3一致完全超图的边着色满足每种颜色出现的次数不超过[cn],那么必含有一个每条边颜色都不一样的彩色哈密顿圈。 相似文献
2.
苗正科 《数学物理学报(A辑)》2004,24(3):381-384
设H是一个超图, 用H+*和L(H)分别表示H的对偶超图和线图. 定义H的邻接图是由L(H+*)和H的所有环组成的图, 记作G-H. 若G-H是本原的, 则称H是本原的, 并称γ(G-H)为H的指数. 该文得到了所有n阶本原简单超图以及所有秩不小于3的n阶本原简单超图的指数集, 并分别刻划了其极超图. 相似文献
3.
几类图的匹配等价图类 总被引：1，自引：0，他引：1
魏岭 《数学的实践与认识》2011,41(17)
两个图G和H的匹配多项式相等,则称它们匹配等价.用[G]表示图G的所有不同构的匹配等价图的集合.刻画了匹配次大根小于1的图及这些图的补图的匹配等价图类. 相似文献
4.
5.
7.
8.
本文证明了下面的定理：若超图Ｈ＝（Ｘ；Ｅ１，Ｅ２，．．．Ｅｍ）中存在浓度为Ｋ长为ｍ的圈，则有ｍ∑ｉ＝１（│Ｅｉ│－ｋ）＞ｎ－ｋ。 相似文献
9.
一类Caterpillars图的匹配刻画 总被引：1，自引：0，他引：1
申世昌 《纯粹数学与应用数学》2010,26(4):541-545
利用匹配多项式的性质以及匹配根的信息研究了图的匹配刻画问题,给出了一类Caterpillars图F（2,m,3）及补图匹配刻画的充分必要条件是m=2,5,8. 相似文献
10.
11.
Two n‐vertex hypergraphs G and H pack, if there is a bijection such that for every edge , the set is not an edge in H. Extending a theorem by Bollobás and Eldridge on graph packing to hypergraphs, we show that if and n‐vertex hypergraphs G and H with with no edges of size 0, 1, and n do not pack, then either
- one of G and H contains a spanning graph‐star, and each vertex of the other is contained in a graph edge, or
- one of G and H has edges of size not containing a given vertex, and for every vertex x of the other hypergraph some edge of size does not contain x.
12.
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. 相似文献
13.
The survey is devoted to line graphs and a new multivalued function
called the line hypergraph. This function generalizes two classical concepts at once, namely the line graph and the dual hypergraph. In a certain sense, line graphs and dual hypergraphs are extreme values of the function
. There are many publications about line graphs, but our considerations are restricted to papers concerning Krausz global characterization of line graphs or Whitneys theorem on edge isomorphisms. The survey covers almost all known results on the function
because they are concentrated around Krausz and Whitneys theorems. These results provide evidence that the notion of the line hypergraph is quite natural. It enables one to unify the classical theorems on line graphs and to obtain their more general versions in a simpler way. 相似文献
14.
15.
Yufei Zhao 《Random Structures and Algorithms》2015,47(2):205-226
A sequence of k‐uniform hypergraphs is convergent if the sequence of homomorphism densities converges for every k‐uniform hypergraph F. For graphs, Lovász and Szegedy showed that every convergent sequence has a limit in the form of a symmetric measurable function . For hypergraphs, analogous limits were constructed by Elek and Szegedy using ultraproducts. These limits had also been studied earlier by Hoover, Aldous, and Kallenberg in the setting of exchangeable random arrays. In this paper, we give a new proof and construction of hypergraph limits. Our approach is inspired by the original approach of Lovász and Szegedy, with the key ingredient being a weak Frieze‐Kannan type regularity lemma. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 205–226, 2015 相似文献
16.
Let S1 and S2 be two (k-1)-subsets in a k-uniform hypergraph H. We call S1 and S2 strongly or middle or weakly independent if H does not contain an edge e ∈ E(H) such that S1 ∩ e ≠∅ and S2 ∩ e ≠∅ or e ⊆ S1 ∪ S2 or e ⊇ S1 ∪ S2, respectively. In this paper, we obtain the following results concerning these three independence. (1) For any n ≥ 2k2-k and k ≥ 3, there exists an n-vertex k-uniform hypergraph, which has degree sum of any two strongly independent (k-1)-sets equal to 2n-4(k-1), contains no perfect matching; (2) Let d ≥ 1 be an integer and H be a k-uniform hypergraph of order n ≥ kd+(k-2)k. If the degree sum of any two middle independent (k-1)-subsets is larger than 2(d-1), then H contains a d-matching; (3) For all k ≥ 3 and sufficiently large n divisible by k, we completely determine the minimum degree sum of two weakly independent (k-1)-subsets that ensures a perfect matching in a k-uniform hypergraph H of order n. 相似文献
17.
18.
We give a simple proof of the result of Grable on the asymptotics of the number of partial Steiner systems S(t,k,m). © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 347–352, 2000 相似文献
19.
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 相似文献