280 KB40 KB200820252020Lehner, FlorianVerret, Gabrielletnik:19številka:2str. 173-187ISSN:1855-3974COBISSID_HOST:43995651URN:URN:NBN:SI:doc-XA9F52TIenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneabarvanje točkdistinguishing numberrazlikovalno številosymmetry breaking in graphvertex colouringvertex-transitive graphsvozliščno tranzitivni grafizlom simetrije v grafuDistinguishing numbers of finite 4-valent vertex-transitive graphs|The distinguishing number of a graph ?$G$? is the smallest ?$k$? such that ?$G$? admits a ?$k$?-colouring for which the only colour-preserving automorphism of ?$G$? is the identity. We determine the distinguishing number of finite 4-valent vertex-transitive graphs. We show that, apart from one infinite family and finitely many examples, they all have distinguishing number 2Razlikovalno število ?$G$? je najmanjše število ?$k$?, pri katerem obstaja ?$k$?-barvanje grafa ?$G$? z lastnostjo, da je edini avtomorfizem grafa ?$G$?, ki ohranja barve, identiteta. Določimo razlikovalno število končnih 4-valentnih vozliščno tranzitivnih grafov. Dokažemo, da imajo, razen ene neskončne družine ter še končno mnogo izjem, vsi ti grafi razlikovalno število 2TEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije