{"entities":{"Q490268":{"pageid":492035,"ns":120,"title":"Item:Q490268","lastrevid":62228607,"modified":"2026-04-11T04:39:25Z","type":"item","id":"Q490268","labels":{"en":{"language":"en","value":"Infinite graphs with finite 2-distinguishing cost"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6389223"}},"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":"Q490268$8B90F02A-2D43-4774-B822-6ECE401A6B10","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"881996255a6076b8dcc6aea95f4abe65c341db62","datavalue":{"value":{"text":"Infinite graphs with finite 2-distinguishing cost","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q490268$9478EF3B-6EFD-4F29-85F8-BD8305BA41D2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3b6348b14f376da3ccbcf1a21b2d938631d15419","datavalue":{"value":"1305.05163","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490268$F42E87BD-7F07-4C3B-9843-23E204FF2456","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"10c07f8b7e3cd9f2923ddf5077d5a80431b6d4ef","datavalue":{"value":{"entity-type":"item","numeric-id":201986,"id":"Q201986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490268$4BD84971-BDA5-445E-BD39-A868BFACCC2A","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":"Q490268$689DB628-7080-4315-9462-246189597247","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":"Q490268$F83F84ED-FB04-4B8E-A6C7-92419C9BC2B1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8bb6c16b18fb3fcb7c20a96f2fcd94ae71f0f929","datavalue":{"value":{"time":"+2015-01-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q490268$248EF5B8-C02C-4B36-AC59-5021DED38972","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e5b582b1ad97b9884706bf02a185c0d080220ef5","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p52","type":"string"},"datatype":"url"},"type":"statement","id":"Q490268$B492B6B7-B984-4699-8551-07733832FE76","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"68aeaf3e8d7b4f3c8effc817b115e94696f58332","datavalue":{"value":"Summary: A graph \\(G\\) is said to be 2-distinguishable if there is a labeling of the vertices with two labels such that only the trivial automorphism preserves the labels. Call the minimum size of a label class in such a labeling of \\(G\\) the cost of 2-distinguishing \\(G\\).  We show that the connected, locally finite, infinite graphs with finite 2-distinguishing cost are exactly the graphs with countable automorphism group. Further we show that in such graphs the cost is less than three times the size of a smallest determining set. We also another, sharper bound on the 2-distinguishing cost, in particular for graphs of linear growth.","type":"string"},"datatype":"string"},"type":"statement","id":"Q490268$252109D9-9182-4AE6-A055-89C5230892AF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9729428b7f3faff6f70db9a7fa765e75946ff6b6","datavalue":{"value":"05C63","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490268$21019302-B4C9-46C5-A20B-D5573FFCF2CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490268$F204031D-4490-4D70-895E-D33B16E01F3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490268$8EFAE7EC-37B6-41C5-9821-392DF464FF5C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8f5646f3697c3b6166f3ffb2d33bb9799fb36dd6","datavalue":{"value":"6389223","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490268$BC6EAEC9-90E1-4589-A976-872CD412BC0E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f161ce45f2c032a5d05185ff52a7738050ecdea9","datavalue":{"value":"distinguishing number","type":"string"},"datatype":"string"},"type":"statement","id":"Q490268$77395F0D-20C9-47E1-B188-0E77978FCCC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88e39c6399827ed47b6c439348383c3ff71c9cba","datavalue":{"value":"distinguishability","type":"string"},"datatype":"string"},"type":"statement","id":"Q490268$3CF564A3-C7A1-4289-A6C4-F8EF11F2AEEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ce7ab89ef0afcd2141c7da8aae338608bd16ac9a","datavalue":{"value":"automorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q490268$5D92374A-9F61-4C65-BE24-F312C526B147","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b5857b06803601475b74a9c90e1521827409cc4f","datavalue":{"value":"determining set","type":"string"},"datatype":"string"},"type":"statement","id":"Q490268$0DF08CED-F5FB-43FB-89A5-8317BB1C10D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"05b737b948faa254fa5ccb6f6f7b03ad01d78058","datavalue":{"value":"determining number","type":"string"},"datatype":"string"},"type":"statement","id":"Q490268$52D6EC4C-B771-44A0-A78E-4E9286D744CF","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":"Q490268$C8DBEC04-428B-4B90-91BA-3D5691955D1C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee150ccc87acd0dd777274f553589e46b09fea97","datavalue":{"value":{"entity-type":"item","numeric-id":870080,"id":"Q870080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490268$32F12B1A-C01F-426E-A4ED-1213F6B9BA45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9234f0e63bf5a06d1fb5cac8ee4d51f04190a4c4","datavalue":{"value":{"entity-type":"item","numeric-id":1918875,"id":"Q1918875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490268$4607EF44-4E72-4CAB-85C5-CC6C6B7FA4D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2d76b6c8b7e12b93ebcdbb0f346b5649614f36b","datavalue":{"value":{"entity-type":"item","numeric-id":869991,"id":"Q869991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490268$7FAC5FA5-4CC3-4205-8038-F34E5CC8900F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff94aa85b9383e28751c4886fff062989e864cfa","datavalue":{"value":{"entity-type":"item","numeric-id":5502846,"id":"Q5502846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490268$4755F410-A3D5-46EF-83A0-A23FDDC9694D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b70a49e3245f46b796b63b15800dc7354226686","datavalue":{"value":{"entity-type":"item","numeric-id":5298911,"id":"Q5298911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490268$42370347-2E8F-4E1D-8BC3-75C5638BD36E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97654eaa6344954ff92e116f8b05b82baf9bc761","datavalue":{"value":{"entity-type":"item","numeric-id":1824687,"id":"Q1824687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490268$4E0B127C-EE31-4FE9-8E53-4DD263911AAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dae7d2113aba662b7a5d739def76d8ee78327106","datavalue":{"value":{"entity-type":"item","numeric-id":3191457,"id":"Q3191457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490268$FDAA2F4F-DE9D-44CB-9B5A-2F6C6D93977A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23ef51e0c1fd3ed374b0d4b2a575650b7bf89695","datavalue":{"value":{"entity-type":"item","numeric-id":2562190,"id":"Q2562190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490268$89EA3BED-CD17-48FE-91BB-D9F76D9A9CD1","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"2b32e8bac267bddf6c7da58841f81a4593a9a037","datavalue":{"value":"bafkreiafamqitsydk6bypsx7hdlgwb2r4ois32yw6mqzg6ucmnt6zzijse","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490268$9408FBE9-22FE-44ED-B3BC-BE7F77ED3BC0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89869053ab25bd3073efadfb369cc3415c9435a3","datavalue":{"value":{"entity-type":"item","numeric-id":2363696,"id":"Q2363696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ccde078b15240af8eee3ec0ac9aa93fcceaf3e96","datavalue":{"value":{"amount":"+0.8973347","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q490268$B47B88B6-9BA5-4F71-B62C-CE6D7F4FD052","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b7aa659452c357c5dd4ee4aa6a91e926dc2cbd4","datavalue":{"value":{"entity-type":"item","numeric-id":2372880,"id":"Q2372880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e499ba142b0bc30fd7a8a25d541e480e19e57123","datavalue":{"value":{"amount":"+0.89240277","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q490268$E394A8D1-2969-4B53-BE41-A0EF105F63C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d931aa49044b9ba92fc1cdc94b784c6e2d7842e9","datavalue":{"value":{"entity-type":"item","numeric-id":6081887,"id":"Q6081887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fcd4b5a2c8547f366afdca5bd2f2ec6dba812c9a","datavalue":{"value":{"amount":"+0.89195055","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q490268$1B56C7CC-C28E-4DA3-B2F6-CAF1B9262794","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"175c2d3a9d410ddeea3a596c48f2d5fbaf6cde87","datavalue":{"value":{"entity-type":"item","numeric-id":2341071,"id":"Q2341071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d431a6dfc37c3d87faf44f530aa53d58e507a67a","datavalue":{"value":{"amount":"+0.88642126","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q490268$F30B2B82-C9AE-4801-B5FD-992561B1E677","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"34baaf730b9106db7e19231d2688372e3d8132ba","datavalue":{"value":{"entity-type":"item","numeric-id":5110667,"id":"Q5110667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b9145183ae70e6bbb01fe557753d4391f8b470d2","datavalue":{"value":{"amount":"+0.8852726","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q490268$873CF016-CE20-4C68-B7CD-B7C58689D299","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f69bc72ba9b6e7f76df4080c4e0dba977020c62","datavalue":{"value":{"entity-type":"item","numeric-id":1323483,"id":"Q1323483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"beacb0d95c6b9d0820aa0bdd0a620cc4b4d22a66","datavalue":{"value":{"amount":"+0.884371","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q490268$46CC2F92-C93F-411D-803A-1CD879CE7396","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"30153577bd343aafb7578ce723e58da64a26bf86","datavalue":{"value":{"entity-type":"item","numeric-id":5370828,"id":"Q5370828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e245d59db4560dd3f50ff2e475c7d5e4be35883","datavalue":{"value":{"amount":"+0.87768835","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q490268$F62BA6FE-106D-40A9-8299-BD25172E3AD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a7f7cc88d0bb727750f8da438c2dd99ac8e0738","datavalue":{"value":{"entity-type":"item","numeric-id":4537558,"id":"Q4537558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7e7caa33e8e718e2ceaedf0540b95b08988f78cc","datavalue":{"value":{"amount":"+0.875258","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q490268$CB830DC1-4B4B-4C2A-8E06-F4F45591B08B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d66d0b698b04ebafa7ab012e06cb16d3063929a","datavalue":{"value":{"entity-type":"item","numeric-id":3204497,"id":"Q3204497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"959b33ff29a2d2e7dee451301ccb81543711766f","datavalue":{"value":{"amount":"+0.86907554","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q490268$D647D93A-49C0-4DF0-BE45-DDBE3EF64F7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c3adf65295315072ba9f1504b8bfaaf24f2d782","datavalue":{"value":{"entity-type":"item","numeric-id":5499933,"id":"Q5499933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b07c6b88b9c0eac1fdf622d19d065cdfd79cef59","datavalue":{"value":{"amount":"+0.8684676","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q490268$5389D293-036C-40BA-9B8C-38BBAEC2AE59","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Infinite graphs with finite 2-distinguishing cost","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Infinite_graphs_with_finite_2-distinguishing_cost"}}}}}