{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:17:01Z","timestamp":1740107821423,"version":"3.37.3"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,9,29]],"date-time":"2023-09-29T00:00:00Z","timestamp":1695945600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,9,29]],"date-time":"2023-09-29T00:00:00Z","timestamp":1695945600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001782","name":"University of Melbourne","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001782","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2024,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The fact that the adjacency matrix of every finite graph is diagonalizable plays a fundamental role in spectral graph theory. Since this fact does not hold in general for digraphs, it is natural to ask whether it holds for digraphs with certain level of symmetry. Interest in this question dates back to the early 1980\u00a0s, when P.\u00a0J.\u00a0Cameron asked for the existence of arc-transitive digraphs with non-diagonalizable adjacency matrix. This was answered in the affirmative by Babai (J Graph Theory 9:363\u2013370, 1985). Then Babai posed the open problems of constructing a 2-arc-transitive digraph and a vertex-primitive digraph whose adjacency matrices are not diagonalizable. In this paper, we solve Babai\u2019s problems by constructing an infinite family of <jats:italic>s<\/jats:italic>-arc-transitive digraphs for each integer <jats:inline-formula><jats:alternatives><jats:tex-math>$$s\\ge 2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>s<\/mml:mi>\n                    <mml:mo>\u2265<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and an infinite family of vertex-primitive digraphs, both of whose adjacency matrices are non-diagonalizable.<\/jats:p>","DOI":"10.1007\/s00493-023-00068-x","type":"journal-article","created":{"date-parts":[[2023,9,29]],"date-time":"2023-09-29T05:02:01Z","timestamp":1695963721000},"page":"179-203","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Solution to Babai\u2019s Problems on Digraphs with Non-diagonalizable Adjacency Matrix"],"prefix":"10.1007","volume":"44","author":[{"given":"Yuxuan","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Binzhou","family":"Xia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sanming","family":"Zhou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wenying","family":"Zhu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,9,29]]},"reference":[{"key":"68_CR1","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1002\/jgt.3190090308","volume":"9","author":"L Babai","year":"1985","unstructured":"Babai, L.: Arc transitive covering digraphs and their eigenvalues. J. Graph Theory 9, 363\u2013370 (1985)","journal-title":"J. Graph Theory"},{"key":"68_CR2","first-page":"1447","volume-title":"Handbook of Combinatorics","author":"L Babai","year":"1995","unstructured":"Babai, L.: Automorphism groups, isomorphism, reconstruction. In: Graham, R.L., Gr\u00f6tschel, M., Lov\u00e1sz, L. (eds.) Handbook of Combinatorics, vol. 2, pp. 1447\u20131540. North-Holland-Elsevier, Amsterdam (1995)"},{"key":"68_CR3","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1006\/jsco.1996.0125","volume":"24","author":"W Bosma","year":"1997","unstructured":"Bosma, W., Cannon, J., Playoust, C.: The MAGMA algebra system I: the user language. J. Symb. Comput. 24, 235\u2013265 (1997)","journal-title":"J. Symb. Comput."},{"key":"68_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1112\/blms\/13.1.1","volume":"13","author":"PJ Cameron","year":"1981","unstructured":"Cameron, P.J.: Finite permutation groups and finite simple groups. Bull. Lond. Math. Soc. 13, 1\u201322 (1981)","journal-title":"Bull. Lond. Math. Soc."},{"key":"68_CR5","first-page":"89","volume-title":"Selected Topics in Graph Theory","author":"PJ Cameron","year":"1983","unstructured":"Cameron, P.J.: Automorphism groups of graphs. In: Beineke, L.W., Wilson, R.J. (eds.) Selected Topics in Graph Theory, vol. 2, pp. 89\u2013127. Academic Press, New York (1983)"},{"key":"68_CR6","series-title":"London Mathematical Society Student Texts","volume-title":"An Introduction to the Theory of Graph Spectra","author":"D Cvetkovi\u0107","year":"2010","unstructured":"Cvetkovi\u0107, D., Rowlinson, P., Simi\u0107, S.: An Introduction to the Theory of Graph Spectra. London Mathematical Society Student Texts, vol. 75. Cambridge University Press, Cambridge (2010)"},{"key":"68_CR7","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0731-3","volume-title":"Permutation Groups","author":"JD Dixon","year":"1996","unstructured":"Dixon, J.D., Mortimer, B.: Permutation Groups. Graduate Texts in Mathematics, vol. 163. Springer, New York (1996)"},{"key":"68_CR8","series-title":"Graduate Texts in Mathematics","volume-title":"Representation Theory: A First Course","author":"W Fulton","year":"1991","unstructured":"Fulton, W., Harris, J.: Representation Theory: A First Course. Graduate Texts in Mathematics, vol. 129. Springer, New York (1991)"},{"key":"68_CR9","doi-asserted-by":"publisher","first-page":"67","DOI":"10.26493\/1855-3974.1339.0ee","volume":"14","author":"M Giudici","year":"2018","unstructured":"Giudici, M., Xia, B.: Vertex-quasiprimitive 2-arc-transitive digraphs. Ars Math. Contemp. 14, 67\u201382 (2018)","journal-title":"Ars Math. Contemp."},{"key":"68_CR10","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/0024-3795(82)90024-6","volume":"46","author":"CD Godsil","year":"1982","unstructured":"Godsil, C.D.: Eigenvalues of graphs and digraphs. Linear Algebra Appl. 46, 43\u201350 (1982)","journal-title":"Linear Algebra Appl."},{"key":"68_CR11","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0163-9","volume-title":"Algebraic Graph Theory","author":"C Godsil","year":"2001","unstructured":"Godsil, C., Royle, G.: Algebraic Graph Theory. Graduate Texts in Mathematics, vol. 207. Springer, New York (2001)"},{"key":"68_CR12","series-title":"Studies in Mathematics","first-page":"225","volume-title":"Eigenvalues of Graphs, in Studies in Graph Theory, Part II","author":"AJ Hoffman","year":"1975","unstructured":"Hoffman, A.J.: Eigenvalues of Graphs, in Studies in Graph Theory, Part II. Studies in Mathematics, vol. 12, pp. 225\u2013245. Mathematical Association of America, Washington, DC (1975)"},{"key":"68_CR13","volume-title":"Topics in Matrix Analysis","author":"RA Horn","year":"1994","unstructured":"Horn, R.A., Johnson, C.R.: Topics in Matrix Analysis. Cambridge University Press, New York (1994)"},{"key":"68_CR14","volume-title":"Expander Families and Cayley Graphs: A Beginner\u2019s Guide","author":"M Krebs","year":"2011","unstructured":"Krebs, M., Shaheen, A.: Expander Families and Cayley Graphs: A Beginner\u2019s Guide. Oxford University Press, Oxford (2011)"},{"key":"68_CR15","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/S0012-365X(00)00331-9","volume":"231","author":"SP Mansilla","year":"2001","unstructured":"Mansilla, S.P., Serra, O.: Construction of $$k$$-arc transitive digraphs. Discrete Math. 231, 337\u2013349 (2001)","journal-title":"Discrete Math."},{"key":"68_CR16","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/j.jctb.2004.04.004","volume":"92","author":"H Suzuki","year":"2004","unstructured":"Suzuki, H.: Thin weakly distance-regular digraphs. J. Combin. Theory Ser. B 92, 69\u201383 (2004)","journal-title":"J. Combin. Theory Ser. B"},{"key":"68_CR17","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/j.ejc.2003.09.009","volume":"25","author":"K Wang","year":"2004","unstructured":"Wang, K.: Commutative weakly distance-regular digraphs of girth $$2$$. Eur. J. Combin. 25, 363\u2013375 (2004)","journal-title":"Eur. J. Combin."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-023-00068-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-023-00068-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-023-00068-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,21]],"date-time":"2024-02-21T22:03:19Z","timestamp":1708552999000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-023-00068-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,29]]},"references-count":17,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,2]]}},"alternative-id":["68"],"URL":"https:\/\/doi.org\/10.1007\/s00493-023-00068-x","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"type":"print","value":"0209-9683"},{"type":"electronic","value":"1439-6912"}],"subject":[],"published":{"date-parts":[[2023,9,29]]},"assertion":[{"value":"1 August 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 July 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 September 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 September 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}