摘要
图G的一个顶点称为割点是指删去该顶点,图的分支数增加,而图G的一个末块是指仅包含G的一个割点的块.对无爪且不含4-团的4-正则图,给出了它的末块数与割点数的上界且刻划了达到这些上界的极值图.
A cut-vertex in a graph G is a vertex whose removal increases the number of connected components of the graph. An end-block of G is a block that contains exactly one cut-vertex of G. In this paper we establish upper bounds on the numbers of end-blocks and cut-vertices for claw-free and 4-clique-free 4-regular graphs, and we characterize the extremal graphs achieving the bounds.
出处
《数学的实践与认识》
CSCD
北大核心
2013年第10期145-149,共5页
Mathematics in Practice and Theory
基金
重庆市科委自然科学基金(cstc2011jjA00020)
重庆师范大学青年基金(2011XLQ29)
关键词
无爪图
割点
末块
4-正则图
claw-free graph
cut-vertices
end-blocks
4-regular graph