{"entities":{"Q865434":{"pageid":867282,"ns":120,"title":"Item:Q865434","lastrevid":64940982,"modified":"2026-04-11T23:14:50Z","type":"item","id":"Q865434","labels":{"en":{"language":"en","value":"Eigenvalues and extremal degrees of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5126040"}},"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":"Q865434$CE5160CD-1CFB-4381-99E8-0BF311244D56","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b0ac107b405c0ad539841eda4ed778771ef32528","datavalue":{"value":{"text":"Eigenvalues and extremal degrees of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q865434$E3521C68-1F7A-47B4-9A18-FADEEBEEBC71","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bfe5991e2a54a3573947c12f85879a1c68a6e165","datavalue":{"value":"1114.05062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q865434$FD5C1009-47D8-4F88-B17F-6706BBB484F8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7848ea27de0418470d5f2213ad091e7aab6bb866","datavalue":{"value":{"entity-type":"item","numeric-id":267200,"id":"Q267200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q865434$A3753B1E-6E25-4E8F-9AE5-BE48F8BE9CC3","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":"Q865434$10AA849B-94A5-4C28-80CF-12FEB0595B9F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a94159f4ab38d8d1a06ee095402a858d13e226d9","datavalue":{"value":{"time":"+2007-02-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":"Q865434$C62BD0D9-6E06-4BA0-AE56-6E0C0028BCEC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fa1f480d3b1ada4faa9e0bdda16c8e0c414d5d29","datavalue":{"value":"https://arxiv.org/abs/math/0605071","type":"string"},"datatype":"url"},"type":"statement","id":"Q865434$03A06BAF-74B3-4457-A4D9-74BD0F2B84A5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f9f9733e8b203eab64029ef29876a7004b08156b","datavalue":{"value":"Let \\(G\\) be a graph on \\(\\{1,2,\\dots,n\\},\\) \\(d_i\\) the degree of node \\(i\\) of \\(G,\\) \\(D(G)=\\text{diag}(d_1,\\dots, d_n),\\) \\(\\delta(G)=\\min_i d_i,\\) \\(\\Delta(G)=\\max_i d_i,\\) \\(A(G)\\) the adjacency matrix of \\(G,\\) \\(\\mu_1(G)\\geq \\cdots \\geq \\mu_n(G)\\) its eigenvalues, \\(L(G)=D(G)-A(G)\\) its Laplacian, and \\(\\lambda_1(G) \\leq \\cdots \\leq \\lambda_n(G)\\) the eigenvalues of \\(L(G)\\). Denote by \\(\\overline{G}\\) the complement of graph \\(G.\\) \\quad Using the variational characterization of the eigenvalues of Hermitian matrices it is shown that \\( \\delta(G)\\leq \\mu_k(G)+\\lambda_k(G) \\leq \\Delta(G),\\) implying \\(\\mu_k(G)+\\mu_{n-k+2}(\\overline{G}) \\geq \\delta(G)-\\Delta(G)-1, \\) \\(k=(1),2,\\dots,n.\\) In \\textit{F. R. K. Chung, R. L. Graham} and \\textit{R. M. Wilson} [Combinatorica 9, 345-362 (1989; Zbl 0715.05057)] an infinite family \\({\\mathcal G}\\) of graphs was defined to be quasi-random if, as \\(G\\) ranges over the graphs of order \\(n\\) of \\({\\mathcal G},\\) we have \\(\\mu_1(G)=2 e(G)/n+o(n),\\) \\(\\mu_2(G)=o(n),\\) and \\(\\mu_n(G)=o(n).\\) It is shown that \\(\\mu_n(G)+\\mu_n(\\overline{G})=o(n)\\) is necessary and sufficient for quasi-randomness of \\({\\mathcal G},\\) while either of the properties \\(\\lambda_n(G)+\\lambda_n(\\overline{G})=n+o(n)\\) or \\(\\lambda_2(G)+\\lambda_2(\\overline{G})=o(n)\\) is a sufficient condition for quasi-randomness.","type":"string"},"datatype":"string"},"type":"statement","id":"Q865434$D00A68A8-6830-4454-A8D7-210C487AD4BD","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4cb749bb0545117c5a39ee1b861da533345043d8","datavalue":{"value":{"entity-type":"item","numeric-id":587686,"id":"Q587686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q865434$078F05C9-06A4-480C-BBBA-FF1FB4A22DAF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q865434$4340B4ED-A4D9-4AE2-A0CE-E88D0203F679","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c21603f2a2de72aea22ccf7830ccc0f1291fe832","datavalue":{"value":"15A42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q865434$D32834AD-2EF7-4C03-9CDF-5E41189FFCA5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"163fa4266241375156c3f4eb8a19d49b1e46e15e","datavalue":{"value":"5126040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q865434$51750BFA-642D-4C1E-B33C-B6356672033C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b07eec98772a8c24fb556e9a027cbd0c75ec516b","datavalue":{"value":"Laplacian","type":"string"},"datatype":"string"},"type":"statement","id":"Q865434$AF73B92A-6B5D-48DF-9451-E98DD5C10E81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d041d14c0c5b7ca03f8d982b260f7ab8ca2e422d","datavalue":{"value":"variational characterization","type":"string"},"datatype":"string"},"type":"statement","id":"Q865434$987D68A3-8EC9-40AD-911F-0C488668B699","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"de26603f4dc2e6024b4c6aaf85b17f7bd5bb8081","datavalue":{"value":"Courant-Fischer theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q865434$046F85D8-AFE1-4C20-A424-FC4D517415E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a155435ab6bf15940a049b00e9d3ea7e736d8a27","datavalue":{"value":"quasi-random graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q865434$DD6D041B-9C54-49A0-8421-71EA3A13FA5F","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":"Q865434$139DA2F7-2377-4F58-ADB7-8734DF745485","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7ab525ad3937df9f30c67b967789848dc63d09b4","datavalue":{"value":"W2070525487","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q865434$3DF1DAEA-7E4F-4D4F-9B00-8ABF50C875DD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"09d12695d4a3731e56edebe1f68edf8feccbdbd8","datavalue":{"value":{"entity-type":"item","numeric-id":4398864,"id":"Q4398864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q865434$D1B32F77-4C72-48B6-93D4-3188C10E6170","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1312a34b6a8327be1e35714f2f181547c026a788","datavalue":{"value":{"entity-type":"item","numeric-id":3907599,"id":"Q3907599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q865434$9EAF0262-366D-4E9E-8486-92EB02939989","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f791412b285553b13dabedab6f9c7458ca857cd","datavalue":{"value":{"entity-type":"item","numeric-id":5895286,"id":"Q5895286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q865434$4525C19A-5A4C-46A0-B43A-D734FFF81F68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86e00b9847c27f6a3f4376049250bc282a2a9d8b","datavalue":{"value":{"entity-type":"item","numeric-id":4296516,"id":"Q4296516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q865434$83AA0624-5819-4306-A48C-A7A141F6E436","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":"Q865434$DD5A9E34-3FED-496F-BF00-6F9C30AB7BBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4717b4e089aa25bc4a1766c06a6060fccbca24d1","datavalue":{"value":{"entity-type":"item","numeric-id":819785,"id":"Q819785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q865434$699605C2-295F-4B53-BEA6-FB9F372A4A52","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6754a6b5da823ceeab95bc6e3f191699c62847f1","datavalue":{"value":"10.1016/J.LAA.2006.06.013","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q865434$EC5BE6C3-D7C1-4482-ACED-F3C0A2D58C76","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"76b1ed265b394439243eff297e1e17a898625b8d","datavalue":{"value":{"entity-type":"item","numeric-id":4955029,"id":"Q4955029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"342e12a5cb159c6969425e4f2479a9221f198be4","datavalue":{"value":{"amount":"+0.7631394","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q865434$3792D704-ED63-4C92-BBD7-6EDC5E51A90F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cb62db891996aa3e10a3342cabcb607a2a3f1f78","datavalue":{"value":{"entity-type":"item","numeric-id":1848147,"id":"Q1848147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dcf7b389122429c0785fb0538b30118dca674bb7","datavalue":{"value":{"amount":"+0.7609307","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q865434$73D899E4-C014-4F2B-A8FA-BF8BC3922F49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1727543623c25b481ded8f148d9b10a72bd83acd","datavalue":{"value":{"entity-type":"item","numeric-id":5704388,"id":"Q5704388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc1548d95331321ffa8b02dbdfdd7bfde098f1e5","datavalue":{"value":{"amount":"+0.7561819","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q865434$3059C087-2390-4A0A-93D3-8C89D4BB577C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"44b4bc99df301f7781eb6399821df874d82fa613","datavalue":{"value":{"entity-type":"item","numeric-id":532131,"id":"Q532131"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c4cd51ea9833e6650125d5ff9c809b7cc358f04","datavalue":{"value":{"amount":"+0.754673","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q865434$86921C7E-6438-466A-83D4-FCF6D7340188","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7f18c1adb9d8ccf0bf1d4579947923390dc63f6b","datavalue":{"value":{"entity-type":"item","numeric-id":3144334,"id":"Q3144334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44e184e5e3a17579ff6c92a65a0df5cb017ab69e","datavalue":{"value":{"amount":"+0.75310796","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q865434$60C46DA5-042D-4589-9D75-90FCB0D1EC51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bcff549d4a25f225440a1e75e904c15d8993e8d7","datavalue":{"value":{"entity-type":"item","numeric-id":5477817,"id":"Q5477817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f0a0a480083521597d34e09432f1a6bbed4aac0","datavalue":{"value":{"amount":"+0.74920493","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q865434$519E112E-12DF-4C42-A0D8-F0AD05D8A914","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"abe9d26c33f49de52a3c6e7415f38bff0603cde3","datavalue":{"value":{"entity-type":"item","numeric-id":402587,"id":"Q402587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a8f063cb74e5df5821996a0d419db99f93b0e8d0","datavalue":{"value":{"amount":"+0.74581146","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q865434$0A76D7A6-721D-4189-872D-B589E1916D63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"484068c0e5b292e697310261e5bd9c72ded0131e","datavalue":{"value":{"entity-type":"item","numeric-id":3571168,"id":"Q3571168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f87128bb6d0aefcbb4771657275ea6fd95ef0b54","datavalue":{"value":{"amount":"+0.7431958","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q865434$445370AB-B1A3-41C1-B235-4CFC95019FCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f726a07c443bea480cb42568a1042dc03a27981","datavalue":{"value":{"entity-type":"item","numeric-id":4471155,"id":"Q4471155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d254c460398c94ed6695c4e71cfeb892a45953b5","datavalue":{"value":{"amount":"+0.7430298","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q865434$BBEA4960-92FB-4242-A1FC-72236ADDBAA0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Eigenvalues and extremal degrees of graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Eigenvalues_and_extremal_degrees_of_graphs"}}}}}