设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.