Critically $n$-connected graphs-猫眼课题宝

DOI：

10.1090/s0002-9939-1972-0290999-1

发表时间：

1972

期刊：

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

G. Chartrand;A. Kaugars;D. R. Lick

证明了以下结果。每个n-连通图都包含一个顶点，它的去掉可以得到一个也是n-连通的图，或者包含一个度小于(3n 1)/2的顶点。图G称为n连通的，如果从图G中去掉少于n个的顶点既没有断开它的连通，也没有把它归结为由单个顶点组成的平凡图。图G是n连通的n的最大值称为它的连通度，记为K(G)。G的最小次数由5(G)表示；K(G)和lt；6(G)是众所周知的。图G称为临界n连通的，如果对G的每个顶点v，K(G)=n且K(G-v)=n-i。类似地，如果K(G)=n且对G的每条边e，K(G-e)=n1，则图G是极小n连通的。本文的目的是给出一个图是临界n连通的一个必要条件，并讨论相关的问题。由于1-连通图是非平凡连通图，并且由于每个非平凡连通图G至少有两个顶点u和v，因此

The following result is proved. Every n-connected graph contains either a vertex whose removal results in a graph which is also n-connected or a vertex of degree less than (3n 1)/2. Introduction. A graph G is said to be n-connected if the removal of fewer than n vertices from G neither disconnects it nor reduces it to the trivial graph consisting of a single vertex. The maximum value of n for which a graph G is n-connected is called its connectivity and is denoted by K(G). The minimum degree of G is designated by 5(G); the inequality K(G)<6(G) is well known. A graph G is said to be critically n-connected if K(G)=n and K(G-v)= n-I for each vertex v of G. Analogously, a graph G is minimally nconnected if K(G)=n and for each edge e of G, K(G-e)=n1. The object of this article is to present a necessary condition for a graph to be critically n-connected and to discuss related topics. Since 1-connected graphs are the nontrivial connected graphs and since every nontrivial connected graph G has at least two vertices u and v such

Critically $n$-connected graphs

文献摘要

被引文献

相似文献