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

DOI10.1016/J.DAM.2006.04.001MaRDI QIDQ2506366zbMATH OpenOpenAlexWikidataFDO

Publication date 28 September 2006

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0602437

Distance in graphs (05C12) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18)

Abstract: The conditional diameter of a connected graph

G a m m a = (V, E)

is defined as follows: given a property

c a l P

of a pair

(G a m m a_{1}, G a m m a_{2})

of subgraphs of

G a m m a

, the so-called emph{conditional diameter} or

c a l P

-{em diameter} measures the maximum distance among subgraphs satisfying

c a l P

. That is, [ D_{{cal P}}(Gamma):=max_{Gamma_1, Gamma_2subset Gamma} {partial(Gamma_1, Gamma_2): Gamma_1, Gamma_2 quad { m satisfy }quad {cal P}}. ] In this paper we consider the conditional diameter in which

c a l P

requires that

d e l t a (u) g e a l p h a

for all

u i n V (G a m m a_{1})

,

for all

v i n V (G a m m a_{2})

,

| V (G a m m a_{1}) | g e s

and

| V (G a m m a_{2}) | g e t

for some integers

1 l e s, t l e | V |

and

, where

d e l t a (x)

denotes the degree of a vertex

x

of

G a m m a

,

d e l t a

denotes the minimum degree and

D e l t a

the maximum degree of

G a m m a

. The conditional diameter obtained is called

-emph{diameter}. We obtain upper bounds on the

-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.

Review text

Given a property \(P\) of a pair \((G_1,G_2)\) of subgraphs of a graph \(G\), the conditional diameter or \(P\)-diameter measures the maximum distance among subgraphs satisfying \(P\). In this paper \(P\) requires that the minimum degrees of the subgraphs are at least \(\alpha\) and \(\beta\), and their orders are at least \(s\) and \(t\), respectively. Upper bounds on the conditional diameter are established by using alternating polynomials on the mesh of eigenvalues.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: The \((\alpha ,\beta ,s,t)\)-diameter of graphs: a particular case of conditional diameter

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2506366)