Diameter and connectivity of finite simple graphs

Abstract

Let $G$ be a finite simple non-complete connected graph on $\{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$. Being motivated by the computation of the depth of the binomial edge ideal of $G$, the possible sequences $(n,q,f,d)$ of integers for which there is a finite simple non-complete connected graph $G$ on $\{1,\dots ,n\}$ with $q=\kappa (G),f=f(G),d=\mathrm{diam}(G)$ satisfying $f+d=n+2-q$ will be determined. Furthermore, finite simple non-complete connected graphs $G$ on $\{1,\dots ,n\}$ satisfying $f(G)+\mathrm{diam}(G)=n+2-\kappa (G)$ will be classified.

10 pages, 8 figures