Trees with Distinguishing Index Equal Distinguishing Number Plus One

Autor: Alikhani Saeid, Klavžar Sandi, Lehner Florian, Soltani Samaneh
Jazyk: angličtina
Rok vydání: 2020
Předmět:
Zdroj: Discussiones Mathematicae Graph Theory, Vol 40, Iss 3, Pp 875-884 (2020)
Druh dokumentu: article
ISSN: 2083-5892
DOI: 10.7151/dmgt.2162
Popis: 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) ≤ 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).
Databáze: Directory of Open Access Journals