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

DOI10.1016/J.DAM.2006.04.001zbMATH Open1105.05021arXivmath/0602437OpenAlexW2124619091WikidataQ57974504 ScholiaQ57974504MaRDI QIDQ2506366FDOQ2506366

Authors: Juan A. Rodríguez-Velázquez 

Publication date: 28 September 2006

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

Abstract: The conditional diameter of a connected graph $Gamma=(V,E)$ is defined as follows: given a property $calP$ of a pair $(Gamm{a}_1,Gamm{a}_2)$ of subgraphs of $Gamma$, the so-called emph{conditional diameter} or $calP$-{em diameter} measures the maximum distance among subgraphs satisfying $calP$. 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 $calP$ requires that $delta(u)gealpha$ for all $uinV(Gamm{a}_1)$, $$ for all $vinV(Gamm{a}_2)$, $|V(Gamm{a}_1)|ges$ and $|V(Gamm{a}_2)|get$ for some integers $1les,tle|V|$ and $$, 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 $$-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.

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

Recommendations

• The alternating polynomials and their relation with the spectra and conditional diameters of graphs
• scientific article; zbMATH DE number 5119227
• On size, order, minimum degree and conditional diameter of graphs
• Conditional diameter saturated graphs
• scientific article; zbMATH DE number 961975

zbMATH Keywords

graph eigenvaluealternating polynomial

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• A spectral approach to the Randić index
• On a class of polynomials and its relation with the spectra and diameters of graphs
• The alternating polynomials and their relation with the spectra and conditional diameters of graphs
• Bounding the diameter and the mean distance of a graph from its eigenvalues: Laplacian versus adjacency matrix methods
• On the superconnectivity and the conditional diameter of graphs and digraphs
• Superconnected digraphs and graphs with small conditional diameters
• Title not available (Why is that?)
• On the Laplacian Eigenvalues and Metric Parameters of Hypergraphs
• On spectral bounds for cutsets
• Title not available (Why is that?)

Cited In (4)

• Note on structural properties of graphs
• On size, order, minimum degree and conditional diameter of graphs
• Conditional diameter saturated graphs
• Title not available (Why is that?)

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)