Proximity and remoteness in triangle-free and C_4-free graphs in terms of order and minimum degree

preprint2020arXivOpen access

Abstract

Let GG be a finite, connected graph. The average distance of a vertex vv of GG is the arithmetic mean of the distances from vv to all other vertices of GG. The remoteness ρ(G)ρ(G) and the proximity π(G)π(G) of GG are the maximum and the minimum of the average distances of the vertices of GG. In this paper, we present a sharp upper bound on the remoteness of a triangle-free graph of given order and minimum degree, and a corresponding bound on the proximity, which is sharp apart from an additive constant. We also present upper bounds on the remoteness and proximity of C4C_4-free graphs of given order and minimum degree, and we demonstrate that these are close to being best possible.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.