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

Abstract

Consider a connected undirected graph $G=(V,E)$ and an integer $r\ge 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.