On size, radius and minimum degree

Graph Theory Let G be a finite connected graph. We give an asymptotically tight upper bound on the size of G in terms of order, radius and minimum degree. Our result is a strengthening of an old classical theorem of Vizing (1967) if minimum degree is prescribed.

Saved in:
Bibliographic Details
Published in:Discrete mathematics and theoretical computer science 2014-01, Vol.16 no. 1 (Graph Theory), p.1-5
Main Author: Mukwembi, Simon
Format: Article
Language:English
Subjects:
[info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
Combinatorics
Computer Science
Discrete Mathematics
graph theory
Graphs
Theorems
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Graph Theory Let G be a finite connected graph. We give an asymptotically tight upper bound on the size of G in terms of order, radius and minimum degree. Our result is a strengthening of an old classical theorem of Vizing (1967) if minimum degree is prescribed.
ISSN:1365-8050
1462-7264
1365-8050
DOI:10.46298/dmtcs.1265