A note on diameter and the degree sequence of a graph

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 Erdős, Pach, Pollack and Tuza [P. Erdős, J. Pach, R. P...

Full description

Saved in:
Bibliographic Details
Published in:Applied mathematics letters 2012-02, Vol.25 (2), p.175-178
Main Author: Mukwembi, Simon
Format: Article
Language:English
Subjects:
Combinatorics
Combinatorics. Ordered structures
Degree sequence
Deltas
Diameter
Exact sciences and technology
Graph theory
Graphs
Mathematical analysis
Mathematics
Minimum degree
Numerical analysis
Numerical analysis. Scientific computation
Pollack
Sciences and techniques of general use
Strengthening
Trees
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 Erdős, Pach, Pollack and Tuza [P. Erdős, 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 δ , then its diameter does not exceed 3 ( n − t ) δ + 1 + O ( 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.
ISSN:0893-9659
1873-5452
DOI:10.1016/j.aml.2011.08.010