Distinguishing numbers of finite 4-valent vertex-transitive graphs - Lehner, Florian (Ars mathematica contemporanea, 2020)
Razlikovalno š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 2.
Keywords: barvanje točk; distinguishing number; razlikovalno število; symmetry breaking in graph; vertex colouring; vertex-transitive graphs; vozliščno tranzitivni grafi; zlom simetrije v grafu