𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The alternating polynomials and their relation with the spectra and conditional diameters of graphs

✍ Scribed by M.A. Fiol; E. Garriga; J.L.A. Yebra

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
527 KB
Volume
167-168
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Given a graph F on n = IV/`l vertices, the distance between two subgraphs F 1,/'2 c /', denoted by c~(F t,/'2), is the minimum among the distances between vertices of F 1 and F 2. For some integers 1 ~< s, t ~< n, the conditional (s, t)-diameter of F is then defined as D(~,t)=maxr,,r~.r{~(Fa,F2): IVFtI=s, IVF2I=t}. Let F have distinct eigenvalues 2 > 21 > 2 2 > .-. > )~d" For every k = 0, 1, ... ,d -l, the k-alternating polynomial Pk is defined to be the polynomial of degree k and norm lIP k 11 ~ = max~ ~ o{ IPk(2~)l } = 1 that attains maximum value at 2. These polynomials, which may be thought of as the discrete version of the Chebychev ones, were recently used by the authors to bound the (standard) diameter D ~ D(I ' 1~ of F in terms of its eigenvalues. In this work we derive similar results for conditional diameters. For instance, it is shown that IIvll 2

where v is the (positive) eigenvector associated to 2 with minimum component 1. Similar results are given for locally regular digraphs by using the Laplacian spectrum. Some applications to the study of other parameters, such as the connectivity of F, are also discussed.

πŸ“œ SIMILAR VOLUMES

On a Class of Polynomials and Its Relati
On a Class of Polynomials and Its Relation with the Spectra and Diameters of Graphs
✍ M.A. Fiol; E. Garriga; J.L.A. Yebra πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 602 KB

Let \* 1 >\* 2 > } } } >\* d be points on the real line. For every k=1, 2, ..., d, the k-alternating polynomial P k is the polynomial of degree k and norm Because of this optimality property, these polynomials may be thought of as the discrete version of the Chebychev polynomials T k and, for parti

On the superconnectivity and the conditi
On the superconnectivity and the conditional diameter of graphs and digraphs
✍ Carmona, A.; FοΏ½brega, J. πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 142 KB πŸ‘ 2 views

It has been proved that if the diameter D of a digraph G satisfies D Υ… 2ᐉ Οͺ 2, where ᐉ is a parameter which can be thought of as a generalization of the girth of a graph, then G is superconnected. Analogously, if D Υ… 2ᐉ Οͺ 1, then G is edge-superconnected. In this paper, we studied some similar condi

On the connectivity and the conditional
On the connectivity and the conditional diameter of graphs and digraphs
✍ Balbuena, C.; Carmona, A.; FοΏ½brega, J.; Fiol, M. A. πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 771 KB

Recently, it was proved that if the diameter D of a graph G is small enough in comparison with its girth, then G is maximally connected and that a similar result also holds for digraphs. More precisely, if the diameter D of a digraph G satisfies D 5 21 -1, then G has maximum connectivity ( K = 6 ) .