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

DOI10.1016/J.DISC.2021.112513zbMATH Open1467.05061arXiv2002.03183OpenAlexW3174749798MaRDI QIDQ2037591FDOQ2037591

Authors: Peter Dankelmann, Elizabeth Jonck, S. Mafunda 

Publication date: 8 July 2021

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: Let $G$ be a finite, connected graph. The average distance of a vertex $v$ of $G$ is the arithmetic mean of the distances from $v$ to all other vertices of $G$. The remoteness $ho(G)$ and the proximity $pi(G)$ of $G$ are the maximum and the minimum of the average distances of the vertices of $G$. 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 $C_4$-free graphs of given order and minimum degree, and we demonstrate that these are close to being best possible.

Full work available at URL: https://arxiv.org/abs/2002.03183

Recommendations

• On the difference between proximity and other distance parameters in triangle-free graphs and \(C_4\)-free graphs
• Proximity, remoteness and maximum degree in graphs
• Proximity, remoteness and minimum degree
• Proof of conjectures on remoteness and proximity in graphs
• New bounds on proximity and remoteness in graphs

zbMATH Keywords

minimum degreeproximityremotenessdistance in graphsaverage distance

Mathematics Subject Classification ID

Vertex degrees (05C07) Distance in graphs (05C12) Connectivity (05C40)

Cites Work

• Radius, diameter, and minimum degree
• Distance in graphs
• Extremal values for ratios of distances in trees
• Proximity, remoteness and girth in graphs
• Variable neighborhood search for extremal graphs. 20. Automated comparison of graph invariants
• Average distance, radius and remoteness of a graph
• Proximity and remoteness in graphs: results and conjectures
• Proximity and average eccentricity of a graph
• Title not available (Why is that?)
• Nordhaus-Gaddum relations for proximity and remoteness in graphs
• The difference between remoteness and radius of a graph
• Proximity and remoteness in directed and undirected graphs
• New bounds on proximity and remoteness in graphs
• Wiener Index and Remoteness in Triangulations and Quadrangulations
• Proximity, remoteness and minimum degree

Cited In (8)

• New bounds on proximity and remoteness in graphs
• Proximity, remoteness and maximum degree in graphs
• Upper bounds on the average eccentricity of \(K_3\)-free and \(C_4\)-free graphs
• Diameter, edge-connectivity, and \(C_4\)-freeness
• Proximity and remoteness in directed and undirected graphs
• On the difference between proximity and other distance parameters in triangle-free graphs and \(C_4\)-free graphs
• Proximity, remoteness and minimum degree
• Proximity and remoteness in graphs: a survey

This page was built for publication: Proximity and remoteness in triangle-free and \(C_4\)-free graphs in terms of order and minimum degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2037591)