345 KB24 KB200820252021Pilśniak, Monikaštevilka:2letnik:20str. 223-231DOI:10.26493/1855-3974.2173.71aISSN:1855-3966COBISSID_HOST:92014595URN:URN:NBN:SI:doc-UJ744LW5enUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneadistinguishing indexmeje Nordhaus-Gaddumovega tipaNordhaus-Gaddum type boundsrazlikovalni indekssymmetry breaking in graphszlom simetrije v grafihNordhaus-Gaddum type inequalities for the distinguishing index|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 nontrivial automorphism. This invariant is defined for any graph without ?$K_2$? as a connected component and without two isolated vertices, and such a graph is called admissible. We prove the Nordhaus-Gaddum type relation: ?$$2 \le D'(G) + D'(\overline{G}) \le \Delta (G)+2$$? for every admissible connected graph ?$G$? of order ?$|G|\ge 7$? such that ?$\overline{G}$? is also admissibleRazlikovalni 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 \Delta (G)+2$$? za vsak dopusten povezan graf ?$G$? reda ?$|G|\ge 7$?, ki izpolnjuje dodaten pogoj, da je tudi ?$\overline{G}$? dopusten grafTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije