{"entities":{"Q2176156":{"pageid":2186899,"ns":120,"title":"Item:Q2176156","lastrevid":57767862,"modified":"2026-04-02T11:01:13Z","type":"item","id":"Q2176156","labels":{"en":{"language":"en","value":"Trees with distinguishing number two"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7195758"}},"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":"Q2176156$7BD4CE0B-4ADB-40C3-A503-9BC257F1BC36","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f67d4b6e342ea7cf2a9c4ea389807b9fd25138e7","datavalue":{"value":{"text":"Trees with distinguishing number two","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2176156$1617E95D-4864-4932-99BA-B4EF19E3FF43","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"53fe563992a391507d6e4542167c83b387802f47","datavalue":{"value":"1479.05051","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2176156$26743F67-9BEB-4E4A-92B1-D0D19F2C7F36","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"01bc004848444ad88855b47de686f076a5e41c51","datavalue":{"value":{"entity-type":"item","numeric-id":277497,"id":"Q277497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2176156$349F2E98-4B7C-4869-806F-20D59E02D9CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bff470ca49752f1c6e0a6d330c1236199e1f531c","datavalue":{"value":{"entity-type":"item","numeric-id":1649919,"id":"Q1649919"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2176156$E83FEFA6-0B18-41DF-8D63-0E5AA2C29F08","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"03e0344fac3b71001f7d01722f599a45a6c3dae0","datavalue":{"value":{"entity-type":"item","numeric-id":321980,"id":"Q321980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2176156$4112CC10-4E2A-48DC-BB3C-4A4BBFD8EADF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"266349113821a9568dc8e478c029e41016cf97fa","datavalue":{"value":{"time":"+2020-05-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2176156$71D71B6A-8918-48E7-AB79-01ED0E030985","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cfd5e7b9c8331fd452d4498ff1fd8928c24fff8c","datavalue":{"value":"https://arxiv.org/abs/1611.09291","type":"string"},"datatype":"url"},"type":"statement","id":"Q2176156$0CD73423-DE44-4070-AD41-0AC849FFD44E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3930d4eef4764709ae0882c158e296140f805fe8","datavalue":{"value":"A labeling of a graph $G$, $\\phi:V(G)\\to\\{1,2,\\dots,r\\}$ is said to be $r$-distinguishing if for any $\\sigma\\in\\mathrm{Aut}(G)$, $\\sigma \\neq\\mathrm{id}$, there is a vertex $x$ such that $\\phi(x)\\neq\\phi(\\sigma(x))$. That is, $\\phi$ is $r$-distinguishing if no nontrivial automorphism of $G$ preserves all the vertex labels. The distinguishing number $D(G)$ of a graph $G$ is the least integer $d$ such that $G$ has a $d$-distinguishing labeling. Distinguishing labeling for graphs was introduced by \\textit{M. O. Albertson} and \\textit{K. L. Collins} [Electron. J. Comb. 3, No. 1, Research paper R18 (1996; Zbl 0851.05088)]. Note, $D(K_n)=n$ for the complete graph $K_n$ and $D(P_n)=2$ where $n\\geq 2$ and $P_n$ is a path with $n$ vertices.   In this paper, the authors discuss this concept for trees and show: \\begin{itemize} \\item[1.] If $T$ is a tree of radius at most two, then $D(T)=2$ if and only if $T$ is one of the trees that the authors have shown in Figure 2. \\item[2.] There is no tree $T$ with diameter three, radius $\\mathrm{rad}(T)\\geq 3$ and $D(T)=2$.  \\item[3.]If $T$ is a tree with radius $\\mathrm{rad}(T)\\geq 3$ and $D(T)=2$, then the complement $\\bar{T}$ of $T$ is a connected 2-self-centered graph that is not bipartite.  \\end{itemize} After further discussion of self-centered graphs, the authors end the paper with a Question: Characterize edges which add to each edge-minimal 2-self-centered graph such that $D(T)=2$.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2176156$7A600039-462D-4F87-A8EC-657B7000185B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6ce7ffbbd6d2dbdda3e66251ca72d6f4fe790d2f","datavalue":{"value":{"entity-type":"item","numeric-id":1115516,"id":"Q1115516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2176156$8E4E2153-5A8D-4497-B046-7D0FFB53121F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2176156$BD440FC7-69B0-49C3-8951-4E1BD9BB69A2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c26c8503c0af6770d19a3140faf496e379b1f09a","datavalue":{"value":"7195758","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2176156$E726259F-9E03-4D3D-A1C0-974B6FC68CC7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f161ce45f2c032a5d05185ff52a7738050ecdea9","datavalue":{"value":"distinguishing number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2176156$DDB51784-A194-40FB-B73D-E37044BE9C30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"534805fa6153b1b3786edcd60407ef0861005e9a","datavalue":{"value":"tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q2176156$0A6E9C18-F800-4048-BFD2-A5B3B41C8DC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7567554b1367efc97f3e213c87dba0f77ed4b4f7","datavalue":{"value":"radius","type":"string"},"datatype":"string"},"type":"statement","id":"Q2176156$7FB54F07-4773-4B08-8389-6BD2BD2B4330","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":"Q2176156$2399FF2F-8AD7-420D-BF63-72784EC61517","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7a9eae06f4e0942f53406b449b17bc60841b25a7","datavalue":{"value":"W2963814438","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2176156$49920E3E-3A2B-4436-AB2E-D24C9A6DB548","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"236691b53238960ce2ec2de1ab529fe8466ade5d","datavalue":{"value":{"entity-type":"item","numeric-id":4294577,"id":"Q4294577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2176156$E6E736A6-3945-477E-B86F-D41BC670DDF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d7ff22a7f90b2e51117d80664f4b709579e47eb","datavalue":{"value":{"entity-type":"item","numeric-id":2788723,"id":"Q2788723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2176156$4F43B9B9-F4F5-4692-BF06-953F5D438FF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44f7613f52c01d3694875277e1eb417291d22076","datavalue":{"value":{"entity-type":"item","numeric-id":1073807,"id":"Q1073807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2176156$A13457CA-D298-47C0-A83A-01524DE66E00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dbdfe0734a921e36b5462d1798f9f77e17cbbc0a","datavalue":{"value":{"entity-type":"item","numeric-id":1692622,"id":"Q1692622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2176156$17761763-507D-477A-A06D-B185BA3FE82E","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":"Q2176156$FE9C80F3-8624-4632-9CFA-49ED982121A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d249e74a398d3c336f8bf6b9bc485393f2db078a","datavalue":{"value":{"entity-type":"item","numeric-id":813439,"id":"Q813439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2176156$F96E3C91-D906-43FC-B1E6-2EE414B0FF12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e09c606c496e90c08c7ed87c9fa59fa93105e670","datavalue":{"value":{"entity-type":"item","numeric-id":2427541,"id":"Q2427541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2176156$801A6F71-34C7-4511-B866-BB8FE52AB342","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29d63a79545ea48830c703c48ef601d8deada148","datavalue":{"value":{"entity-type":"item","numeric-id":5898352,"id":"Q5898352"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2176156$7B548187-DA28-4F00-8AC9-8E74F4E8934C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cacf171eae503e4566c0a32b2d353815b471025a","datavalue":{"value":"10.1016/J.AKCEJ.2018.02.001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2176156$E39F3DA7-ABFE-4401-A4F2-BA5A3663C998","rank":"normal"}],"P1643":[{"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":"98d9256895f1c10ccf1dadecd266e19c67a5f82d","datavalue":{"value":{"amount":"+0.8036431","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":"Q2176156$6D6BA74E-D96F-4946-8B79-DCE01412DF1B","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":"b8be2dc36c26e28f697df7b8300482c9c0fa42d7","datavalue":{"value":{"amount":"+0.80325127","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":"Q2176156$03939620-E72D-43B8-8C65-B986741511BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b1b25a0c10e0e127907c940f55aa3b4f0bf0e4b","datavalue":{"value":{"entity-type":"item","numeric-id":2175243,"id":"Q2175243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7603b82692a8c4101f2a1a06172d277c2c70f09","datavalue":{"value":{"amount":"+0.79642236","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":"Q2176156$4669B3DE-1BAB-479B-9D3D-CEE1A31A2F79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"31c9058f7227585b9a8c15dc51c32facc4ab34df","datavalue":{"value":{"entity-type":"item","numeric-id":5921670,"id":"Q5921670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9dc095a895fe4d3c5e094bac0a5e26f60d455b4c","datavalue":{"value":{"amount":"+0.79191047","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":"Q2176156$73771BD1-424F-4F43-8DA5-983277BF9F9F","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":"15ab39dfad96760ffec1e43d19983014056e9fca","datavalue":{"value":{"amount":"+0.7761906","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":"Q2176156$81D10D4B-B0CC-4821-8E77-92DAC368EC54","rank":"normal"},{"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":"968234db1b60ec9f41be2d4f5dbc0afef9dfe579","datavalue":{"value":{"amount":"+0.7726496","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":"Q2176156$59CE46F5-6A08-46D5-82E8-1BBD22923FEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d39035ad6b05730ba6dac054a4eb64358bfc20db","datavalue":{"value":{"entity-type":"item","numeric-id":4969593,"id":"Q4969593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"85c1ef3cc9b1d89a933c70167a599892975c30e8","datavalue":{"value":{"amount":"+0.7724744","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":"Q2176156$C9823C4B-1CEE-441C-9514-B24E601F3C80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"678ae25279d2000d22742e84f1d73faee78c275d","datavalue":{"value":{"entity-type":"item","numeric-id":2968230,"id":"Q2968230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d2aa3aa54ebe13a5fd609de5fa9199adc62cd39","datavalue":{"value":{"amount":"+0.7628593","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":"Q2176156$5853CD23-12B4-417C-8950-63329430E49D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b07031f590d0d039ed84fa9cae49d12d0944af5","datavalue":{"value":{"entity-type":"item","numeric-id":1011889,"id":"Q1011889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"88430cf69c6a10cd4bd04d4373f618b90a1650de","datavalue":{"value":{"amount":"+0.7619157","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":"Q2176156$28341AAA-24EE-42BC-A57F-6CC33FF50638","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f0145626f768df0d464b2e04a8d8bcfb324366c","datavalue":{"value":{"entity-type":"item","numeric-id":815210,"id":"Q815210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f62a93bc6c4f545c7a129138818e23d98fc62aa","datavalue":{"value":{"amount":"+0.7595316","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":"Q2176156$BC54F125-9007-4371-8BED-3B5CC2AEA1A1","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"c39a117a349789e54237c0a3254f5a10c0a6517e","datavalue":{"value":{"entity-type":"item","numeric-id":6830565,"id":"Q6830565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2176156$6820AA66-221C-49EC-9E80-D79D26393F16","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2176156","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2176156"}}}}}