苏健基. 临界2棱连通图的最大度及度大于4的顶点数的上界[J]. Journal of Xinjiang University (Natural Science Edition in Chinese and English), 1985, (1).DOI:
临界2棱连通图的最大度及度大于4的顶点数的上界
摘要
1、前言对一些特殊图类的最小度
人们已经有了较多的认识
然而对于图的最大度及其它度的顶点的性质所知还不多。对临界2棱连通图
当其2度顶点数给定时
我们给出最大度的上界(定理1)及度大于4的各类顶点数的上界(定理2、3)
并且这些上界都是最好可能的。我们讨论的都是有限阶的简单图
不另加说明的术语和记号与Bolloás同。
Abstract
Let G be a critically 2-line-connected graph and D be the set of vertices with degree two in the graph G. A(G) denotes the maximum degree of G and D≧2k-s(G)={x:(x∈G)(?)(d(x)≥2k-1)}
D2k-1:2k(G)={x:(x∈G)(?)(2k-1≤d(x)≤2k)}
where k is a natural number. The symbol [a] denotes the greatest integer not greater than a. In this paper we prove the following theorems: Theorem 1. Let |D|=α then △ (G)≤2[α/2]; Theorem 2. Let |D|=α and α≥2k≥6
then |D≧2k-1(G)|≤2k[(α-4)/(2k-4)]+2[(α-4-(2k-4)[(α-4)/(2k-4)])/2]; Theorem 3. Let |D|=α and α≥2k≥6
then |D2k-112k(G)|≤2k[(α-4)/(2k-4)]+2[(α-4-(2k-4)[(α-4)/(2k-4)])/2]. And in three theorems above the upper bounds are the best possible.