Trees with distinguishing index equal distinguishing number plus one

Saeid Alikhani; Sandi Klavžar; Florian Lehner; Samaneh Soltani

doi:10.7151/dmgt.2162

Trees with distinguishing index equal distinguishing number plus one

Saeid Alikhani, Sandi Klavžar, Florian Lehner, Samaneh Soltani

Institute of Discrete Mathematics (5050)

Research output: Contribution to journal › Article › peer-review

Abstract

The distinguishing number (index)D(G) (D′(G)) of a graphGis theleast integerdsuch thatGhas an vertex (edge) labeling withdlabels thatis preserved only by the trivial automorphism. It is known that for everygraphGwe haveD′(G)≤D(G) + 1. In this note we characterize finite treesfor which this inequality is sharp. We also show that ifGis a connectedunicyclic graph, thenD′(G) =D(G)

Original language	English
Pages (from-to)	875-884
Number of pages	10
Journal	Discussiones Mathematicae Graph Theory
Volume	40
Issue number	3
DOIs	https://doi.org/10.7151/dmgt.2162
Publication status	Published - 2020

Fields of Expertise

Information, Communication & Computing

Access to Document

10.7151/dmgt.2162Licence: CC BY-NC-ND 4.0

FWF - Groups - Graphs and Groups
Lehner, F.
1/04/19 → 31/12/20
Project: Research project

Cite this

@article{d27ae07f86d546488edfe276fb72d2bd,

title = "Trees with distinguishing index equal distinguishing number plus one",

abstract = "The distinguishing number (index)D(G) (D′(G)) of a graphGis theleast integerdsuch thatGhas an vertex (edge) labeling withdlabels thatis preserved only by the trivial automorphism. It is known that for everygraphGwe haveD′(G)≤D(G) + 1. In this note we characterize finite treesfor which this inequality is sharp. We also show that ifGis a connectedunicyclic graph, thenD′(G) =D(G)",

author = "Saeid Alikhani and Sandi Klav{\v z}ar and Florian Lehner and Samaneh Soltani",

year = "2020",

doi = "10.7151/dmgt.2162",

language = "English",

volume = "40",

pages = "875--884",

journal = "Discussiones Mathematicae Graph Theory",

issn = "2083-5892",

publisher = "The University of Zielona Gora Press",

number = "3",

}

TY - JOUR

T1 - Trees with distinguishing index equal distinguishing number plus one

AU - Alikhani, Saeid

AU - Klavžar, Sandi

AU - Lehner, Florian

AU - Soltani, Samaneh

PY - 2020

Y1 - 2020

N2 - The distinguishing number (index)D(G) (D′(G)) of a graphGis theleast integerdsuch thatGhas an vertex (edge) labeling withdlabels thatis preserved only by the trivial automorphism. It is known that for everygraphGwe haveD′(G)≤D(G) + 1. In this note we characterize finite treesfor which this inequality is sharp. We also show that ifGis a connectedunicyclic graph, thenD′(G) =D(G)

AB - The distinguishing number (index)D(G) (D′(G)) of a graphGis theleast integerdsuch thatGhas an vertex (edge) labeling withdlabels thatis preserved only by the trivial automorphism. It is known that for everygraphGwe haveD′(G)≤D(G) + 1. In this note we characterize finite treesfor which this inequality is sharp. We also show that ifGis a connectedunicyclic graph, thenD′(G) =D(G)

U2 - 10.7151/dmgt.2162

DO - 10.7151/dmgt.2162

M3 - Article

SN - 2083-5892

VL - 40

SP - 875

EP - 884

JO - Discussiones Mathematicae Graph Theory

JF - Discussiones Mathematicae Graph Theory

IS - 3

ER -

Trees with distinguishing index equal distinguishing number plus one

Abstract

Fields of Expertise

Access to Document

Fingerprint

Projects

FWF - Groups - Graphs and Groups

Cite this