Trees with distinguishing index equal distinguishing number plus one | Zendy

‎Saeid Alikhani | Zendy; Sandi Klavžar | Zendy; Florian Lehner | Zendy; Samaneh Soltani | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Trees with distinguishing index equal distinguishing number plus one

Author(s) -

‎Saeid Alikhani,

Sandi Klavžar,

Florian Lehner,

Samaneh Soltani

Publication year - 2018

Publication title -

discussiones mathematicae graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.476

H-Index - 19

eISSN - 2083-5892

pISSN - 1234-3099

DOI - 10.7151/dmgt.2162

Subject(s) - mathematics , combinatorics , index (typography) , tree (set theory) , statistics , discrete mathematics , computer science , world wide web

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).

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research