{"entities":{"Q1385847":{"pageid":1396587,"ns":120,"title":"Item:Q1385847","lastrevid":67508031,"modified":"2026-04-12T18:28:49Z","type":"item","id":"Q1385847","labels":{"en":{"language":"en","value":"A note on the asymptotic and computational complexity of graph distinguishability"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1147940"}},"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":"Q1385847$1A4F3666-AFDE-4299-9AAF-209644A3BC32","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"af7e10c00b95892e18bc87395aa989cd53aa522a","datavalue":{"value":{"text":"A note on the asymptotic and computational complexity of graph distinguishability","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1385847$07DC6B38-94A7-41C0-A9C4-40BD0945B69C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ab22dbcba129a223abc84fb70a7b828fb574b1c1","datavalue":{"value":"0901.05052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1385847$65162729-98EC-437C-A502-A984344ED42F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9e1640d7463d22bb99b71dc73dd0067db506b020","datavalue":{"value":{"entity-type":"item","numeric-id":204362,"id":"Q204362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1385847$5A637FF5-AC2D-45BF-91D2-EA18E761370B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6fbfebc2bf8aa93e71bcb717fab67c77978715de","datavalue":{"value":{"entity-type":"item","numeric-id":210282,"id":"Q210282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1385847$F57832D4-4BE8-4886-9D6C-CD1944E44168","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":"Q1385847$228C53F5-26CB-40E2-BCD0-287CD75643F9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0a70e1c598c77a2c68107d0b0c1806859c43bcd6","datavalue":{"value":{"time":"+1998-04-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1385847$2CCFCDA8-EFCC-465E-ACC9-7A98AD155BC4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1d140d91140a486186692116d1d4bb3d7c14f1ae","datavalue":{"value":"https://eudml.org/doc/119614","type":"string"},"datatype":"url"},"type":"statement","id":"Q1385847$A137940A-F4B5-46B8-8D8D-609B69EBA951","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"c969183b457062a56cc9321e897e4902ba2b15cb","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_5/Abstracts/v5i1r23.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1385847$10873DAB-B1B1-44E2-AAF8-B5A72BA9EF47","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8e5d1fd1e27513dd1cbbada5c32091a58581d529","datavalue":{"value":"A graph \\(G\\) is \\(d\\)-distinguishable if it has a vertex coloring with \\(d\\) colors such that \\(G\\) has no color preserving automorphisms. (Adjacent vertices may receive the same color. Indeed, the only purpose of the graph in this theory seems to be to specify a group of vertex permutations.) The cycle norm of \\(G\\), \\(c(G)\\), is \\(| V| - k\\), where \\(k\\) is the greatest number of disjoint cycles in a non-trivial element of \\(\\Aut(G)\\), regarded as a vertex permutation. Clearly, the more disjoint cycles that a vertex permutation has, the more symmetric colorings it will have. The authors use this observation to conclude that  \\[  c(G)\\ln(d) > \\ln(| \\Aut(G)|)\\text{ implies that \\(G\\) is \\(d\\)-distinguishable}.  \\]  The second half of the paper examines the computational complexity of determining the \\(d\\)-distinguishability of a graph \\(G\\). Whether or not it is NP-hard is an open problem. The authors present compelling evidence that it is not coNP-hard. For a basic reference on this subject see \\textit{M. O. Alberson} and \\textit{K. L. Collins} [Electron. J. Comb. 3, No. 1, Paper R18 (1996; Zbl 0851.05088)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1385847$F3221BC2-BB98-4B94-9B1B-8BB1C3B564DA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1385847$D3D8E9C3-CEA1-467F-A257-EE95015426F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1385847$27DDFD3F-DE48-4783-A025-F37707C78A65","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d328d926eab48887ef81a876e25c8b4d3bddf77e","datavalue":{"value":"1147940","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1385847$410EA145-1AE7-49C3-B600-2230BE1CAC79","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85dfdbd7a975d6137b355769addaba184ea21dc4","datavalue":{"value":"vertex coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1385847$8951B367-77A0-44DC-AC96-EA3BEBEAC740","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4e28b5e893ee2450a5ed2cbfd38aace27dd09fed","datavalue":{"value":"cycle norm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1385847$E77BE74F-4CCD-4A0C-A2BF-A7E625681E6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"406cc9a146318abbb73ed93dcf260fd419a1d9f1","datavalue":{"value":"vertex permutation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1385847$5E4E5C48-A67A-444A-9395-6BBABB33AB37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1385847$DC5FEFED-72F6-4180-9765-B311EBA7D408","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"09c46553ea87cd2a93272f63687a4a495c3a2089","datavalue":{"value":"\\(d\\)-distinguishability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1385847$F7BEED07-3119-4890-B55A-39456144B3E6","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"99aa050a3c44bfaf6f196d26904cc4c97e1c205f","datavalue":{"value":{"entity-type":"item","numeric-id":966174,"id":"Q966174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1385847$1C666A58-B414-40FF-9BD2-78E595854507","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":"Q1385847$AD09F8A6-352B-4C63-8CCE-172D0E813A3A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aaacd1a47bf94e77e54a4f1872699db3fb2ae89d","datavalue":{"value":{"entity-type":"item","numeric-id":426889,"id":"Q426889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb13312ec7647b1cf72e131e7647a6dc5bd71091","datavalue":{"value":{"amount":"+0.79724437","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":"Q1385847$FC92DD15-CA93-498E-A92A-FAF91E301529","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c748b990312d978e76379f39b847d87864df359c","datavalue":{"value":{"entity-type":"item","numeric-id":5365544,"id":"Q5365544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5f03263fd5cf810578e6cbc177e6e6b9a0c81c7a","datavalue":{"value":{"amount":"+0.7941351","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":"Q1385847$6B83357D-4CF6-4185-9DD8-7ED5DAA8A9F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"33db6452b99de5664402f142ecaf980d90ae4ee3","datavalue":{"value":{"entity-type":"item","numeric-id":813439,"id":"Q813439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"99c05cff3f0b0887cbe9c59098021744a905d8a0","datavalue":{"value":{"amount":"+0.78708684","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":"Q1385847$DF76189C-50D8-4607-9644-2B7C9BF32FA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"805f97f44020587d5bdad2ac1ba6b0fa6707f51c","datavalue":{"value":{"entity-type":"item","numeric-id":870080,"id":"Q870080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce5208a8e4bc888cc4f29e9f651f0d4e1c3b4be5","datavalue":{"value":{"amount":"+0.7753189","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":"Q1385847$C5724980-1FC9-4558-89E6-19502BAEEBD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ad12db48e5f49f73b22a3514508c8c53b139446f","datavalue":{"value":{"entity-type":"item","numeric-id":490268,"id":"Q490268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"946b1cd2c24b37868ac4cede5d957717decb5caa","datavalue":{"value":{"amount":"+0.77358574","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":"Q1385847$037F4650-9AA1-492B-AFC7-C58B708A4961","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4103bc50f96faf1f02d2a6fc0fe824837b046fe9","datavalue":{"value":{"entity-type":"item","numeric-id":5058214,"id":"Q5058214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ad7a2402967f295aaacf0636d68aad0c69a1dcc","datavalue":{"value":{"amount":"+0.77056473","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":"Q1385847$003BBBE8-BE10-4F4E-B6DB-5080C471D351","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6bfdba8e67918651ce5e09bfb1e8aab021850cf","datavalue":{"value":{"entity-type":"item","numeric-id":6056750,"id":"Q6056750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d8df00422dbc5d568f17823d02e17eb61380744","datavalue":{"value":{"amount":"+0.7682137","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":"Q1385847$9BC2C9EF-A38E-4C38-8FC8-9BB35097E12C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9faccbf24bf4a12897b0739ff8461dd148a94e26","datavalue":{"value":{"entity-type":"item","numeric-id":2237852,"id":"Q2237852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec65d8a0f5d6dda8285781d3363f1842652b72c7","datavalue":{"value":{"amount":"+0.7670177","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":"Q1385847$ACA42532-15E0-4BFA-BAC6-E74D8A930C8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"522d21bd73927915660a4cc757b685892bcadb31","datavalue":{"value":{"entity-type":"item","numeric-id":1918875,"id":"Q1918875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8bb4da4f3f29c67fa2b9388abc08dad4ba15493a","datavalue":{"value":{"amount":"+0.76511997","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":"Q1385847$9FC7052D-50D5-4084-B675-585AA72E18CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ded89460dfe38946cef12d8084bf096ef8635e7b","datavalue":{"value":{"entity-type":"item","numeric-id":626859,"id":"Q626859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a3476fcb42e05a829c9035c44ce67ee3b9cb872e","datavalue":{"value":{"amount":"+0.7625116","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":"Q1385847$1BC7277C-3E0B-41FE-99E0-CB51D7FFC570","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"65bf30900395a89182dfc9928fbd9d559b32a5ea","datavalue":{"value":"bafkreiazn4vak3rneqv7oweme2izsew5s76p2lx4x7wvebckgm6ba67dwq","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1385847$E3DA1D4C-86AF-490A-821A-56ABA43E95BE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A note on the asymptotic and computational complexity of graph distinguishability","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_note_on_the_asymptotic_and_computational_complexity_of_graph_distinguishability"}}}}}