Distance–regular graphs having the M-property

Abstract

We analyse when the Moore–Penrose inverse of the combinatorial Laplacian of a distance–regular graph is an M-matrix; that is, it has non-positive off-diagonal elements or, equivalently when the Moore–Penrose inverse of the combinatorial Laplacian of a distance–regular graph is also the combinatorial Laplacian of another network. When this occurs we say that the distance–regular graph has the M-property. We prove that only distance–regular graphs with diameter up to three can have the M-property and we give a characterization of the graphs that satisfy the M-property in terms of their intersection array. Moreover, we exhaustively analyse strongly regular graphs having the M-property and we give some families of distance–regular graphs with diameter three that satisfy the M-property. Roughly speaking, we prove that all distance–regular graphs with diameter one; about half of the strongly regular graphs; only some imprimitive distance–regular graphs with diameter three, and no distance–regular graphs with diameter greater than three, have the M-property. In addition, we conjecture that no primitive distance–regular graph with diameter three has the M-property.

Keywords:

• M-matrix
• Moore–Penrose inverse
• equilibrium measure
• distance–regular graphs

AMS Subject Classification:

• 15A09

Acknowledgements

This work has been partly supported by the Spanish Research Council (Comisión Interministerial de Ciencia y Tecnología) under projects MTM2007-62551 and MTM2008-06620-C03-01/MTM.