On diameter and inverse degree of a graph

The inverse degree r ( G ) of a finite graph G = ( V , E ) is defined as r ( G ) = ∑ v ∈ V 1 deg v , where deg v is the degree of vertex v . We establish inequalities concerning the sum of the diameter and the inverse degree of a graph which for the most part are tight. We also find upper bounds on...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2010-02, Vol.310 (4), p.940-946
Main Author: Mukwembi, Simon
Format: Article
Language:English
Subjects:
Algebra
Applied sciences
Chemical graph
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Diameter
Exact sciences and technology
Information retrieval. Graph
Inverse degree
Mathematics
Sciences and techniques of general use
Theoretical computing
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:The inverse degree r ( G ) of a finite graph G = ( V , E ) is defined as r ( G ) = ∑ v ∈ V 1 deg v , where deg v is the degree of vertex v . We establish inequalities concerning the sum of the diameter and the inverse degree of a graph which for the most part are tight. We also find upper bounds on the diameter of a graph in terms of its inverse degree for several important classes of graphs. For these classes, our results improve bounds by Erdős et al. (1988) [5], and by Dankelmann et al. (2008) [4].
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2009.09.014