Notes on simplicial rook graphs. (English) Zbl 1339.05222
Summary: The simplicial rook graph \(\mathrm{SR}(m,n)\) is the graph of which the vertices are the sequences of nonnegative integers of length \(m\) summing to \(n\), where two such sequences are adjacent when they differ in precisely two places. We show that \(\mathrm{SR}(m,n)\) has integral eigenvalues, and smallest eigenvalue \(s = \max(-n,-{{m}\choose{2}})\), and that this graph has a large part of its spectrum in common with the Johnson graph \(J(m+n-1,n)\). We determine the automorphism group and several other properties.
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |
Software:
MathOverflowReferences:
| [1] | Blackburn, S.R., Paterson, M.B., Stinson, D.R.: Putting dots in triangles. J. Comb. Math. Combin. Comput. 78, 23-32 (2011) · Zbl 1234.05050 |
| [2] | Brouwer, A.E., Cohen, A.M., Neumaier, A.: Distance-Regular Graphs. Springer, New York (1989) · Zbl 0747.05073 · doi:10.1007/978-3-642-74341-2 |
| [3] | Brouwer, A.E., Haemers, W.H.: Spectra of Graphs. Springer, New York (2012) · Zbl 1231.05001 · doi:10.1007/978-1-4614-1939-6 |
| [4] | Chang, L.C.: The uniqueness and nonuniqueness of the triangular association scheme. Sci. Rec. 3, 604-613 (1959) · Zbl 0089.15102 |
| [5] | Chang, L.C.: Association schemes of partially balanced block designs with parameters \[v = 28v=28, n_1 = 12n1=12, n_2 = 15\] n2=15 and \[p_{11}^2 = 4\] p112=4. Sci. Rec. 4, 12-18 (1960) · Zbl 0093.32101 |
| [6] | Elkies, N.D.: Mathoverflow (2012). http://mathoverflow.net/questions/103540/hexagonal-rooks · Zbl 1081.05003 |
| [7] | Godsil, C.D., McKay, B.D.: Constructing cospectral graphs. Aequ. Math. 25, 257-268 (1982) · Zbl 0527.05051 · doi:10.1007/BF02189621 |
| [8] | Humphreys, J.E.: Reflection Groups and Coxeter Groups. Cambridge University Press, Cambridge (1990) · Zbl 0725.20028 |
| [9] | Martin, J.L., Wagner, J.D.: On the spectra of simplicial rook graphs, arXiv:1209.3493 / Graphs and Combinatorics, on-line 18 May 2014 / pp. 373-386 In: Proceedings of the 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), Discrete Math. Theor. Comput. Sci. Proc, Nancy (2013) · Zbl 1294.05111 |
| [10] | Nivasch, G., Lev, E.: Non-attacking queens on a triangle. Math. Mag. 78, 399-403 (2005) · Zbl 1081.05003 · doi:10.2307/30044202 |
| [11] | Vaderlind, P., Guy, R.K., Larson, L.C.: The Inquisitive Problem Solver. MAA Problem Book Series. Mathematical Association of America, Washington, DC (2002) · Zbl 1067.00006 |
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.
