The (a,b,s,t)-diameter of graphs: a particular case of conditional diameter
| dc.creator | Rodriguez, J. A. | |
| dc.date | 2006-02-20 | |
| dc.date.accessioned | 2026-07-07T07:03:37Z | |
| dc.date.available | 2026-07-07T07:03:37Z | |
| dc.description | The conditional diameter of a connected graph $Γ=(V,E)$ is defined as follows: given a property ${\cal P}$ of a pair $(Γ_1, Γ_2)$ of subgraphs of $Γ$, the so-called \emph{conditional diameter} or ${\cal P}$-{\em diameter} measures the maximum distance among subgraphs satisfying ${\cal 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 ${\cal P}$ requires that $δ(u)\ge α$ for all $ u\in V(Γ_1)$, $δ(v)\ge β$ for all $v\in V(Γ_2)$, $| V(Γ_1)| \ge s$ and $| V(Γ_2)| \ge t$ for some integers $1\le s,t\le |V|$ and $δ\le α, β\le Δ$, where $δ(x)$ denotes the degree of a vertex $x$ of $Γ$, $δ$ denotes the minimum degree and $Δ$ the maximum degree of $Γ$. The conditional diameter obtained is called $(α,β, s,t)$-\emph{diameter}. We obtain upper bounds on the $(α,β, 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. | |
| dc.identifier | https://arxiv.org/abs/math/0602437 | |
| dc.identifier | http://arxiv.org/abs/math/0602437 | |
| dc.identifier | Discrete Applied Mathematics 154 (14) (2006) 2024-2031 | |
| dc.identifier | doi:10.1016/j.dam.2006.04.001 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/109038 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C50; 05C12; 15A18 | |
| dc.title | The (a,b,s,t)-diameter of graphs: a particular case of conditional diameter | |
| dc.type | text |