{"entities":{"Q1918875":{"pageid":1929617,"ns":120,"title":"Item:Q1918875","lastrevid":46459164,"modified":"2025-12-24T20:05:19Z","type":"item","id":"Q1918875","labels":{"en":{"language":"en","value":"Symmetry breaking in graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 907639"}},"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":"Q1918875$9F8C5B90-910C-4D81-B545-A499CEB85B0F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c809b94c611c336ca17b902549dc6593677c4bdd","datavalue":{"value":{"text":"Symmetry breaking in graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1918875$04719763-28D2-4DDF-B53A-77F7221908F7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b253fa7189455e93b532fee97a94e52b980f7d9a","datavalue":{"value":"0851.05088","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1918875$9E3527A7-1240-4C02-845C-42D2784BB852","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1a80f0a30c34568b1594b2aaace08fe6b51a1e6b","datavalue":{"value":{"entity-type":"item","numeric-id":234314,"id":"Q234314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1918875$A0BD5FD9-6BE9-4062-B081-06B63710F27E","rank":"normal"},{"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":"Q1918875$86F03E17-D67F-476F-9D97-420B9B0D1DD5","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":"Q1918875$010C1B7B-19C6-467F-AA84-2FA831B86C29","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ea39d34088133350decb299267d3fe6ec694e597","datavalue":{"value":{"time":"+1996-07-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1918875$06C5A23C-F61A-4DFC-AE95-2866CA32294E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"09956b33faa87a0fafd158763f1b59f3bb31117a","datavalue":{"value":"https://eudml.org/doc/118910","type":"string"},"datatype":"url"},"type":"statement","id":"Q1918875$6D197E67-08A2-44ED-BF27-19BA46BFEAD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"3d059445c29cde8043c3ad053f7e4d1c45f3c70c","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_3/volume3.html#R18","type":"string"},"datatype":"url"},"type":"statement","id":"Q1918875$FA5D919C-8AE7-4AD5-9232-F6A5040B7783","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"eadde862de7c5725ed7c567edd0d8fa85517fc1d","datavalue":{"value":"Summary: A labeling of the vertices of a graph \\(G\\), \\(\\phi: V(G)\\to \\{1,\\dots, r\\}\\), is said to be \\(r\\)-distinguishing provided no automorphism of the graph preserves all of the vertex labels. The distinguishing number of a graph \\(G\\), denoted by \\(D(G)\\), is the minimum \\(r\\) such that \\(G\\) has an \\(r\\)-distinguishing labeling. The distinguishing number of the complete graph on \\(t\\) vertices is \\(t\\). In contrast, we prove (i) given any group \\(\\Gamma\\), there is a graph \\(G\\) such that \\(\\Aut(G)\\) is \\(\\Gamma\\) and \\(D(G)= 2\\); (ii) \\(D(G)= O(\\log(|\\Aut(G)|))\\); (iii) if \\(\\Aut(G)\\) is abelian, then \\(D(G)\\leq 2\\); (iv) if \\(\\Aut(G)\\) is dihedral, then \\(D(G)\\leq 3\\); and (v) if \\(\\Aut(G)= S_4\\), then either \\(D(G)= 2\\) or \\(D(G)= 4\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1918875$D9F9CA1B-C3C4-4397-A4E5-EF050235468E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5333d0205ccf54f8482367bfadbaa8f4afc5f8fb","datavalue":{"value":"05C78","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1918875$88E4C404-34E7-49B8-A7A3-D63032F3147E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1918875$D3A45E3F-B22B-4F53-A485-C999ED67273D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"25c8936003d39e41a9c8a541470f5aac0fe1fa32","datavalue":{"value":"20B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1918875$001D5F9B-BCC6-4AD4-BD30-9239CA68E64F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1918875$CB7F436D-F336-40FD-B292-C2EAE177EFEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7560d7c00da9c803324a799b9e549a4182d5fe47","datavalue":{"value":"20F99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1918875$3336AE6E-9C55-4701-8D75-498927C30656","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bbae47e097fb94b33fc6b57c756fc03c91fe1de9","datavalue":{"value":"907639","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1918875$F2408E34-E79D-46DA-8846-15EB0E1147EC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"721db152ea6f5f1d941a96190ff027c3df9b3519","datavalue":{"value":"symmetry breaking","type":"string"},"datatype":"string"},"type":"statement","id":"Q1918875$1EFAB14D-83FB-42FD-8B31-6AB8C80159F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb5dbb9c018c941d87d8ebd9a9c3e079d8ffa0f1","datavalue":{"value":"labeling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1918875$8BC99FFA-E155-4301-984D-BCF740DE31F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ce7ab89ef0afcd2141c7da8aae338608bd16ac9a","datavalue":{"value":"automorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q1918875$F2BA4A33-8DE3-481D-9A3B-1521C04EF43B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f161ce45f2c032a5d05185ff52a7738050ecdea9","datavalue":{"value":"distinguishing number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1918875$AE8C4A9F-1F55-4837-B059-CBD9EB38ABD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"36c2c990981f9c9594b70bf6086c9fd5e77cc4ca","datavalue":{"value":"group","type":"string"},"datatype":"string"},"type":"statement","id":"Q1918875$D245696C-0F05-4158-98BC-434A8D0ECFD9","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":"Q1918875$24EFFDC0-C23C-462D-83F2-60718AD7AF9C","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"1238b3fdce6a6215194f0b4b696b8c0c50f3019b","datavalue":{"value":"bafkreifx4dix6zlligixauozf5mg3jws373fkm5zagx5gdqmuqwtkrhjiy","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1918875$680CE97A-FC73-48BE-BECC-7363AFD78DE5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1fcf46ca2a3159140e56fe356bd976f25a17300f","datavalue":{"value":{"entity-type":"item","numeric-id":1883683,"id":"Q1883683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30e4129908f7d34791af7a797f0b0cbde7ed9776","datavalue":{"value":{"amount":"+0.8965396285057068","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":"Q1918875$DE349128-08F8-4DF5-9AE2-EAB8AF109B2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d41e7d802d2df914cef0d787ab1bd23da73c2f66","datavalue":{"value":{"entity-type":"item","numeric-id":3583296,"id":"Q3583296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"139822e099d608aff5e856b629a6c9a6390f8257","datavalue":{"value":{"amount":"+0.8397706747055054","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":"Q1918875$AD44AE0E-C91B-479E-86D6-0E6ECF2B555A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8721a8db5c5fc360a6a44b863d8300e53efce273","datavalue":{"value":{"entity-type":"item","numeric-id":4949875,"id":"Q4949875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"235a554661ae54c1477cffb0b516cbe9dbb6147d","datavalue":{"value":{"amount":"+0.8347252011299133","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":"Q1918875$A6590D57-0864-481F-BEAF-A898174E4D36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e9c874c80fe53e4abbef59e2d01f62b6710911ad","datavalue":{"value":{"entity-type":"item","numeric-id":4621305,"id":"Q4621305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d7646c0df75f523ce46a719c169539da743fe67","datavalue":{"value":{"amount":"+0.8216331005096436","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":"Q1918875$747A62B3-B728-4E0F-BA74-157A3B3E49E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08ab3f2648fa40a79b5b99fcdd6ca44dd1460c69","datavalue":{"value":{"entity-type":"item","numeric-id":2509274,"id":"Q2509274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"84a12cf2bd8e8731bfadac9c02f391adc465f276","datavalue":{"value":{"amount":"+0.8146047592163086","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":"Q1918875$14C419F9-6685-4384-91FB-2702305308B1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1918875","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1918875"}}}}}