×

zbMATH — the first resource for mathematics

Quotient-polynomial graphs. (English) Zbl 1326.05174
Summary: As a generalization of orbit-polynomial and distance-regular graphs, we introduce the concept of a quotient-polynomial graph. In these graphs every vertex \(u\) induces the same regular partition around \(u\), where all vertices of each cell are equidistant from \(u\). Some properties and characterizations of such graphs are studied. For instance, all quotient-polynomial graphs are walk-regular and distance-polynomial. Also, we show that every quotient-polynomial graph generates a (symmetric) association scheme.

MSC:
05E30 Association schemes, strongly regular graphs
05E05 Symmetric functions and generalizations
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C12 Distance in graphs
42C05 Orthogonal functions and polynomials, general theory of nontrigonometric harmonic analysis
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Biggs, N., Algebraic graph theory, (1993), Cambridge University Press Cambridge
[2] Beezer, R. A., Trivalent orbit polynomial graphs, Linear Algebra Appl., 73, 133-146, (1986) · Zbl 0657.05036
[3] Beezer, R. A., Orbit polynomial graphs of prime order, Discrete Math., 67, 139-147, (1987) · Zbl 0642.05028
[4] Brouwer, A. E.; Cohen, A. M.; Neumaier, A., Distance-regular graphs, (1989), Springer-Verlag Berlin, New York · Zbl 0747.05073
[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] van Dam, E. R., Three-class association schemes, J. Algebraic Combin., 10, 69-107, (1999) · Zbl 0929.05096
[7] Delsarte, Ph., An algebraic approach to the association schemes of coding theory, Philips Res. Rep. Suppl., 10, (1973) · Zbl 1075.05606
[8] 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
[9] 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
[10] Godsil, C. D., Algebraic combinatorics, (1993), Chapman and Hall New York · Zbl 0814.05075
[11] Godsil, C. D.; McKay, B. D., Feasibility conditions for the existence walk-regular graphs, Linear Algebra Appl., 30, 51-61, (1980) · Zbl 0452.05045
[12] Hoffman, A. J., On the polynomial of a graph, Amer. Math. Monthly, 70, 30-36, (1963) · Zbl 0112.14901
[13] Qiao, Z.; Du, S. F.; Koolen, J. H., 2-walk-regular dihedrants from group-divisible designs, (2015), preprint
[14] Weichsel, P., 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.