On the maximal number of independent circuits in a graph
On the maximal number of independent circuits in a graph
复制标题
DOI：
10.1007/bf01901931
复制
发表时间：
1963-03
期刊：
影响因子：
--
通讯作者：
G. Dirac;P. Erdös
中科院分区：
文献类型：
--
作者：
G. Dirac;P. Erdös
在最近的一篇论文[l] k . CORRÁDI和a . HAJNAL中证明了如果一个没有多条边的有限图包含至少3k个顶点，并且每个顶点的价至少为2k，其中k是一个正整数，则该图包含k个独立的电路，即该图包含k个电路的子图，其中没有两个有共同顶点。本文包含了这个定理的推广。在最近的一篇论文[2]P. ERDŐS和L. PÓSA中，除其他外，证明了如果一个有或没有环路和多条边的有限图包含n个顶点和至少n+ 4条边，则该图包含两个没有共同边的电路。本文包含了平面图的类似结果。我们采用以下符号：O k表示由k个独立电路组成的图，k O表示由k个或更多电路组成的图，其中没有两个电路有共同的边。如果q是一个图，则‘V (q)表示q的顶点集合，Vi (q)表示q的顶点集合为i inq （i为非负整数），t5i (q), Ty i (q)分别表示4的顶点集合为-i和’i, & (q)表示c~的边集合。图中顶点x的价用v （x, C~）表示。我吗?I用V (q)表示，J (q)用E (q)表示，等等。在这种符号中，上面引用的CORRÁDI和HAJNAL定理表明，如果q是一个没有多条边的有限图，并且如果V (q) 3k和T----2k_ 1(4)= 0，则q Ok；上面引用的ERDÖS和PÓSA定理表明，它是一个有限图，E (C) _-V (q)+ 4，则q D 2O。
In a recent paper [l] K. CORRÁDI and A. HAJNAL proved that if a finite graph without multiple edges contains at least 3k vertices and the valency of every vertex is at least 2k, where k is a positive integer, then the graph contains k independent circuits, ie the graph contains as a subgraph a set of k circuits no two of which have a vertex in common. The present paper contains extensions of this theorem. In a recent paper [2] P. ERDŐS and L. PÓSA proved, among other things, that if a finite graph with or without loops and multiple edges contains n vertices and at least n+ 4 edges, then the graph contains two circuits without an edge in common. The present paper contains analogous results for planar graphs. We adopt the following notation: O k denotes a graph consisting ofk independent circuits, k O denotes a graph consisting of k or more circuits no two of which have an edge in common. If q is a graph then'V (q) denotes the set of vertices of q,Vi (q) denotes the set of vertices ofqhaving valency i inq (i being a non-negative integer), T 5i (q), Ty i (q) denote the set of vertices of4having valency-i and'i, respectively, and & (q) denotes the set of edges of c~. The valency of the vertex x in the graph will be denoted by v (x, C~). I?(() I will be denoted by V (q), J & (q) I by E (q) etc. In this notation the theorem Of CORRÁDI and HAJNAL quoted above states that ifqis a finite graph without multiple edges and if V (q) 3k and T----2k_ 1 (4)= 0, thenq Ok; and the theorem of ERDÖS and PÓSA quoted above states that if is a finite graph and E (C) _-V (q)+ 4, thenq D 2O.