摘要
设G是一个连通图,最大度和最小度分别为△(G)和δ(G).图G的非正则指标t(G)是指G的度序列中不同值的个数.如果t(G)=△(G)一δ(G)+1,则称图G为极大非正则图.本文给出了极大非正则图和不含三角的极大非正则图边数的上界,同时给出极大非正则图边数的一个紧的下界.
Let G be a connected graph with maximum degree △(G) and minimum degreeδ (G). The irregularity index t(G) of G is defined as the number of distinct terms in the degree sequence of G. We say that G is maximally irregular if t(G) =△(G) - δ(G) + 1. The purpose of this note is to establish upper bound on the size of maximally irregular graphs and triangle-free graphs and give a tight lower bound on the size of maximally irregular graphs.
出处
《数学进展》
CSCD
北大核心
2016年第5期721-726,共6页
Advances in Mathematics(China)
基金
supported by NSFC(No.11171283,No.11326219)
XJEDU(No.2013S03)
the Fund of Xinjiang University(No.XY110104,No.BS120103)
关键词
非正则指标
极大非正则图
不含三角的图
irregularity index
maximally irregular graphs
triangle-free graphs