Premium
Proximity and remoteness in graphs: Results and conjectures
Author(s) -
Aouchiche Mustapha,
Hansen Pierre
Publication year - 2011
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20450
Subject(s) - combinatorics , mathematics , independence number , vertex (graph theory) , upper and lower bounds , matching (statistics) , graph , order (exchange) , connectivity , discrete mathematics , statistics , mathematical analysis , finance , economics
The proximity π = π( G ) of a connected graph G is the minimum, over all vertices, of the average distance from a vertex to all others. Similarly, the maximum is called the “remoteness” and denoted by ρ = ρ( G ). In this article we first prove upper and lower bounds on π and ρ as a function of the order n of G . A comparison between these two invariants follows and then each one is compared to the diameter, radius, average eccentricity, average distance, independence number and matching number. Most bounds so obtained are proved, but a few of them remain conjectures. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011