319 KB23 KB200820252020Imrich, WilfriedKalinowski, RafałPilśniak, MonikaWoźniak, Mariuszštevilka:1letnik:18str. 117-126ISSN:1855-3966COBISSID_HOST:39629315URN:URN:NBN:SI:doc-O5XMSQF0enUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneadistinguishing index of a graphrazlikovalni indeks grafasymmetry breakingzlom simetrijeThe distinguishing index of connected graphs without pendant edges|We consider edge colourings, not necessarily proper. The distinguishing index ?$D'(G)$? of a graph ?$G$? is the least number of colours in an edge colouring that is preserved only by the identity automorphism. It is known that ?$D'(G) \le \Delta$? for every countable, connected graph ?$G$? with finite maximum degree ?$\Delta$? except for three small cycles. We prove that ?$D'(G) \le \lceil\sqrt{\Delta}\rceil+1$? if additionally ?$G$? does not have pendant edgesObravnavamo 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 povezavTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije