Improving upper bounds for the distinguishing index
Pilśniak, Monika
ARS MATHEMATICA CONTEMPORANEA, Tome 14 (2017), / Harvested from ARS MATHEMATICA CONTEMPORANEA
link
link
link

The distinguishing index of a graph G, denoted by Dʹ(G), is the least number of colours in an edge colouring of G not preserved by any non-trivial automorphism. We characterize all connected graphs G with Dʹ(G) ≥ Δ (G). We show that Dʹ(G) ≤ 2 if G is a traceable graph of order at least seven, and Dʹ(G) ≤ 3 if G is either claw-free or 3-connected and planar. We also investigate the Nordhaus-Gaddum type relation: 2 ≤ Dʹ(G) + Dʹ(‾G) ≤ max{Δ (G), Δ (‾G)} + 2 and we confirm it for some classes of graphs.

Publié le : 2017-01-01
DOI : https://doi.org/10.26493/1855-3974.981.ff0 
@article{981,
     title = {Improving upper bounds for the distinguishing index},
     journal = {ARS MATHEMATICA CONTEMPORANEA},
     volume = {14},
     year = {2017},
     doi = {10.26493/1855-3974.981.ff0},
     language = {EN},
     url = {http://dml.mathdoc.fr/item/981}
}

Pilśniak, Monika. Improving upper bounds for the distinguishing index. ARS MATHEMATICA CONTEMPORANEA, Tome 14 (2017) . doi : 10.26493/1855-3974.981.ff0. http://gdmltest.u-ga.fr/item/981/