Extremal Values for the Maximum Degree in a Twin-Free Graph

Abstract

Consider a connected undirected graph \(G = (V, E)\) and an integer \(r \geq 1\); for any vertex \(v \in V\), let \(B_r(v)\) denote the ball of radius \(r\) centred at \(v\), i.e., the set of all vertices linked to \(v\) by a path of at most \(r\) edges. If for all vertices \(v \in V\), the sets \(B_r(v)\) are different, then we say that \(G\) is \(r\)-twin-free.

In \(r\)-twin-free graphs, we prolong the study of the extremal values that can be reached by some classical parameters in graph theory, and investigate here the maximum degree.