On complete subgraphs of different orders
On complete subgraphs of different orders
复制标题
DOI：
10.1017/s0305004100052063
复制
发表时间：
1976-01
影响因子：
0.8
通讯作者：
B. Bollobás
中科院分区：
文献类型：
--
作者：
B. Bollobás
设S是一个集合，{X1，...，Xn} =是S的一个相异子集族.有顶点集{X1，...，Xn}且XiXj（i <$j）是Ω（）的一条边的交图Ω（）当且仅当Xi <$Xi <$Xi <$<$（c.f.（六））。很容易看出，（7），每一个图是一个交叉图，换句话说，每一个图可以表示为子集的一个集合。Erdös，Goodman和Pósa（5）证明了：如果一个图有n ≥ 4个顶点，那么可以找到一个至多含有[n ~ 2/4]个元素的表示集。这个断言是结果（5）的直接结果，即具有n ≥ 1个顶点的图的边可以被至多[n 2/4]个边不相交的三角形和边覆盖。我们称一个图G被子图G1，…，Gk覆盖，如果G的每条边至少在一个Gi中。本文的目的之一是证明Erdös（4）提出的这个结果的一个推广。
Let S be a set and let {X1, …, Xn} = be a family of distinct subsets of S. The intersection graph Ω() of has vertex set {X1, …, Xn} and XiXj (i ≠ j) is an edge of Ω() if and only if Xi ∩ Xi ≠ Ø (c.f. (6)). It is easily seen, (7), that every graph is an intersection graph, in other words every graph can be represented by subsets ofa set. Moreover, it was proved by Erdös, Goodman and Pósa (5) that if a graph has n ≥ 4 vertices then one can find a representing set with at most [n2/4] elements. This assertion is an immediate consequence of the result, (5), that the edges of a graph with n ≥ 1 vertices can be covered with at most [n2/4] edge disjoint triangles and edges. We say that a graph G is covered with the subgraphs G1, …, Gk, if every edge of G is in at least one Gi. One of the aims of this note is to prove an extension of this result, pro-posed by Erdös (4).