A note on diameter and the degree sequence of a graph

作者：Mukwembi Simon^*

来源：Applied Mathematics Letters, 2012, 25(2): 175-178.

DOI：10.1016/j.aml.2011.08.010

• Diameter
• Minimum degree
• Degree sequence

In this note, we use a technique introduced by Dankelmann and Entringer [P. Dankelmann, R.C. Entringer, Average distance, minimum degree and spanning trees, J. Graph Theory 33 (2000) 1-13] to obtain a strengthening of an old classical theorem by Erdos, Pach, Pollack and Tuza [P. Erdos, J. Pach, R. Pollack, Z. Tuza, Radius, diameter, and minimum degree, J. Combin. Theory B 47 (1989) 73-79] on diameter and minimum degree. To be precise, we will prove that if G is a connected graph of order n and minimum degree S, then its diameter does not exceed 3(n - t)/delta + 1 + 0(1), where t is the number of distinct terms of the degree sequence of G. The featured parameter, t, is attractive in nature and promising; more discoveries on it in relation to other graph parameters are envisaged.

• 出版日期2012-2