The (a,b,s,t)-diameter of graphs: a particular case of conditional diameter

Abstract

The conditional diameter of a connected graph $\Gamma =(V,E)$ is defined as follows: given a property $\mathcal{P}$ of a pair $({\Gamma }_1,{\Gamma }_2)$ of subgraphs of $\Gamma$, the so-called \emph{conditional diameter} or $\mathcal{P}$-{\em diameter} measures the maximum distance among subgraphs satisfying $\mathcal{P}$. That is, \[ D_{\cal P}(Γ):=\max_{Γ_1, Γ_2\subset Γ} \{\partial(Γ_1, Γ_2): Γ_1, Γ_2 \quad {\rm satisfy }\quad {\cal P}\}. \] In this paper we consider the conditional diameter in which $\mathcal{P}$ requires that $\delta (u)\ge \alpha$ for all $u\in V({\Gamma }_1)$, $\delta (v)\ge \beta$ for all $v\in V({\Gamma }_2)$, $|V({\Gamma }_1)|\ge s$ and $|V({\Gamma }_2)|\ge t$ for some integers $1\le s,t\le |V|$ and $\delta \le \alpha ,\beta \le \Delta$, where $\delta (x)$ denotes the degree of a vertex $x$ of $\Gamma$, $\delta$ denotes the minimum degree and $\Delta$ the maximum degree of $\Gamma$. The conditional diameter obtained is called $(\alpha ,\beta ,s,t)$-\emph{diameter}. We obtain upper bounds on the $(\alpha ,\beta ,s,t)$-diameter by using the $k$-alternating polynomials on the mesh of eigenvalues of an associated weighted graph. The method provides also bounds for other parameters such as vertex separators.

Cited by in corpus (1)

• On the Randić index and conditional parameters of a graph