摘要
本文将极大图和次极大图的构造和判定算法,从平图推广到一般图.证明了所有的G-极大图可由K_1通过若干个图运算构造得到,所有的G-次极大图可由C_1,K_4通过若干个图运算构造得到.给出了判定一个图是否为G-极大图或G-次极大图的算法.
In this paper, the constructions and the judgement algorithms of extremal and near-extremal graphs are extended from plane graphs to general graphs. WTe prove that all G- extremal graphs （resp. G-nea〉extremal graphs） can be constructed from K1 by several graph operations （resp. C1 and K4 by several graph operations）. The algorithms are also given to judge whether a graph is a G-extremal graph or not and whether a graph is a G-near-extremal graph or not, respectively.
出处
《数学进展》
CSCD
北大核心
2013年第6期817-822,共6页
Advances in Mathematics（China）
基金
国家自然科学基金资助项目(No.10831001)
福建省教育厅A类科技项目(No.JA11332)
关键词
G-极大图
G-次极大图
构造
算法
G-extremai graph
G-near-extremal graph
construction
algorithm
