Feasibility conditions for the existence of walk-regular graphs |
| |
Authors: | CD Godsil BD McKay |
| |
Institution: | Department of Mathematics University of Melbourne Parkville, Victoria 3052 Australia |
| |
Abstract: | A graph X is walk-regular if the vertex-deleted subgraphs of X all have the same characteristic polynomial. Examples of such graphs are vertex-transitive graphs and distance-regular graphs. We show that the usual feasibility conditions for the existence of a distance-regular graph with a given intersection array can be extended so that they apply to walk-regular graphs. Despite the greater generality, our proofs are more elementary than those usually given for distance-regular graphs. An application to the computation of vertex-transitive graphs is described. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |