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

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

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.

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)