Improving upper bounds for the distinguishing index - Pilśniak, Monika (Ars mathematica contemporanea, 2017)
Razlikovalni indeks grafa ?$G$?, označen z ?$D^′(G)$?, je najmanjše število barv v barvanju povezav grafa ?$G$?, ki ga ne ohranja noben netrivialni avtomorfizem. Karakteriziramo vse povezane grafe ?$G$?, ki ustrezajo pogoju ?$D^′(G)≥ Δ(G)$?. Pokažemo da je ?$D^′(G)≤ 2$?, če je ?$G$? sledljiv graf reda najmanj sedem, in da je ?$D^′(G)≤ 3$? če je ?$G$? bodisi brez trizobov ali pa je 3-povezan in planaren. Raziskujemo tudi relacijo tipa Nordhaus-Gaddum: ?$2≤ D^′(G)+D^′(\overline{G})≤ \max\{Δ(G),Δ(\overline{G})\}+2$? in jo potrdimo za določene razrede grafov.
Keywords: barvanje povezav; graf brez trizobov; ravninski graf; razlikovalni indeks; zlom simetrije v grafu