Minimum size of a graph or digraph of given radius

Peter Dankelmann; Lutz Volkmann

doi:10.1016/j.ipl.2009.06.001

Minimum size of a graph or digraph of given radius

Peter Dankelmann
, Lutz Volkmann

Research output: Contribution to journal › Article › peer-review

8 Citations (Scopus)

Abstract

In this paper we show that a connected graph of order n, radius r and minimum degree δ has at least frac(1, 2) (δ n + frac((n - 1) (δ - 2), (δ - 1)^r - 1)) edges, for n large enough, and this bound is sharp. We also present a similar result for digraphs.

Original language	English
Pages (from-to)	971-973
Number of pages	3
Journal	Information Processing Letters
Volume	109
Issue number	16
DOIs	https://doi.org/10.1016/j.ipl.2009.06.001
Publication status	Published - 31 Jul 2009
Externally published	Yes

Keywords

Digraph
Graph
Interconnection networks
Minimum degree
Radius
Size

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/j.ipl.2009.06.001

Cite this

@article{4cffaaf2a17d47c3a74c41743177dc8b,

title = "Minimum size of a graph or digraph of given radius",

abstract = "In this paper we show that a connected graph of order n, radius r and minimum degree δ has at least frac(1, 2) (δ n + frac((n - 1) (δ - 2), (δ - 1)r - 1)) edges, for n large enough, and this bound is sharp. We also present a similar result for digraphs.",

keywords = "Digraph, Graph, Interconnection networks, Minimum degree, Radius, Size",

author = "Peter Dankelmann and Lutz Volkmann",

year = "2009",

month = jul,

day = "31",

doi = "10.1016/j.ipl.2009.06.001",

language = "English",

volume = "109",

pages = "971--973",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "16",

}

TY - JOUR

T1 - Minimum size of a graph or digraph of given radius

AU - Dankelmann, Peter

AU - Volkmann, Lutz

PY - 2009/7/31

Y1 - 2009/7/31

N2 - In this paper we show that a connected graph of order n, radius r and minimum degree δ has at least frac(1, 2) (δ n + frac((n - 1) (δ - 2), (δ - 1)r - 1)) edges, for n large enough, and this bound is sharp. We also present a similar result for digraphs.

AB - In this paper we show that a connected graph of order n, radius r and minimum degree δ has at least frac(1, 2) (δ n + frac((n - 1) (δ - 2), (δ - 1)r - 1)) edges, for n large enough, and this bound is sharp. We also present a similar result for digraphs.

KW - Digraph

KW - Graph

KW - Interconnection networks

KW - Minimum degree

KW - Radius

KW - Size

UR - https://www.scopus.com/pages/publications/67649340794

U2 - 10.1016/j.ipl.2009.06.001

DO - 10.1016/j.ipl.2009.06.001

M3 - Article

AN - SCOPUS:67649340794

SN - 0020-0190

VL - 109

SP - 971

EP - 973

JO - Information Processing Letters

JF - Information Processing Letters

IS - 16

ER -

Minimum size of a graph or digraph of given radius

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this