280 KB28 KB200820252016Kalinowski, RafałPilśniak, MonikaWoźniak, Mariuszštevilka:1letnik:11str. 79-89COBISSID:17841241ISSN:1855-3966URN:URN:NBN:SI:doc-12L1O0R1enUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneasymmetry breaking in graphstotal colourings of graphstotal distinguishing chromatic numbertotal distinguishing numbertotalna barvanja grafovtotalno razlikovalno kromatsko številototalno razlikovalno številozlom simetrije v grafihDistinguishing graphs by total colourings|We introduce the total distinguishing number ?$D^{\prime\prime}(G)$? of a graph ?$G$? as the least number ?$d$? such that ?$G$? has a total colouring (not necessarily proper) with ?$d$? colours that is only preserved by the trivial automorphism. This is an analog to the notion of the distinguishing number ?$D(G)$?, and the distinguishing index ?$D^\prime(G)$?, which are defined for colourings of vertices and edges, respectively. We obtain a general sharp upper bound: ?$D^{\prime\prime}(G)\leq \lceil\sqrt{\Delta(G)}\rceil$? for every connected graph ?$G$?. We also introduce the total distinguishing chromatic number ?$\chi^{\prime\prime}_D(G)$? similarly defined for proper total colourings of a graph ?$G$?. We prove that ?$\chi^{\prime\prime}_{D}(G) \leq \chi^{\prime\prime}(G) + 1$? for every connected graph ?$G$? with the total chromatic number ?$\chi^{\prime\prime}(G)$?. Moreover, if ?$\chi^{\prime\prime}(G) \geq\Delta(G) + 2$?, then ?$\chi^{\prime\prime}_{D}(G) = \chi(G)$?. We prove these results by setting sharp upper bounds for the minimal number of colours in a proper total colouring such that each vertex has a distinct set of colour walks emanating from itVpeljemo totalno razlikovalno število ?$D^{\prime\prime}(G)$? grafa ?$G$? kot najmanjše takšno število ?$d$?, da ima ?$G$? totalno barvanje (ne nujno pravilno) z ?$d$? barvami, ki ga ohranja samo trivialni avtomorfizem. Gre za analogijo pojmov razlikovalnega števila ?$D(G)$? in razlikovalnega indeksa ?$D^\prime(G)$?, ki sta definirana za barvanja vozlišč oziroma povezav. Dobimo splošno ostro zgornjo mejo: ?$D^{\prime\prime}(G)\leq \lceil\sqrt{\Delta(G)}\rceil$? za vsak povezan graf ?$G$?. Vpeljemo tudi totalno razlikovalno kromatsko število ?$\chi^{\prime\prime}_D(G)$? definirano podobno za pravilna totalna barvanja grafa ?$G$?. Dokažemo, da je ?$\chi^{\prime\prime}_{D}(G) \leq \chi^{\prime\prime}(G) + 1$? za vsak povezan graf ?$G$? s totalnim kromatskim številom ?$\chi^{\prime\prime}(G)$?. Še več, če je ?$\chi^{\prime\prime}(G) \geq\Delta(G) + 2$?, potem je ?$\chi^{\prime\prime}_{D}(G) = \chi(G)$?. Te rezultate dokažemo tako da določimo ostre zgornje meje za minimalno število barv v pravilnem totalnem barvanju, v katerem iz vsakega vozlišča izhaja drugačna množica barvnih potiTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije