𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Nordhaus–Gaddum relations for proximity and remoteness in graphs

✍ Scribed by M. Aouchiche; P. Hansen

Publisher
Elsevier Science
Year
2010
Tongue
English
Weight
300 KB
Volume
59
Category
Article
ISSN
0898-1221

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Nordhaus-Gaddum inequalities for dominat
Nordhaus-Gaddum inequalities for domination in graphs
✍ Frank Harary; Teresa W. Haynes 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 297 KB

A node in a graph G = (V,E) is said to dominate itself and all nodes adjacent to it. A set S C V is a dominating set for G if each node in V is dominated by some node in S and is a double dominating set for G if each node in V is dominated by at least two nodes in S. First we give a brief survey of

Edge proximity conditions for extendabil
Edge proximity conditions for extendability in cubic bipartite graphs
✍ R. E. L. Aldred; Bill Jackson 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 123 KB

## Abstract We show that a set __M__ of __m__ edges in a cyclically (3__m__ − 2)‐edge‐connected cubic bipartite graph is contained in a 1‐factor whenever the edges in __M__ are pairwise distance at least __f__(__m__) apart, where © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 112–120, 2007