{"entities":{"Q870080":{"pageid":871928,"ns":120,"title":"Item:Q870080","lastrevid":50048662,"modified":"2026-01-12T19:26:42Z","type":"item","id":"Q870080","labels":{"en":{"language":"en","value":"Using determining sets to distinguish Kneser graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5132854"}},"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":"Q870080$0EEC674A-0C0C-4FA0-B56B-B49FF2BFD06F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b51c8e4541ea8fd421e94f0b419af263655be991","datavalue":{"value":{"text":"Using determining sets to distinguish Kneser graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q870080$444556D1-5B5D-4EA2-A499-633DFBA72F1F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5894d7f43045a8e2090e075d16f97dc8206a3aa1","datavalue":{"value":"1114.05089","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q870080$945D1725-FE5F-439A-AB84-5DF41A2777DA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"82040cfe7ba0d41798d213a2940864deca0691a1","datavalue":{"value":{"entity-type":"item","numeric-id":186192,"id":"Q186192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q870080$9DD88D2E-B939-44A7-9761-940DD1238BA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fa51bb1863efa081b3dbaf456d6e3c11d5750efc","datavalue":{"value":{"entity-type":"item","numeric-id":709321,"id":"Q709321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q870080$04042138-CC82-46B7-90FB-3069744EA9EF","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":"Q870080$4979D23D-8550-488A-AFF9-5E7B0C99C666","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"39eed756ef4774638f5dc70a5b404d4f34900328","datavalue":{"value":{"time":"+2007-03-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q870080$57D3847C-82A9-42A8-8D27-EA4A6C93E38C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8918cb03a048ecf003b4174500c67a4208ba4323","datavalue":{"value":"https://eudml.org/doc/127568","type":"string"},"datatype":"url"},"type":"statement","id":"Q870080$35FE67C0-39C5-469B-96B9-D8018D13F6CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"f189e533d606b4e6c5ffb1096fd4546dd3df0f38","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_14/Abstracts/v14i1r20.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q870080$9107E03F-92C4-4B3C-B12D-5FEC79BE4FF5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9a87560c667cf58a847348615009ab14235c48f3","datavalue":{"value":"Summary: This work introduces the technique of using a carefully chosen determining set to prove the existence of a distinguishing labeling using few labels. A graph \\(G\\) is said to be \\(d\\)-distinguishable if there is a labeling of the vertex set using \\(1, \\dots, d\\) so that no nontrivial automorphism of \\(G\\) preserves the labels. A set of vertices \\(S\\subseteq V(G)\\) is a determining set for \\(G\\) if every automorphism of \\(G\\) is uniquely determined by its action on \\(S\\). We prove that a graph is \\(d\\)-distinguishable if and only if it has a determining set that can be \\((d-1)\\)-distinguished. We use this to prove that every Kneser graph \\(K_{n:k}\\) with \\(n\\geq6\\) and \\(k\\geq2\\) is 2-distinguishable.","type":"string"},"datatype":"string"},"type":"statement","id":"Q870080$81172CB4-9167-4D99-A5CB-6AB9B48BBD08","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5333d0205ccf54f8482367bfadbaa8f4afc5f8fb","datavalue":{"value":"05C78","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q870080$8FB95358-F33D-4F5E-8486-BDCEDBCA1032","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q870080$32EA98BF-5D18-499B-A462-E04D9A8F1A54","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"94e4a571a4455d667386e1e93dfd1051c17d6256","datavalue":{"value":"5132854","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q870080$18C2D446-8D6B-4063-B250-D5EF75838581","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d25e14db36137e9a03d2112973e173f87b806ef","datavalue":{"value":"distinguishing labeling","type":"string"},"datatype":"string"},"type":"statement","id":"Q870080$7199DCD9-DEB4-464A-AF77-8E388A2D0F12","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":"Q870080$F71EDDE2-23A4-498A-ACB0-E182E4CACFDA","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"ab75ddb4cd139486786b2aedd38c1d4d74780de4","datavalue":{"value":"bafkreibnslii7zhghheeuhodgwcggouinmibaytaayylcdh5kabb3kcvei","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q870080$8C302306-151E-49AA-AF72-07C6867076A3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"995ab5d625565e71a9169edb91da924ff93310e4","datavalue":{"value":{"entity-type":"item","numeric-id":1953404,"id":"Q1953404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c6d78d1716144c60c9e825f5d14b92bfdb7d9a2f","datavalue":{"value":{"amount":"+0.8729557991027832","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":"Q870080$DA545CAC-B03E-4252-AD7D-18097EB009B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c89e1f3b30dad36089fc411f67ab8699f4797547","datavalue":{"value":{"entity-type":"item","numeric-id":1693128,"id":"Q1693128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b46dc90dde5eeb5808a912b15b1af217bf113ba","datavalue":{"value":{"amount":"+0.8554925322532654","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":"Q870080$14F3CB55-9066-4599-A891-3E6EC3A208BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e364ed90ca56e66982f4a29b03e0086e120c6cd","datavalue":{"value":{"entity-type":"item","numeric-id":5747367,"id":"Q5747367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"623947c2fc857b48f73ea9a55965aea306674553","datavalue":{"value":{"amount":"+0.8437417149543762","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":"Q870080$B88D33BE-D15B-43B2-8A0A-133C5A253206","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c09f59c7bf94e81e17848854f22dc2fd2f5e336","datavalue":{"value":{"entity-type":"item","numeric-id":5298911,"id":"Q5298911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c3e968932230b1b9884398c2a92924c15376642e","datavalue":{"value":{"amount":"+0.8235645890235901","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":"Q870080$82A79ED1-CEB6-4746-AD9A-3006768EC8C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b38a6c6c2296a13798528f65582ebed8fe5d5e4b","datavalue":{"value":{"entity-type":"item","numeric-id":869991,"id":"Q869991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"970c7b7e18faf02c594f78f3a670c535e61c7d86","datavalue":{"value":{"amount":"+0.8118011951446533","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":"Q870080$32F209CC-92F3-4F57-8075-F6184A06DA80","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:870080","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:870080"}}}}}