{"entities":{"Q1010813":{"pageid":1012661,"ns":120,"title":"Item:Q1010813","lastrevid":66595071,"modified":"2026-04-12T11:11:07Z","type":"item","id":"Q1010813","labels":{"en":{"language":"en","value":"Nonexistence of almost Moore digraphs of diameter three"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5540992"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010813$A56F9F65-22BB-4DAD-889B-B7EAD5427A48","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1e42765c35d5b02bfe79b90632351e9482e161cf","datavalue":{"value":{"text":"Nonexistence of almost Moore digraphs of diameter three","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1010813$CE61B898-0B18-45AA-84DE-074CE1D1062D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0532286cb8971b09fd01bf46cbfffbf82fcf1bee","datavalue":{"value":"1163.05318","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010813$03442B71-79BD-4F16-B25D-0D2E46162272","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010813$4C49EFC7-6259-4B72-B3D1-2C4C8D9BC445","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f584a175cfc2fafdfc362244f176e06010bbf381","datavalue":{"value":{"time":"+2009-04-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1010813$22DB5305-A38A-482D-9B22-2EDB419D944E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cb186fc8ea0d6fa7ce34722f242a0a625f5a437d","datavalue":{"value":"https://eudml.org/doc/129979","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010813$1C54E663-478B-43D8-B700-A91484252F1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"8c4a9191ef4349ca8597c6d50dd9f10922240fc9","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_15/Abstracts/v15i1r87.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010813$2988D5AD-3B65-427D-A407-9AD099DC2465","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"790a4fd0f3a32f80dd940b39bfdde1fce1f94a40","datavalue":{"value":"Summary: Almost Moore digraphs appear in the context of the degree/diameter problem as a class of extremal directed graphs, in the sense that their order is one less than the unattainable Moore bound \\(M(d,k)=1+d+\\dots +d^k\\), where \\(d>1\\) and \\(k>1\\) denote the maximum out-degree and diameter, respectively. So far, the problem of their existence has only been solved when \\(d=2,3\\) or \\(k=2\\). In this paper, we prove that almost Moore digraphs of diameter \\(k=3\\) do not exist for any degree \\(d\\). The enumeration of almost Moore digraphs of degree \\(d\\) and diameter \\(k=3\\) turns out to be equivalent to the search of binary matrices \\(A\\) fulfilling that \\(AJ=dJ\\) and \\(I+A+A^2+A^3=J+P\\), where \\(J\\) denotes the all-one matrix and \\(P\\) is a permutation matrix. We use spectral techniques in order to show that such equation has no \\((0,1)\\)-matrix solutions. More precisely, we obtain the factorization in \\({\\mathbb Q}[x]\\) of the characteristic polynomial of \\(A\\), in terms of the cycle structure of \\(P\\), we compute the trace of \\(A\\) and we derive a contradiction on some algebraic multiplicities of the eigenvalues of \\(A\\). In order to get the factorization of \\(\\det(xI-A)\\) we determine when the polynomials \\(F_n(x)=\\Phi_n(1+x+x^2+x^3)\\) are irreducible in \\({\\mathbb Q}[x]\\), where \\(\\Phi_n(x)\\) denotes the \\(n\\)-th cyclotomic polynomial, since in such case they become `big pieces' of \\(\\det(xI-A)\\). By using concepts and techniques from algebraic number theory, we prove that \\(F_n(x)\\) is always irreducible in \\({\\mathbb Q}[x]\\), unless \\(n=1,10\\). So, by combining tools from matrix and number theory we have been able to solve a problem of graph theory.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010813$DB138ECD-D8E9-4A34-AE49-CA96D8426E8C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010813$C7CF08FC-8DCD-4695-B839-7F78843B93B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010813$C6DF163D-9D82-4D2F-A89F-BF3BB20946E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"33596e09702254c39edd592e961d4cba7cfc6c47","datavalue":{"value":"11R18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010813$169E73E6-9854-47FE-B789-A5F7D33A476A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"70603fe1cf9b9e555eea652bd3537c36ea8cdbb8","datavalue":{"value":"5540992","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010813$09EAAC2F-D506-4820-B69B-688C836393A9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dcefda6ca3341c1a34f2f8f39b1c6def65f98057","datavalue":{"value":"almost Moore digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010813$A1A83978-BDD4-4DE8-AD67-449F0669A90F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"64287d55cb2f38dd0f11da246e78f83648de9a8a","datavalue":{"value":"characteristic polynomial","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010813$84E788F4-3024-4A2C-B3E1-05F1BA129A0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a3830b0910f1af2355bbc6ca39e7e832bd2f097b","datavalue":{"value":"cyclotomic polynomial","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010813$BDA37BDD-9109-4CD0-84E8-99BD3CD7C1CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7773c55b542f60995b68950a880d5c3d4a075990","datavalue":{"value":"per-","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010813$10843589-E048-4C80-A314-700569E4AA58","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f88990c0180cd81e2a8a245b33d8e59b317f6af7","datavalue":{"value":{"entity-type":"item","numeric-id":1953469,"id":"Q1953469"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010813$E2A58775-1D9B-4218-888D-A02CD862B3B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"349d6099b876bc2907c1602ca75ea0c7a1fcc5fd","datavalue":{"value":{"entity-type":"item","numeric-id":233541,"id":"Q233541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010813$90FDEE51-F609-4378-969C-8ECFC0D820AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4d6805eac657ad1cbd7233e4e0193de1a4baa2b8","datavalue":{"value":{"entity-type":"item","numeric-id":224971,"id":"Q224971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010813$8FA88511-F985-41E9-9E34-8D871F2CAFF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4d792b2ebc4c8684cbc738843a9ae7bb5c36f943","datavalue":{"value":{"entity-type":"item","numeric-id":592041,"id":"Q592041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010813$C7C35B2E-C3C3-48CB-A3E9-113BFE724CDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3a39e9faa1e73d060bc11ef620ca062d65da77f1","datavalue":{"value":{"entity-type":"item","numeric-id":1953470,"id":"Q1953470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010813$9CE76D15-40E3-4980-ADC9-7AB6323E9A06","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010813$67E72747-2A8C-448F-906E-3CF28DF202F5","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"e90e12c2079b4b8e8f4669036e4bf80524fbf48b","datavalue":{"value":"bafkreiglowsjxjyqlgs2jcsndejzlspl7zmvjc7owukmvr62ksx2dxh4ti","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010813$7C45654D-333F-4128-9888-E5B17649EB51","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f45b0ec7524bde5d03992036f3811ecd2f575e60","datavalue":{"value":{"entity-type":"item","numeric-id":3625865,"id":"Q3625865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef0464842ba88f4ad1bdbadbc6b90b39e9585cda","datavalue":{"value":{"amount":"+0.9255067706108092","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1010813$294ED63E-03E5-4F99-AFD6-D805E20915AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b5b0d73136fb1b1c72c75c0080ae09381477aa4f","datavalue":{"value":{"entity-type":"item","numeric-id":2441957,"id":"Q2441957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1c31f37aa8628dc6e87623c370ab3e8a986b6d0","datavalue":{"value":{"amount":"+0.8961278200149536","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1010813$92C38AA7-93EB-4B4D-BD0B-DAF801C41526","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7fb852cfb41ac2ffa134cdc4b45c70ea8137f244","datavalue":{"value":{"entity-type":"item","numeric-id":5937587,"id":"Q5937587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4c6860b2a4f5d62d2c4ad28190bf2a778a3b5bf","datavalue":{"value":{"amount":"+0.8740761280059814","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1010813$00953438-0CB2-444B-AB20-1CCF7E34F79C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f7265c78570ee9931b453d006ada47998ee6497","datavalue":{"value":{"entity-type":"item","numeric-id":4667792,"id":"Q4667792"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"70b00ce11520a7aac9f8853b974ac5be0187e765","datavalue":{"value":{"amount":"+0.8613068461418152","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1010813$B1971949-85E2-49A9-AE59-D929138B23FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf4454b592485b198e83c5e53fff1cdd235f0b61","datavalue":{"value":{"entity-type":"item","numeric-id":4552212,"id":"Q4552212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"35eb3c04de9642b5f4c73e01c71f7be697ff5743","datavalue":{"value":{"amount":"+0.8576924204826355","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1010813$B596D12B-6D34-4712-AE74-9EA55F21C859","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Nonexistence of almost Moore digraphs of diameter three","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Nonexistence_of_almost_Moore_digraphs_of_diameter_three"}}}}}