20.500.12556/DKUM-92004 Trees with distinguishing index equal distinguishing number plus one Drevesa z razlikovalnim indeksom za ena večjim od razlikovalnega števila The distinguishing number (index) D(G) (D'(G)) of a graph G is the least integer d such that G has an vertex (edge) labeling with d labels that is preserved only by the trivial automorphism. It is known that for every graph G we have D'(G) \leq D(G) + 1. In this note we characterize finite trees for which this inequality is sharp. We also show that if G is a connected unicyclic graph, then D'(G) = D(G). Razlikovalno število (indeks) D(G) (D'(G)) grafa G je najmanjše naravno število d, tako da G premore vozliščno (povezavno) označitev z d oznakami, ki jo ohranja le trivialni avtomorfizem. Znano je, da za vsak graf G velja D'(G) \leq D(G) + 1. V tem prispevku karakteriziramo končna drevesa, za katera je ta neenakost natančna. Dokažemo tudi, da če je G povezan, enociklični graf, potem velja D'(G) = D(G). automorphism group distinguishing index distinguishing number tree unicyclic graph grupa avtomorfizmov razlikovalni indeks razlikovalno število drevo enociklični graf true false true Technical University Press Angleški jezik Slovenski jezik Znanstveno delo 2025-03-11 08:26:19 2025-03-11 09:54:19 2025-03-12 03:12:42 0000-00-00 00:00:00 2020 0 0 Str. 875-884 št. 3 Letn. 40 2020 0000-00-00 Zaloznikova Objavljeno NiDoloceno 2017-09-15 2018-07-13 0000-00-00 519.17 18956889 10.7151/dmgt.2162 1234-3099 Alikhani-2020-TREES_WITH_DISTINGUISHING_INDEX.pdf Alikhani-2020-TREES_WITH_DISTINGUISHING_INDEX.pdf 1 52B8E3DB245D84B546B3F5FD842D8D6A 7a3ae0bbeaa0de6bbc4da946b2423b6171ddc8907d2894b74a33b04997631bb6 f2966631-fe55-11ef-b15e-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=189156 https://doi.org/10.7151/dmgt.2162 0 20e5afec-fe4a-11ef-b15e-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=189143 Fakulteta za naravoslovje in matematiko 0 0 0