Diameter and connectivity of finite simple graphs


Abstract in English

Let $G$ be a finite simple non-complete connected graph on ${1, ldots, n}$ and $kappa(G) geq 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, ldots, 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, ldots, n}$ satisfying $f(G) + mathrm{diam}(G) = n + 2 - kappa(G)$ will be classified.

Download