On the maximal number of independent circuits in a graph
On the maximal number of independent circuits in a graph
复制标题
DOI：
10.1007/bf01895727
复制
发表时间：
1963-09
期刊：
影响因子：
--
通讯作者：
K. Corrádi;A. Hajnal
中科院分区：
文献类型：
--
作者：
K. Corrádi;A. Hajnal
该定理的特例 k= 1 是图论中众所周知且几乎微不足道的断言。 P. ERD6S 对此进行了推测。几年前，G. DIRAC 提出了以下稍弱的猜想（书面交流）。如果一个有 n~ 3k 个顶点的图是 2k 重连通的，那么它包含 k 个独立的电路。他们也已经知道我们结果的特殊情况 k= 2。 G. DIRAC 和 P. ERD6S 在他们的论文 [1] 中证明了以下定理。对于每个 k=~ l 和 c _-> 0，存在一个最小整数 n (k, c)，使得如果 n> n (k, c) 则 n 个顶点的每个图 ~ 的每个顶点的化合价 => 2k，除了可能的 c 顶点包含 k 个独立电路。尽管这个关于大 n 的定理比我们的定理更强，但它具有完全不同的特征，并且证明需要不同的论证。
The special case k= 1 of this theorem is a well-known and almost trivial assertion of graph theory. This generalization of it has been conjectured by P. ERD6S. A few years ago G. DIRAC stated the following slightly weaker conjecture (written communication).If a graph~, of n~ 3k vertices is 2k-fold connected then it contains k independent circuits. Tlie special case k= 2 of our result was already known to them too. In their paper [1] G. DIRAC and P. ERD6S prove the following theorem. To every k=~ l and to c _-> 0 there is a smallest integer n (k, c) such that if n> n (k, c) then every graph~ of n vertices every vertex of which has valency=> 2k except possible c vertices contains k independent circuits. Though this theorem for large n is stronger than ours, it is of quite different character and the proof needs different arguments.