On almost distance-regular graphs.

*(English)*Zbl 1225.05249Summary: Distance-regular graphs are a key concept in Algebraic Combinatorics and have given rise to several generalizations, such as association schemes. Motivated by spectral and other algebraic characterizations of distance-regular graphs, we study ‘almost distance-regular graphs’. We use this name informally for graphs that share some regularity properties that are related to distance in the graph. For example, a known characterization of a distance-regular graph is the invariance of the number of walks of given length between vertices at a given distance, while a graph is called walk-regular if the number of closed walks of given length rooted at any given vertex is a constant.

One of the concepts studied here is a generalization of both distance-regularity and walk-regularity called \(m\)-walk-regularity. Another studied concept is that of \(m\)-partial distance-regularity or, informally, distance-regularity up to distance \(m\). Using eigenvalues of graphs and the predistance polynomials, we discuss and relate these and other concepts of almost distance-regularity, such as their common generalization of \((\ell ,m)\)-walk-regularity.

We introduce the concepts of punctual distance-regularity and punctual walk-regularity as a fundament upon which almost distance-regular graphs are built. We provide examples that are mostly taken from the Foster census, a collection of symmetric cubic graphs. Two problems are posed that are related to the question of when almost distance-regular becomes whole distance-regular. We also give several characterizations of punctually distance-regular graphs that are generalizations of the spectral excess theorem.

One of the concepts studied here is a generalization of both distance-regularity and walk-regularity called \(m\)-walk-regularity. Another studied concept is that of \(m\)-partial distance-regularity or, informally, distance-regularity up to distance \(m\). Using eigenvalues of graphs and the predistance polynomials, we discuss and relate these and other concepts of almost distance-regularity, such as their common generalization of \((\ell ,m)\)-walk-regularity.

We introduce the concepts of punctual distance-regularity and punctual walk-regularity as a fundament upon which almost distance-regular graphs are built. We provide examples that are mostly taken from the Foster census, a collection of symmetric cubic graphs. Two problems are posed that are related to the question of when almost distance-regular becomes whole distance-regular. We also give several characterizations of punctually distance-regular graphs that are generalizations of the spectral excess theorem.

##### Keywords:

distance-regular graph; walk-regular graph; eigenvalues; local multiplicities; predistance polynomial
PDF
BibTeX
XML
Cite

\textit{C. Dalfó} et al., J. Comb. Theory, Ser. A 118, No. 3, 1094--1113 (2011; Zbl 1225.05249)

**OpenURL**

##### References:

[1] | Beezer, R.A., Distance polynomial graphs, (), 51-73 |

[2] | Biggs, N., Algebraic graph theory, (1994), Cambridge University Press Cambridge, second ed., 1973 · Zbl 0797.05032 |

[3] | Bloom, G.S.; Quintas, L.W.; Kennedy, J.W., Distance degree regular graphs, (), 95-108 · Zbl 0476.05070 |

[4] | Brouwer, A.E.; Cohen, A.M.; Neumaier, A., Distance-regular graphs, (1989), Springer-Verlag Berlin/New York · Zbl 0747.05073 |

[5] | Dalfó, C.; Fiol, M.A.; Garriga, E., On k-walk-regular graphs, Electron. J. combin., 16, 1, (2009), #R47 · Zbl 1226.05107 |

[6] | Dalfó, C.; Fiol, M.A.; Garriga, E., Characterizing \((\ell, m)\)-walk-regular graphs, Linear algebra appl., 433, 1821-1826, (2010) · Zbl 1213.05164 |

[7] | van Dam, E.R.; Haemers, W.H.; Koolen, J.H.; Spence, E., Characterizing distance-regularity of graphs by the spectrum, J. combin. theory ser. A, 113, 1805-1820, (2006) · Zbl 1105.05076 |

[8] | van Dam, E.R., The spectral excess theorem for distance-regular graphs: a global (over)view, Electron. J. combin., 15, 1, (2008), #R129 · Zbl 1180.05130 |

[9] | Fiol, M.A., Algebraic characterizations of distance-regular graphs, Discrete math., 246, 111-129, (2002) · Zbl 1025.05060 |

[10] | Fiol, M.A.; Gago, S.; Garriga, E., A simple proof of the spectral excess theorem for distance-regular graphs, Linear algebra appl., 432, 2418-2422, (2010) · Zbl 1221.05112 |

[11] | Fiol, M.A.; Garriga, E., The alternating and adjacency polynomials, and their relation with the spectra and diameters of graphs, Discrete appl. math., 87, 77-97, (1998) · Zbl 0914.05050 |

[12] | Fiol, M.A.; Garriga, E., From local adjacency polynomials to locally pseudo-distance-regular graphs, J. combin. theory ser. B, 71, 162-183, (1997) · Zbl 0888.05056 |

[13] | Fiol, M.A.; Garriga, E., On the algebraic theory of pseudo-distance-regularity around a set, Linear algebra appl., 298, 115-141, (1999) · Zbl 0984.05060 |

[14] | Fiol, M.A.; Garriga, E.; Yebra, J.L.A., Locally pseudo-distance-regular graphs, J. combin. theory ser. B, 68, 179-205, (1996) · Zbl 0861.05064 |

[15] | Fiol, M.A.; Garriga, E.; Yebra, J.L.A., Boundary graphs: the limit case of a spectral property, Discrete math., 226, 155-173, (2001) · Zbl 0965.05068 |

[16] | Godsil, C.D., Algebraic combinatorics, (1993), Chapman and Hall New York · Zbl 0814.05075 |

[17] | Godsil, C.D.; McKay, B.D., Feasibility conditions for the existence of walk-regular graphs, Linear algebra appl., 30, 51-61, (1980) · Zbl 0452.05045 |

[18] | Hilano, T.; Nomura, K., Distance degree regular graphs, J. combin. theory ser. B, 37, 96-100, (1984) · Zbl 0567.05028 |

[19] | Hoffman, A.J., On the polynomial of a graph, Amer. math. monthly, 70, 30-36, (1963) · Zbl 0112.14901 |

[20] | Huang, T.; Huang, Y.; Liu, S.-C.; Weng, C., Partially distance-regular graphs and partially walk-regular graphs, (2007) |

[21] | Klin, M.; Muzychuk, M.; Ziv-Av, M., Higmanian rank-5 association schemes on 40 points, Michigan math. J., 58, 255-284, (2009) · Zbl 1284.05339 |

[22] | Martin, W.J.; Tanaka, H., Commutative association schemes, European J. combin., 30, 1497-1525, (2009) · Zbl 1228.05317 |

[23] | McKay, B.D.; Stanton, R.G., The current status of the generalised Moore graph problem, (), 21-31 · Zbl 0422.05044 |

[24] | Powers, D.L., Partially distance-regular graphs, (), 991-1000 · Zbl 0841.05098 |

[25] | Rowlinson, P., Linear algebra, (), 86-99 · Zbl 0878.05059 |

[26] | Royle, G.; Conder, M.; McKay, B.; Dobscanyi, P., Cubic symmetric graphs, (July 2009), (The Foster Census) |

[27] | Sampels, M., Vertex-symmetric generalized Moore graphs, Discrete appl. math., 138, 195-202, (2004) · Zbl 1034.05019 |

[28] | Weichsel, P.M., On distance-regularity in graphs, J. combin. theory ser. B, 32, 156-161, (1982) · Zbl 0477.05047 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.