{"entities":{"Q612923":{"pageid":614699,"ns":120,"title":"Item:Q612923","lastrevid":63050136,"modified":"2026-04-11T10:05:27Z","type":"item","id":"Q612923","labels":{"en":{"language":"en","value":"On graphs with cyclic defect or excess"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5827392"}},"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":"Q612923$55F341BF-D6E6-41AD-8EFF-3E2F2D2C5ADB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8eaa21e8e7ca397ebbcc0b82132e8bf6150409b2","datavalue":{"value":{"text":"On graphs with cyclic defect or excess","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q612923$070F46EB-78EB-4C00-A85C-941C3078B9ED","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5d5cad1849566b3d9efa06fab6cd274975e4ed75","datavalue":{"value":"1204.05043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q612923$EB18793C-7DFD-400C-873A-29740F0527EC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"989a9701d150170acf3a0218ce39685294f0c3e7","datavalue":{"value":{"entity-type":"item","numeric-id":195165,"id":"Q195165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q612923$3BCEEF11-691F-45CC-B1F7-20649990902B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d1068018fcd1da3c073d343302ccd554704769e8","datavalue":{"value":{"entity-type":"item","numeric-id":273164,"id":"Q273164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q612923$4D075FBD-B167-4D56-88E7-AD3AA726648D","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":"Q612923$38BE18A1-0B2A-4F3A-8AA1-F3EAC535B6E6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63d0db48794e6800d8c22359b1f6c876c0e4d309","datavalue":{"value":{"time":"+2010-12-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q612923$116A6845-B089-4756-91E8-EF61E9FCDA67","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"00adfabc4869bfd0327705e7fb75fd5afc7cbc1f","datavalue":{"value":"https://arxiv.org/abs/1010.5841","type":"string"},"datatype":"url"},"type":"statement","id":"Q612923$3B3AC56A-A357-4F1D-BEFC-206F6D6EDAEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"4d47e240751bfe78c02ce85baa33ef2fcfb6edd2","datavalue":{"value":"https://eudml.org/doc/226730","type":"string"},"datatype":"url"},"type":"statement","id":"Q612923$89753DAD-A184-4508-BD7E-3D871798723B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"fd9d8f73b12bf880f52ffb9d64bff54a17b96b4f","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_17/Abstracts/v17i1r143.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q612923$A32E0867-7376-4F24-9300-B7322F96A278","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1f64df2ad8c360857ef2fc6c58266ca96686fec6","datavalue":{"value":"Summary: The Moore bound constitutes both an upper bound on the order of a graph of maximum degree \\(d\\) and diameter \\(D=k\\) and a lower bound on the order of a graph of minimum degree d and odd girth \\(g=2k+1\\). Graphs missing or exceeding the Moore bound by \\(\\varepsilon\\) are called graphs with defect or excess \\(\\varepsilon\\), respectively.  While Moore graphs (graphs with \\(\\varepsilon=0\\)) and graphs with defect or excess 1 have been characterized almost completely, graphs with defect or excess 2 represent a wide unexplored area.  Graphs with defect (excess) 2 satisfy the equation \\(G_{d,k}(A)= J_n+B\\) (\\(G_{d,k}(A)= J_n-B\\)), where \\(A\\) denotes the adjacency matrix of the graph in question, \\(n\\) its order, \\(J_n\\) the \\(n\\times n\\) matrix whose entries are all 1's, \\(B\\) the adjacency matrix of a union of vertex-disjoint cycles, and \\(G_{d,k}(x)\\) a polynomial with integer coefficients such that the matrix \\(G_{d,k}(A)\\) gives the number of paths of length at most \\(k\\) joining each pair of vertices in the graph. In particular, if \\(B\\) is the adjacency matrix of a cycle of order \\(n\\) we call the corresponding graphs graphs with cyclic defect or excess; these graphs are the subject of our attention in this paper.  We prove the non-existence of infinitely many such graphs. As the highlight of the paper we provide the asymptotic upper bound of \\(O(\\frac{64}{3}d^{3/2})\\) for the number of graphs of odd degree \\(d\\geq 3\\) and cyclic defect or excess. This bound is in fact quite generous, and as a way of illustration, we show the non-existence of some families of graphs of odd degree \\(d\\geq 3\\) and cyclic defect or excess.  Actually, we conjecture that, apart from the M\u00f6bius ladder on 8 vertices, no non-trivial graph of any degree \\(\\geq 3\\) and cyclic defect or excess exists.","type":"string"},"datatype":"string"},"type":"statement","id":"Q612923$55F38B61-C167-4700-ACC9-CF48DB9FFF7A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q612923$2A5E4099-18E3-4168-ADE9-21419B547A43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q612923$3D6DD300-95BC-4B07-9728-EE35E85FFC63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q612923$F0099BFE-C66B-42CD-BE5C-52F0130F0F12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q612923$CCC726AF-ECC2-4C9C-83D5-8DAB28DB00E9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"38ce95dc2bf6cc93ea823779a0beef53db8b0c32","datavalue":{"value":"5827392","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q612923$D95A70E8-12A5-4A49-ACA5-97680FBC9297","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e4a93c7d90ee4b4e7032e71c725910c3dd97a9a2","datavalue":{"value":"Moore bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q612923$83339824-D481-4B1E-82BA-3EE0530B0804","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"80cdfac862b6592e59205312f05453a561b55f89","datavalue":{"value":"Moore graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q612923$4D34CD9C-EBFC-4A23-815F-5C3F6FF6C73E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"98f127d45a980854c5f039296a37b2b445f211d1","datavalue":{"value":"defect","type":"string"},"datatype":"string"},"type":"statement","id":"Q612923$E06955F5-972E-452A-80EB-B231D95FA883","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bbaa3918192c98d9e46028c744bcb5304cb5e058","datavalue":{"value":"excess","type":"string"},"datatype":"string"},"type":"statement","id":"Q612923$5B99A7E6-49DA-4DF0-AAD9-7826451F72B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fe0b4e9b6e968b15755e5c9414e4e9786b0b28b1","datavalue":{"value":"Chebyshev polynomial of the second kind","type":"string"},"datatype":"string"},"type":"statement","id":"Q612923$B6BC6871-04DF-4ADF-AB94-A497EAEE621C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d5996ee23a41df6968b4818a1e1adffe2b6efb9f","datavalue":{"value":"cyclic defect","type":"string"},"datatype":"string"},"type":"statement","id":"Q612923$52B8B695-1BA0-4606-8F53-FB11D8907807","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"878302d0bf6bf0065f201aa3138befd16c1abd53","datavalue":{"value":"cyclic excess","type":"string"},"datatype":"string"},"type":"statement","id":"Q612923$C15A9258-BDE6-4C8D-A724-4E7FDC207803","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"49b5234b6c5544dc8d193425e33d7d21358eb398","datavalue":{"value":"Pell equation","type":"string"},"datatype":"string"},"type":"statement","id":"Q612923$AB6DD8AF-5472-4FB1-AD0F-5D24CEEAE187","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":"Q612923$629F8E9A-3EC6-46FA-9B05-9B85950A8BE8","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"e9be89584d13cd3a2b22b3cc732a0d53bb2f5f4e","datavalue":{"value":"bafkreichgydf7bv6xasrc3t63wygrbgmkcucgb4hvdaam27vcydctghkhm","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q612923$B6FED3D2-8D0D-4F9F-A4AA-A4D7ACBBC641","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c519d663d6e2c9586b9036a55387d2c3a7877d7","datavalue":{"value":{"entity-type":"item","numeric-id":540060,"id":"Q540060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"efae0e22c67cb5a9c4fa6e3a0de9d888ecbaf2c5","datavalue":{"value":{"amount":"+0.8878622055053711","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":"Q612923$F669EE5B-FACB-482A-B6F4-CA67C7ECC842","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f9f117162ce4a4d306ebde274d95931b9e68a96","datavalue":{"value":{"entity-type":"item","numeric-id":476306,"id":"Q476306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"07507c852ff78152b26ab2854c2ad430f38290aa","datavalue":{"value":{"amount":"+0.8795518279075623","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":"Q612923$E4480672-EBAC-42B0-B6A0-ABAD615817FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bd160bdc8977a8521a7f0ac44af4b3c14ccff144","datavalue":{"value":{"entity-type":"item","numeric-id":2275941,"id":"Q2275941"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c18eb485a9426fc8a84abeb994f3494022eeacf9","datavalue":{"value":{"amount":"+0.8640615344047546","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":"Q612923$546DED4D-D4C0-4387-9923-80FD5DF92E41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a211c74110c9aab0bb158d8dea121a768e52813c","datavalue":{"value":{"entity-type":"item","numeric-id":3035326,"id":"Q3035326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f79b398bde49ef0968bb17f9ee31b8353f0f5abb","datavalue":{"value":{"amount":"+0.8501604199409485","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":"Q612923$AC767686-2F0C-4AF9-A77A-02655852C4DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e5f2e3f3415c3a0be65b401b6e0bb080380f419b","datavalue":{"value":{"entity-type":"item","numeric-id":521356,"id":"Q521356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b307d1b0530d9d097f44884817ff3f074de4e4c6","datavalue":{"value":{"amount":"+0.8203224539756775","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":"Q612923$4E3E6BAD-90BF-4B2F-8C44-AA2B4D181842","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On graphs with cyclic defect or excess","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_graphs_with_cyclic_defect_or_excess"}}}}}