Some graphs $\varGamma$ have the following property $\cal P$: {\it the configuration graph (i.e. the non--collinearity graph) of the neighbourhood geometry of $\varGamma$ is isomorphic to} $\varGamma$. For instance, the ubiquitous Petersen graph satisfies $\cal P$. The purpose of this paper is to reveal repercussions of property $\cal P$ on adjacency matrices $A$ for $\varGamma$. This will be achieved in terms of invariance under (powers of) the following mapping $\varTheta$: denote by $I$ and $J$ the identity matrix and the all one matrix, respectively, both of order $n = k^2+1$, and define $\varTheta(A):= (k-1)I +J -A^2$. If $k = 3$ and $A$ is an adjacency matrix for the Petersen graph, it is well known that $\varTheta(A)=A$. In 1960, Hoffman and Singleton showed that for arbitrary $k$ the matrix equation $\varTheta(A)=A$ has only very few solutions, namely for $k = 2,3,7$ and possibly for $k = 57$. We prove that the property $\cal P$ implies the existence of an integer $m \ge 1$ such that $\varTheta ^m(A)=A$. We determine a standard form for such matrices which is invariant under the action of $\varTheta$. In particular, we characterize all solutions, on $A$, to $\varTheta ^m(A)=A$ \/ for $k=3$ and $k=4$, where $A$ is an adjacency matrix of some $k$--regular graph, solving a conjecture posed by the authors.

Invariant adjacency matrices of configuration graphs

ABREU, Marien;FUNK, Martin;LABBATE, Domenico;
2012-01-01

Abstract

Some graphs $\varGamma$ have the following property $\cal P$: {\it the configuration graph (i.e. the non--collinearity graph) of the neighbourhood geometry of $\varGamma$ is isomorphic to} $\varGamma$. For instance, the ubiquitous Petersen graph satisfies $\cal P$. The purpose of this paper is to reveal repercussions of property $\cal P$ on adjacency matrices $A$ for $\varGamma$. This will be achieved in terms of invariance under (powers of) the following mapping $\varTheta$: denote by $I$ and $J$ the identity matrix and the all one matrix, respectively, both of order $n = k^2+1$, and define $\varTheta(A):= (k-1)I +J -A^2$. If $k = 3$ and $A$ is an adjacency matrix for the Petersen graph, it is well known that $\varTheta(A)=A$. In 1960, Hoffman and Singleton showed that for arbitrary $k$ the matrix equation $\varTheta(A)=A$ has only very few solutions, namely for $k = 2,3,7$ and possibly for $k = 57$. We prove that the property $\cal P$ implies the existence of an integer $m \ge 1$ such that $\varTheta ^m(A)=A$. We determine a standard form for such matrices which is invariant under the action of $\varTheta$. In particular, we characterize all solutions, on $A$, to $\varTheta ^m(A)=A$ \/ for $k=3$ and $k=4$, where $A$ is an adjacency matrix of some $k$--regular graph, solving a conjecture posed by the authors.
2012
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11563/9235
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact