Mathematics – Combinatorics
Scientific paper
2006-02-20
Discrete Applied Mathematics 154 (14) (2006) 2024-2031
Mathematics
Combinatorics
Scientific paper
10.1016/j.dam.2006.04.001
The conditional diameter of a connected graph $\Gamma=(V,E)$ is defined as follows: given a property ${\cal P}$ of a pair $(\Gamma_1, \Gamma_2)$ of subgraphs of $\Gamma$, 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}}(\Gamma):=\max_{\Gamma_1, \Gamma_2\subset \Gamma} \{\partial(\Gamma_1, \Gamma_2): \Gamma_1, \Gamma_2 \quad {\rm satisfy }\quad {\cal P}\}. \] In this paper we consider the conditional diameter in which ${\cal 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.
No associations
LandOfFree
The (a,b,s,t)-diameter of graphs: a particular case of conditional diameter does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The (a,b,s,t)-diameter of graphs: a particular case of conditional diameter, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The (a,b,s,t)-diameter of graphs: a particular case of conditional diameter will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-520827