期刊文献+

极大非正则图的边数(英文)

The Size of Maximally Irregular Graphs
原文传递
导出
摘要 设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
  • 相关文献

参考文献6

  • 1Bondy, J.A. and Murty, U.S.R., Graph Theory, New York: Springer-Verlag, 2008.
  • 2Liu, F.X., Zhang, Z. and Meng, J.X., The size of maximally irregular graphs and maximally irregular triangle- free graphs, Graphs Cornbin., 2013, 30(3): 699-705.
  • 3Majcher, Z. and Michael, J., Degree sequence of highly irregular graphs, Discrete Math., 1997, 164(1/2/3): 225-236.
  • 4Majcher, Z. and Michael, J., Highly irregular graphs with extreme numbers of edges, Discrete Math., 1997, 164(1/2/3): 237-242.
  • 5Mukwembi, S., A note on diameter and degree sequence of a graph, Appl. Math. Lett., 2012, 25(3): 175-178.
  • 6Mukwembi, S., On maximally irregular graphs, Bull. Malays. Math. Sci. Soc. (2), 2013, 36(3): 717-721.

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部