{"entities":{"Q5946174":{"pageid":8122976,"ns":120,"title":"Item:Q5946174","lastrevid":47685376,"modified":"2026-01-02T10:33:48Z","type":"item","id":"Q5946174","labels":{"en":{"language":"en","value":"The spread of the spectrum of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1658464"}},"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":"Q5946174$146B282A-47FD-4736-B4BA-6BCC0C7DE5D0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d1cba9a273e5551a172d35058b2efb6b8fb2bcf8","datavalue":{"value":{"text":"The spread of the spectrum of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5946174$5879B351-D42D-4CBC-B32D-B658A3487508","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b2e488431271429e2afabe4f374daff0df4655c5","datavalue":{"value":"0978.05049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946174$E30325A6-B1E0-43FD-A09B-BA06930BCC45","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ffd32861d14d66510f16a972cb92d31c6bb0b998","datavalue":{"value":"10.1016/S0024-3795(00)00086-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946174$B7AF8B92-DE0A-4279-86E1-BF942CE8EF09","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e5cd4d86fa4cb2018df87083fc560d1b76dea77e","datavalue":{"value":{"entity-type":"item","numeric-id":209029,"id":"Q209029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946174$133D791E-9DE7-4840-8157-564EB4ED2DDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"61ba8dd6a707b3526ec29b446d6dd973c982f563","datavalue":{"value":{"entity-type":"item","numeric-id":209030,"id":"Q209030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946174$7DF52706-2924-4168-8E63-C820BC5FBC8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"eca2b6671a8654cb19241223a6a4d5545355bf0a","datavalue":{"value":{"entity-type":"item","numeric-id":233191,"id":"Q233191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946174$B83305D0-B359-4CC5-B10A-D5C290017E9A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"8de031de05325b44570d0c47c3ec8813873d565c","datavalue":{"value":{"entity-type":"item","numeric-id":92813,"id":"Q92813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946174$74A1683B-BEE5-4BEF-9AD6-3FBAB6D60AE3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b10c0a8ab114f307ae85cd2e8ca5f34e82e75864","datavalue":{"value":{"time":"+2002-01-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5946174$A3BF74BF-D9A8-43AA-86A4-A8545627BB2A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"94626be276206b45b57e94a7e29516fb1870dd91","datavalue":{"value":{"entity-type":"item","numeric-id":190550,"id":"Q190550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946174$6D67C508-60B5-41C1-9A51-545A214EC573","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946174$96433730-FD66-4AA9-A1B2-EB2057BC678E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c21603f2a2de72aea22ccf7830ccc0f1291fe832","datavalue":{"value":"15A42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946174$BC8777AF-EA58-4E82-8A64-705A71DD9345","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06299a38dab9dd1c28e96fe2a7f8cac0943d746","datavalue":{"value":"15B36","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946174$A9A2BB6B-B893-4F35-8652-EEBBE22CC118","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"580d0adfc849b9d632e57e8232291e5380af2ce3","datavalue":{"value":"1658464","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5946174$D1B3A90A-1EDD-4B2A-88F5-C17CC714D5E5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"de6a0346430345c2d984a9b2cd875ef0b5a72dc9","datavalue":{"value":"spread of spectrum","type":"string"},"datatype":"string"},"type":"statement","id":"Q5946174$77D5CAFF-6859-4A54-A577-1082E134D918","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4b52d130ed7cb8e0a4ecef7199825eba7d5ebeb","datavalue":{"value":"adjacency matrix of graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q5946174$EC051628-BE0E-4E6E-B142-6CF13FF9AF4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5a0b1f917cce6aa67d2c75958419dd55449897f4","datavalue":{"value":"eigenvalues of graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q5946174$E007318A-47AC-4A80-B53C-385BCE843FF4","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":"Q5946174$DF4C8A8E-033B-4AED-9A78-D66C78B87999","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3faae139d435925c6128cfec710d1b5951d710c0","datavalue":{"value":{"entity-type":"item","numeric-id":1123902,"id":"Q1123902"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946174$4A20519B-A10E-4F04-9BA1-C7FE990CA0AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946174$8E8E5E18-5E6F-4C46-B9FB-38309486C9A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14dfcc44180e410b3262b7ccaf567bcced1afc2a","datavalue":{"value":{"entity-type":"item","numeric-id":4326384,"id":"Q4326384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946174$5505F7AA-1F4E-43FC-9F8B-AAEA4A9DE9DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"75db644480007bb48925df62c31e03f7e79b9197","datavalue":{"value":{"entity-type":"item","numeric-id":768643,"id":"Q768643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946174$8B3B0EA1-6D70-48EF-BF11-A2CA00477EE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef8f1df0d7471e6cae1cb989718adf133576fabb","datavalue":{"value":{"entity-type":"item","numeric-id":2785496,"id":"Q2785496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946174$E7AD3768-E0CF-49FF-BB48-9088A863D7FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1726920e7fec7d821c12caa63e36b825a5dd0776","datavalue":{"value":{"entity-type":"item","numeric-id":3866128,"id":"Q3866128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946174$DEA6CD82-6DAD-43BF-A650-EA766ACB4A20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe3f076d6c347421c94147e0bddcaa6a59d55251","datavalue":{"value":{"entity-type":"item","numeric-id":3697157,"id":"Q3697157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946174$C2C4464F-85F5-4485-BCDB-5D7B5CA22698","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"21d44496fbe787bf82b89ee7d42804c01ea47e46","datavalue":{"value":{"entity-type":"item","numeric-id":1066236,"id":"Q1066236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946174$1B29E787-78B3-49BB-810D-CF68901A86AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4e5dabdd436c9605d7b2220be8ac974303b678a","datavalue":{"value":{"entity-type":"item","numeric-id":1319985,"id":"Q1319985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946174$35DEA36B-FB49-4ADE-A0C0-4F996A4F90B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f5317c5ed9502d7a7d623f23ef6fd8f2395ceb8","datavalue":{"value":{"entity-type":"item","numeric-id":4853923,"id":"Q4853923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946174$E9A66949-BD99-488C-B2CD-2A1894B2E2FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43a84da1c9d7293e5adf5a1df83de63dbaf98bd0","datavalue":{"value":{"entity-type":"item","numeric-id":3236680,"id":"Q3236680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946174$317DC689-F38D-46AD-9D37-6628E1676A3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"47c54de38c101cab54ea9568ce5b0e400e52dc14","datavalue":{"value":{"entity-type":"item","numeric-id":4322505,"id":"Q4322505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946174$6EDD84F1-E4AD-43E5-AC85-FB7ED3FE5424","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"923ad3d027caf22daf3119d0b2b57403c1e00c62","datavalue":{"value":{"entity-type":"item","numeric-id":3216691,"id":"Q3216691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946174$31EEC38B-AE08-4A39-8DC1-ACC606EB3294","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49cd050affb1e4b71422903e354634c4f12afb9c","datavalue":{"value":{"entity-type":"item","numeric-id":4015403,"id":"Q4015403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5946174$BCD6636F-3867-4487-9CD3-F456AB2B49A7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b69fc6d668fff9495c5c1cad561c84235241dc76","datavalue":{"value":"Let \\(A=A(G)\\) be the adjacency matrix of a simple graph \\(G\\) with \\(n\\) vertices and \\(e\\) edges, and let \\(\\lambda_1\\geq\\lambda_2\\geq\\dots\\geq\\lambda_n\\) be its eigenvalues. The spread \\(s(G)\\) is the difference \\(\\lambda_1-\\lambda_n\\). The authors consider the maximum spread of graphs under various constraints. NEWLINENEWLINENEWLINELet \\(G_0\\) denote the subgraph of \\(G\\) obtained by deleting the isolated vertices of \\(G\\). The main result is the following Theorem 2.3: Let \\(G\\) be a graph with \\(n\\) vertices, \\(e\\) edges, and precisely \\(k\\) negative eigenvalues, \\(1\\leq k\\leq n-1\\). Then NEWLINE\\[NEWLINE s(G) \\leq \\frac{k+1}k \\lambda_1 + \\sqrt{ 2e \\frac{k-1}k - \\frac{k^2-1}{k^2} \\lambda_1^2}.NEWLINE\\]NEWLINE Equality holds if and only if \\(G_0\\) is a complete \\((k+1)\\)-partite graph and, when \\(k\\geq 3\\), the \\(k\\) smallest parts of \\(G_0\\) all have equal size. The authors also find a number of other upper bounds on the spread of a graph with constant number of edges under some additional conditions. NEWLINENEWLINENEWLINENext, the authors consider a conjecture about the maximum spread amongst the graphs with \\(n\\) vertices. The join of two vertex disjoint graphs \\(G_1\\) and \\(G_2\\) is the graph \\(G_1\\vee G_2\\) obtained from their union by including all edges between the vertices in \\(G_1\\) and the vertices in \\(G_2\\). For integers \\(1\\leq k\\leq n-1\\), let \\(G(n,k)=K_k\\vee \\overline K_{n-k}\\), the join of \\(K_k\\), the complete graph with \\(k\\) vertices, with the \\(n-k\\) independent vertices of \\(\\overline K_{n-k}\\), the complement of \\(K_{n-k}\\). NEWLINENEWLINENEWLINEThe graph \\(G(n,\\lceil 2n/3\\rceil)\\) has the spread \\(s(G(n,\\lceil 2n/3\\rceil)) = \\lceil (4/3)(n^2-n+1)\\rceil^{1/2}\\) and so \\((1/\\sqrt 3)(2n-1) < s(G(n,\\lceil 2n/3\\rceil)) < (1/\\sqrt 3)(2n-1) + {\\sqrt 3}/(4n-2)\\) (or \\(s(G(n,\\lceil 2n/3\\rceil)) \\approx 1.1547n-0.5774\\)). The authors conjecture that the maximum spread \\(s(n)\\) amongst the graphs with \\(n\\) vertices is attained only by \\(G(n,\\lceil 2n/3\\rceil)\\). This conjecture has been checked by computer for graphs with at most \\(9\\) vertices and it is supported by the upper bound \\(s(n)\\leq (1/2)(1+\\sqrt 2)n\\) (or \\(s(n) < 1.2072n\\)) the authors prove. NEWLINENEWLINENEWLINEAmong other results the authors prove that a triangle-free graph with \\(n\\) vertices, \\(e\\) edges, and maximum vertex degree \\(k\\) has a spread at least \\((2e/n)+\\sqrt k\\). This minimum spread is attained by Johnson graphs \\(J(2r,r)\\), for example.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5946174$4F2211CA-E2DF-4615-ACB3-C7F15B202250","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"68b4a09272d54950999101b45233e15dcfc9db1b","datavalue":{"value":{"entity-type":"item","numeric-id":3216691,"id":"Q3216691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d5933251556e01c6414f5b48c4674b9f3b193a4","datavalue":{"value":{"amount":"+0.8554390668869019","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":"Q5946174$499320ED-1D7C-4FA5-BE3C-45F4BA81A70A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"30d7809b8f282cc829ff64dd975d66a67cdb5180","datavalue":{"value":{"entity-type":"item","numeric-id":1043620,"id":"Q1043620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c5ff7607e5f5949995657acb907320db51eee7b","datavalue":{"value":{"amount":"+0.8499768972396851","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":"Q5946174$DE34F4DA-28A1-4375-AB13-C76E7FEC1867","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7af81e2b4515d8e00671d02ffc2ada9aebd9a2cd","datavalue":{"value":{"entity-type":"item","numeric-id":3325759,"id":"Q3325759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ece6414e81b2d79fe4a6d6865ff3947fd390801","datavalue":{"value":{"amount":"+0.8446529507637024","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":"Q5946174$62C4170C-8AEB-4A9D-941A-7E337EF407F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2059c7df506e1f5d04bdbfa824b1470a211a963c","datavalue":{"value":{"entity-type":"item","numeric-id":2125585,"id":"Q2125585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"702bffd35a1051e590d7f369dce6dac5550641d5","datavalue":{"value":{"amount":"+0.8381513953208923","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":"Q5946174$CFB2B741-651E-4555-8DD3-AEA3D4E7430C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"374093dc79da0408075d8e11d5f11d245544e326","datavalue":{"value":{"entity-type":"item","numeric-id":962122,"id":"Q962122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d83b322331b5423fa6e6baeafaefe958e848d2c3","datavalue":{"value":{"amount":"+0.8341461420059204","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":"Q5946174$8849ACE3-2061-411C-B47B-CD20C5E483F4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5946174","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5946174"}}}}}