Razlikovalni indeks grafa ?$G$?, označen z ?$D^\prime(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^\prime(G)\geq \Delta(G)$?. Pokažemo da je ?$D^\prime(G)\leq 2$?, če je ?$G$? sledljiv graf reda najmanj sedem, in da je ?$D^\prime(G)\leq 3$? če je ?$G$? bodisi brez trizobov ali pa je 3-povezan in planaren. Raziskujemo tudi relacijo tipa Nordhaus-Gaddum: ?$2\leq D^\prime(G)+D^\prime(\overline{G})\leq \max\{\Delta(G),\Delta(\overline{G})\}+2$? in jo potrdimo za določene razrede grafov.

Pravice

URN

URN:NBN:SI:DOC-ENFNC271

COBISSID

18354777

Objavljeno

29.05.2020

Metapodatki

Citiranje

APA:

Pilśniak, Monika (2017). Improving upper bounds for the distinguishing index. Ars mathematica contemporanea, letnik 13, številka 2, str. 259-274. URN:NBN:SI:DOC-ENFNC271 from http://www.dlib.si

MLA:

Pilśniak, Monika. "Improving upper bounds for the distinguishing index." Ars mathematica contemporanea letnik 13. številka 2 (2017) str. 259-274.
<http://www.dlib.si/?URN=URN:NBN:SI:DOC-ENFNC271>

Ars mathematica contemporanea
2008-
(Zbirni zapis)