Obravnavamo barvanja povezav, ne nujno pravilna. Razlikovalni indeks ?$D'(G)$? grafa ?$G$? je najmanjše število barv v barvanju povezav, ki ga ohranja samo identični avtomorfizem. Znano je, da je ?$D'(G) \le \Delta$? za vsak števen, povezan graf ?$G$? s končno maksimalno stopnjo ?$\Delta$? razen za tri majhne cikle. Dokažemo, da je ?$D'(G) \le \lceil\sqrt{\Delta}\rceil+1$? ob dodatnem pogoju, da graf ?$G$? nima visečih povezav.

Pravice

URN

URN:NBN:SI:DOC-O5XMSQF0

COBISSID

39629315

Objavljeno

28.04.2021

Metapodatki

Citiranje

APA:

Imrich, Wilfried, Kalinowski, Rafał, Pilśniak, Monika, Woźniak, Mariusz (2020). The distinguishing index of connected graphs without pendant edges. Ars mathematica contemporanea, letnik 18, številka 1, str. 117-126. URN:NBN:SI:DOC-O5XMSQF0 from http://www.dlib.si

MLA:

Imrich, Wilfried, Kalinowski, Rafał, Pilśniak, Monika, Woźniak, Mariusz. "The distinguishing index of connected graphs without pendant edges." Ars mathematica contemporanea letnik 18. številka 1 (2020) str. 117-126.
<http://www.dlib.si/?URN=URN:NBN:SI:DOC-O5XMSQF0>

Ars mathematica contemporanea
2008-
(Zbirni zapis)