Distance mean-regular graphs

V. Diego, M. A. Fiol

Published 2015-08-16Version 1

We introduce the concept of distance mean-regular graph, which can be seen as a generalization of both vertex-transitive and distance-regular graphs. Let $\Gamma$ be a graph with vertex set $V$, diameter $D$, adjacency matrix $A$, and adjacency algebra ${\cal A}$. Then, $\Gamma$ is $distance$ $mean$-$regular$ when, for a given $u\in V$, the averages of the intersection numbers $p_{ij}^h(u,v)=|\Gamma_i(u)\cap \Gamma_j(v)|$ (number of vertices at distance $i$ from $u$ and distance $j$ from $v$) computed over all vertices $v$ at a given distance $h\in \{0,1,\ldots,D\}$ from $u$, do not depend on $u$. In this work we study some properties and characterizations of these graphs. For instance, it is shown that a distance mean-regular graph is always distance degree-regular, and we give a condition for the converse to be also true. Some algebraic and spectral properties of distance mean-regular graphs are also investigated. We show that, for distance mean regular-graphs, the role of the distance matrices of distance-regular graphs is played for the so-called distance mean-regular matrices. These matrices are computed from a sequence of orthogonal polynomials evaluated at the adjacency matrix of $\Gamma$ and, hence, they generate a subalgebra of ${\cal A}$. Some other algebras associated to distance mean-regular graphs are also characterized.