# Consultar departamento

Por fecha Por autores Por títulos Por temas (CDU)

Del documento Todo RECERCAT

# Mi RECERCAT

Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/2150

 Título: Some applications of the proper and adjacency polynomials in the theory of graph spectra Fiol Mora, Miquel Àngel Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV; Universitat Politècnica de Catalunya. COMBGRAF - Combinatòria, Teoria de Grafs i Aplicacions Given a vertex $u\inV$ of a graph $\Gamma=(V,E)$, the (local) proper polynomials constitute a sequence of orthogonal polynomials, constructed from the so-called $u$-local spectrum of $\Gamma$. These polynomials can be thought of as a generalization, for all graphs, of the distance polynomials for te distance-regular graphs. The (local) adjacency polynomials, which are basically sums of proper polynomials, were recently used to study a new concept of distance-regularity for non-regular graphs, and also to give bounds on some distance-related parameters such as the diameter. Here we develop the subject of these polynomials and gave a survey of some known results involving them. For instance, distance-regular graphs are characterized from their spectra and the number of vertices at extremal distance'' from each of their vertices. Afterwards, some new applications of both, the proper and adjacency polynomials, are derived, such as bounds for the radius of $\Gamma$ and the weight $k$-excess of a vertex. Given the integers $k,\mu\ge 0$, let $\Gamma_k^{\mu}(u)$ denote the set of vertices which are at distance at least $k$ from a vertex $u\in V$, and there exist exactly $\mu$ (shortest) $k$-paths from $u$ to each each of such vertices. As a main result, an upper bound for the cardinality of $\Gamma_k^{\mu}(u)$ is derived, showing that $|\Gamma_k^{\mu}(u)|$ decreases at least as $O(\mu^{-2})$, and the cases in which the bound is attained are characterized. When these results are particularized to regular graphs with four distinct eigenvalues, we reobtain a result of Van Dam about $3$-class association schemes, and prove some conjectures of Haemers and Van Dam about the number of vertices at distane three from every vertex of a regular graph with four distinct eigenvalues---setting $k=2$ and $\mu=0$---and, more generally, the number of non-adjacent vertices to every vertex $u\in V$, which have $\mu$ common neighbours with it. Peer Reviewed Graph theoryCombinatoricsGraphOrthogonal polynomialsAdjacency matrixLocal spectrumDistance-regular graphAssociation schemeGrafs, Teoria deCombinacions (Matemàtica)Classificació AMS::05 Combinatorics::05C Graph theoryClassificació AMS::05 Combinatorics::05E Algebraic combinatorics Artículo

## Otros documentos del mismo autor/a

Fiol Mora, Miquel Àngel; Serra Albó, Oriol
Dalfó Simó, Cristina; Fiol Mora, Miquel Àngel
Fiol Mora, Miquel Àngel; Vilaltella Castanyer, Joan
Dalfó Simó, Cristina; Fiol Mora, Miquel Àngel

Coordinación

Patrocinio