Nordhaus-Gaddum type inequalities for the distinguishing index - Pilśniak, Monika (Ars mathematica contemporanea, 2021)
Razlikovalni indeks grafa ?$G$?, označen z ?$D'(G)$?, je najmanjše število barv v barvanju povezav grafa ?$G$?, tako da tega barvanja ne ohranja noben netrivialen avtomorfizem grafa ?$G$?. Ta invarianta je definirana za vsak graf, ki ne vsebuje grafa ?$K_2$? kot povezane komponente, pa tudi ne dveh izoliranih vozlišč; takšnemu grafu pravimo dopusten graf. Dokažemo, da velja naslednja neenakost Nordhaus-Gaddumovega tipa: ?$$2 \le D'(G) + D'(\overline{G}) \le Δ (G)+2$$? za vsak dopusten povezan graf ?$G$? reda ?$|G|\ge 7$?, ki izpolnjuje dodaten pogoj, da je tudi ?$\overline{G}$? dopusten graf.
Keywords: distinguishing index; meje Nordhaus-Gaddumovega tipa; Nordhaus-Gaddum type bounds; razlikovalni indeks; symmetry breaking in graphs; zlom simetrije v grafih