374 KB45 KB200820252017Pilśniak, Monikaletnik:13številka:2str. 259-274COBISSID:18354777ISSN:1855-3966URN:URN:NBN:SI:doc-ENFNC271enUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneabarvanje povezavgraf brez trizobovravninski grafrazlikovalni indekszlom simetrije v grafuImproving upper bounds for the distinguishing index|The distinguishing index of a graph ?$G$?, denoted by ?$D^\prime(G)$?, is the least number of colours in an edge colouring of ?$G$? not preserved by any non-trivial automorphism. We characterize all connected graphs ?$G$? with ?$D^\prime(G)\geq \Delta(G)$?. We show that ?$D^\prime(G)\leq 2$? if ?$G$? is a traceable graph of order at least seven, and ?$D^\prime(G)\leq 3$? if ?$G$? is either claw-free or 3-connected and planar. We also investigate the Nordhaus-Gaddum type relation: ?$2\leq D^\prime(G)+D^\prime(\overline{G})\leq \max\{\Delta(G),\Delta(\overline{G})\}+2$? and we confirm it for some classes of graphsRazlikovalni 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 grafovTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije