Nordhaus-Gaddum relations for proximity and remoteness in graphs

M. Aouchiche; P. Hansen

doi:10.1016/j.camwa.2010.02.001

Nordhaus-Gaddum relations for proximity and remoteness in graphs

M. Aouchiche, P. Hansen

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

28 Citations (Scopus)

Abstract

The transmission of a vertex in a connected graph is the sum of all distances from that vertex to the others. It is said to be normalized if divided by n - 1, where n denotes the order of the graph. The proximity of a graph is the minimum normalized transmission, while the remoteness is the maximum normalized transmission. In this paper, we give Nordhaus-Gaddum-type inequalities for proximity and remoteness in graphs. The extremal graphs are also characterized for each case.

Original language	English
Pages (from-to)	2827-2835
Number of pages	9
Journal	Computers and Mathematics with Applications
Volume	59
Issue number	8
DOIs	https://doi.org/10.1016/j.camwa.2010.02.001
Publication status	Published - Apr 2010
Externally published	Yes

Keywords

Extremal graph
Nordhaus-Gaddum
Proximity
Remoteness

ASJC Scopus subject areas

Modelling and Simulation
Computational Theory and Mathematics
Computational Mathematics

Access to Document

10.1016/j.camwa.2010.02.001

Cite this

@article{056e7f16753546c7922e07abd7d0a03e,

title = "Nordhaus-Gaddum relations for proximity and remoteness in graphs",

abstract = "The transmission of a vertex in a connected graph is the sum of all distances from that vertex to the others. It is said to be normalized if divided by n - 1, where n denotes the order of the graph. The proximity of a graph is the minimum normalized transmission, while the remoteness is the maximum normalized transmission. In this paper, we give Nordhaus-Gaddum-type inequalities for proximity and remoteness in graphs. The extremal graphs are also characterized for each case.",

keywords = "Extremal graph, Nordhaus-Gaddum, Proximity, Remoteness",

author = "M. Aouchiche and P. Hansen",

year = "2010",

month = apr,

doi = "10.1016/j.camwa.2010.02.001",

language = "English",

volume = "59",

pages = "2827--2835",

journal = "Computers and Mathematics with Applications",

issn = "0898-1221",

publisher = "Elsevier Limited",

number = "8",

}

TY - JOUR

T1 - Nordhaus-Gaddum relations for proximity and remoteness in graphs

AU - Aouchiche, M.

AU - Hansen, P.

PY - 2010/4

Y1 - 2010/4

N2 - The transmission of a vertex in a connected graph is the sum of all distances from that vertex to the others. It is said to be normalized if divided by n - 1, where n denotes the order of the graph. The proximity of a graph is the minimum normalized transmission, while the remoteness is the maximum normalized transmission. In this paper, we give Nordhaus-Gaddum-type inequalities for proximity and remoteness in graphs. The extremal graphs are also characterized for each case.

AB - The transmission of a vertex in a connected graph is the sum of all distances from that vertex to the others. It is said to be normalized if divided by n - 1, where n denotes the order of the graph. The proximity of a graph is the minimum normalized transmission, while the remoteness is the maximum normalized transmission. In this paper, we give Nordhaus-Gaddum-type inequalities for proximity and remoteness in graphs. The extremal graphs are also characterized for each case.

KW - Extremal graph

KW - Nordhaus-Gaddum

KW - Proximity

KW - Remoteness

UR - http://www.scopus.com/inward/record.url?scp=77950189090&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77950189090&partnerID=8YFLogxK

U2 - 10.1016/j.camwa.2010.02.001

DO - 10.1016/j.camwa.2010.02.001

M3 - Article

AN - SCOPUS:77950189090

SN - 0898-1221

VL - 59

SP - 2827

EP - 2835

JO - Computers and Mathematics with Applications

JF - Computers and Mathematics with Applications

IS - 8

ER -

Nordhaus-Gaddum relations for proximity and remoteness in graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this