Diameter and connectivity of finite simple graphs II

Abstract

Let $G$ be a finite simple non-complete connected graph on $[n]=\{1,\dots ,n\}$ and $\kappa (G)\ge 1$ its vertex connectivity. Let $f(G)$ denote the number of free vertices of $G$ and $\mathrm{diam}(G)$ the diameter of $G$. The final goal of this paper is to determine all sequences of integers $(n,f,d,k)$ with $n\ge 8$, $f\ge 0$, $d\ge 2$ and $k\ge 1$ for which there exists a finite simple non-complete connected graph on $[n]$ with $f=f(G)$, $d=\mathrm{diam}(G)$ and $k=\kappa (G)$.

11 pages, 3 figures