×

Edge-distance-regular graphs are distance-regular. (English) Zbl 1277.05050

Summary: A graph is edge-distance-regular when it is distance-regular around each of its edges and it has the same intersection numbers for any edge taken as a root. In this paper we give some (combinatorial and algebraic) proofs of the fact that every edge-distance-regular graph \({\Gamma}\) is distance-regular and homogeneous. More precisely, \({\Gamma}\) is edge-distance-regular if and only if it is bipartite distance-regular or a generalized odd graph. Also, we obtain the relationships between some of their corresponding parameters, mainly, the distance polynomials and the intersection numbers.

MSC:

05C12 Distance in graphs
42C05 Orthogonal functions and polynomials, general theory of nontrigonometric harmonic analysis
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Biggs, N., Algebraic Graph Theory (1993), Cambridge University Press: Cambridge University Press Cambridge
[2] Brouwer, A. E.; Cohen, A. M.; Neumaier, A., Distance-Regular Graphs (1989), Springer-Verlag: Springer-Verlag Berlin, New York · Zbl 0747.05073
[3] Cámara, M.; Dalfó, C.; Fàbrega, J.; Fiol, M. A.; Garriga, E., Edge-distance-regular graphs, J. Combin. Theory Ser. A, 118, 2071-2091 (2011) · Zbl 1231.05083
[4] Cvetković, C. D.; Doob, M.; Sachs, H., Spectra of Graphs (1980), Johann Barth Verlag: Deutscher Verlag der Wissenschaften: Johann Barth Verlag: Deutscher Verlag der Wissenschaften Berlin: Academic Press: Johann Barth Verlag: Deutscher Verlag der Wissenschaften: Johann Barth Verlag: Deutscher Verlag der Wissenschaften Berlin: Academic Press New York, first edition:
[5] Dalfó, C.; van Dam, E. R.; Fiol, M. A.; Garriga, E.; Gorissen, B. L., On almost distance-regular graphs, J. Combin. Theory Ser. A, 118, 1094-1113 (2011) · Zbl 1225.05249
[6] Curtin, B.; Nomura, K., 1-homogeneous, pseudo-1-homogeneous, and 1-thin distance-regular graphs, J. Combin. Theory Ser. B, 93, 279-302 (2005) · Zbl 1060.05101
[7] 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
[8] van Dam, E. R.; Fiol, M. A., A short proof of the odd-girth theorem, Electron. J. Combin., 19, 3 (2012), #P12 · Zbl 1253.05098
[9] van Dam, E. R.; Haemers, W. H., An odd characterization of the generalized odd graphs, J. Combin. Theory Ser. B, 101, 6, 486-489 (2011) · Zbl 1234.05157
[10] Fiol, M. A., Algebraic characterizations of distance-regular graphs, Discrete Math., 246, 111-129 (2002) · Zbl 1025.05060
[11] 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
[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., An algebraic characterization of completely regular codes in distance-regular graphs, SIAM J. Discrete Math., 15, 1, 1-13 (2001) · Zbl 1044.05069
[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] Godsil, C. D., Algebraic Combinatorics (1993), Chapman and Hall: Chapman and Hall New York · Zbl 0814.05075
[16] 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
[17] Hoffman, A. J., On the polynomial of a graph, Amer. Math. Monthly, 70, 30-36 (1963) · Zbl 0112.14901
[18] Lee, G.-S.; Weng, C.-W., The spectral excess theorem for general graphs, J. Combin. Theory Ser. A, 119, 1427-1431 (2012) · Zbl 1245.05087
[20] Nomura, K., Homogeneous graphs and regular near polygons, J. Combin. Theory Ser. B, 60, 63-71 (1994) · Zbl 0793.05130
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.