{"entities":{"Q1209408":{"pageid":1220157,"ns":120,"title":"Item:Q1209408","lastrevid":69894558,"modified":"2026-04-13T11:03:21Z","type":"item","id":"Q1209408","labels":{"en":{"language":"en","value":"Eigenvalues and separation in graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 167840"}},"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":"Q1209408$8F6E9FB4-65BD-45C0-B4D6-D73E826F03F1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"53c6299ece9d91e9c3effd07751faaca0feb2064","datavalue":{"value":{"text":"Eigenvalues and separation in graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1209408$5354EE5A-9E43-474F-ADF2-4C1F09162905","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7013583182ae3a3daec1690e43c0d53d34816893","datavalue":{"value":"0771.05062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209408$A99723DB-D9CC-4E45-8F8B-C73A47BEDEE8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c267e2145bbfa9e0567b390ece949b47080d9345","datavalue":{"value":"10.1016/0024-3795(93)90030-R","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209408$5B905F93-3899-4C7A-8E94-358A8249EAD4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"caac39c0f4244a2c9247d944fa0ac77ebba15c59","datavalue":{"value":{"entity-type":"item","numeric-id":740974,"id":"Q740974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209408$4FDBE017-B70B-4054-8DDE-BCE65F46A32B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8a67ac3d4ff1136089c36b4553e3910b2bc1d5d5","datavalue":{"value":{"entity-type":"item","numeric-id":409452,"id":"Q409452"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209408$329780CA-366B-4947-AD3F-963B5769C77C","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":"Q1209408$3A68B1D3-8011-400B-B86C-D07949B5FCF8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1772b6c81a5108c06854e0de4518fb90e5a6ebdc","datavalue":{"value":{"time":"+1993-05-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":"Q1209408$7FF15FF2-83FA-409B-96B0-F9A09437BF0E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c7d5f1a99802ffaa1d0dec76e23bd80af5c246a5","datavalue":{"value":"If \\(f:V(G)\\to V(H)\\) is a one-to-one map of graphs \\(G\\) and \\(H\\), where \\(| G|\\leq| H|\\), then \\(\\text{sep}(G,H)=\\max\\min\\{\\text{dist}_ H(f(x),f(y)):xy\\in E(G)\\}\\) where the maximum is over all such functions \\(f\\). The study of \\(\\text{sep}(G,H)\\) is an extension of problems arising in coding theory, for example. The authors apply a method involving the Kronecker product to obtain the eigenvalues of powers of the \\(n\\)-cube \\(Q(n)\\) and of powers of the discrete torus \\(C_ n\\times C_ n\\). They obtain, among other things, functions \\(s(k,p)\\) and \\(t(k,p)\\) such that if \\(G\\) is a graph with \\(p\\) points and \\(q\\) edges, where \\(q>s(k,p)\\) or \\(q>t(k,p)\\), then \\(\\text{sep}(G,Q(n))\\leq k\\) or \\(\\text{sep}(G,C_ n\\times C_ n)\\leq k\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209408$148D6AD4-80C9-4AB7-83EC-DF4295973754","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209408$D2798386-3358-4625-8D61-A127BA952F96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209408$73F5D306-1D9F-4C9C-84F9-A5223811B87B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d0dca1d92db286473871f18f5bb90771574e5d70","datavalue":{"value":"167840","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209408$4E3C9B6B-DE97-464D-B1E5-2D3E06A9DD78","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b80c99afc4950f85b79a2fe3707eb2e870b9567f","datavalue":{"value":"separation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209408$3DDB68B3-3E9F-48D1-847B-AB97ED790C5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fe57727e16c499bf1c030db1376bdd324c3c24ad","datavalue":{"value":"edge-isoperimetric problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209408$13A5BF3B-37FF-41B5-BC74-4C710547F888","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3534ce13a0a2607997f0d545d35641025b09aa48","datavalue":{"value":"map","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209408$F386347F-B99D-40F2-9175-C8B2FF0BF6AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"811604a75801fcd709c8667f83ea26944825b8d2","datavalue":{"value":"eigenvalues","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209408$43F3C35E-F9EF-4A4A-B576-18EBC7E5C895","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"acabea84bcd2e14b7775489c565a376e01536ff2","datavalue":{"value":"discrete torus","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209408$A36708AF-66F0-4581-9C38-8F1B8948693A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"478bb984958f47159570b1788ede69358a5f4226","datavalue":{"value":{"entity-type":"item","numeric-id":656146,"id":"Q656146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209408$AB578956-8580-4B50-A1D0-C65FB1742A2E","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":"Q1209408$EA26C9FE-5607-473F-8889-41E4EED1EC52","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0df8c16fb6d4d3c861f57e0569695f268c7efadd","datavalue":{"value":{"entity-type":"item","numeric-id":800384,"id":"Q800384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209408$EA81BD11-CC8C-47A3-BA67-2B192DCB8E6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db7794fd53d223d371ff96304864a2e06009ce4b","datavalue":{"value":{"entity-type":"item","numeric-id":4173399,"id":"Q4173399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209408$5CD5A324-06C8-4261-A1F3-762B633A62CD","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":"Q1209408$E43AD649-589B-4398-B392-11A86B137849","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53147db84dbd97cf64fd607dd5242d62d26abbad","datavalue":{"value":{"entity-type":"item","numeric-id":1220937,"id":"Q1220937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209408$3D15A267-D522-4FEC-87E5-6B7CF099F29D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9dcac5e839e9527350c7fa866f67e9d0574580e1","datavalue":{"value":{"entity-type":"item","numeric-id":3833885,"id":"Q3833885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209408$9381D981-51BE-4083-AA2A-161401D7934E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"413947626d43080a43a6bd864e53251986a23933","datavalue":{"value":{"entity-type":"item","numeric-id":4866083,"id":"Q4866083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca5b7571b7201cbe22914b5e0ccb45ace05ad73a","datavalue":{"value":{"amount":"+0.9558615","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":"Q1209408$F8C9C821-2A82-47DB-BB07-8292E46F935F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e8c3f422d6b176037e5b3acda786733ae3179d0","datavalue":{"value":{"entity-type":"item","numeric-id":4661928,"id":"Q4661928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca5b7571b7201cbe22914b5e0ccb45ace05ad73a","datavalue":{"value":{"amount":"+0.9558615","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":"Q1209408$24C2A25F-B17E-4CA3-B464-95A866942310","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"76844079a6c05274237e2418c30782fa0e9db1be","datavalue":{"value":{"entity-type":"item","numeric-id":685669,"id":"Q685669"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"05e0a8183a55d730d8af8c888e84b9b4510543e8","datavalue":{"value":{"amount":"+0.94322526","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":"Q1209408$01765CD1-D96D-49C3-BEFC-E22122B273CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d3251e5b2301cf557637eff0db1cbc1e9d878b3","datavalue":{"value":{"entity-type":"item","numeric-id":3435575,"id":"Q3435575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b6e813c4953a8d2764320900f6de6f0d6b57b45","datavalue":{"value":{"amount":"+0.9410607","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":"Q1209408$F39EA0F1-825F-40A4-AEC6-7794208A6244","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"46b02081127024e5705691bd854382b32347c1c0","datavalue":{"value":{"entity-type":"item","numeric-id":4603773,"id":"Q4603773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c388e10b59a0d22b655e704e7a0f42ea05d66afa","datavalue":{"value":{"amount":"+0.94106066","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":"Q1209408$CEC55AF0-6B37-48D4-9E52-463FD0F03A8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f787fa55bd85ffc8a29cf81c8df0b4a07178a03e","datavalue":{"value":{"entity-type":"item","numeric-id":4886769,"id":"Q4886769"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"14ec4d4c1d71c4ceff22de95994a0fcf38c38eb0","datavalue":{"value":{"amount":"+0.93680656","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":"Q1209408$96342859-80BB-4974-BFC8-14F5BDC2A5FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b4591f177072cdb1acccf32349a93e400151f5b","datavalue":{"value":{"entity-type":"item","numeric-id":819785,"id":"Q819785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b959bf86ff8f880fd4f42c16130ed898486c8777","datavalue":{"value":{"amount":"+0.93547297","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":"Q1209408$2B38E768-1820-46A3-9F58-9B489CE2B01C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e621bb4a732d0bb65e27a0f6cc39485bc25e057f","datavalue":{"value":{"entity-type":"item","numeric-id":4853930,"id":"Q4853930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a770c7ad40e6b44b2e1d7be3d11f4b2c7fbe154d","datavalue":{"value":{"amount":"+0.9351422","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":"Q1209408$C2DCA076-C7C6-4A43-B2E9-AC92E1786509","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"734e23d3853a399d8e436408fd1f110b2fc9fa46","datavalue":{"value":{"entity-type":"item","numeric-id":2918383,"id":"Q2918383"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39d60b1050a6bf071c0ba04e530e966d82de32d8","datavalue":{"value":{"amount":"+0.9344625","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":"Q1209408$D9EE0FE2-1F55-407F-B854-F2757531D7C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6fabbfbe58dc147691cf4cc4f70352ebb6f5745b","datavalue":{"value":{"entity-type":"item","numeric-id":2272481,"id":"Q2272481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"865f64dcd05851c66efe8106cb307f0db3df2925","datavalue":{"value":{"amount":"+0.93366504","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":"Q1209408$E1E123C7-E92A-46BC-9AE8-B0287E1692B9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Eigenvalues and separation in graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Eigenvalues_and_separation_in_graphs"}}}}}