Anzeige
Erschienen in:
26.06.2020
Average eccentricity, minimum degree and maximum degree in graphs
Erschienen in: Journal of Combinatorial Optimization | Ausgabe 3/2020
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Let G be a connected finite graph with vertex set V(G). The eccentricity e(v) of a vertex v is the distance from v to a vertex farthest from v. The average eccentricity of G is defined as \(\frac{1}{|V(G)|}\sum _{v \in V(G)}e(v)\). We show that the average eccentricity of a connected graph of order n, minimum degree \(\delta \) and maximum degree \(\Delta \) does not exceed \(\frac{9}{4} \frac{n-\Delta -1}{\delta +1} \big ( 1 + \frac{\Delta -\delta }{3n} \big ) + 7\), and this bound is sharp apart from an additive constant. We give improved bounds for triangle-free graphs and for graphs not containing 4-cycles.