724 KB55 KB200820252017Balachandran, NiranjanPadinhatteeri, Sajithštevilka:1letnik:12str. 89-109COBISSID:18095193ISSN:1855-3966URN:URN:NBN:SI:doc-RGSSIJL4enUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneagrupa avtomorfizmov grafalema o gibanjurazlikovalno kromatsko številošibki produkt grafovChisubD(G), |Aut(G)|, and a variant of the Motion Lemma|The Distinguishing Chromatic Number of a graph ?$G$?, denoted ?${\chi_D}(G)$?, was first defined in K. L. Collins and A. N. Trenk, The distinguishing chromatic number, Electron. J. Combin. 13 (2006), R16, as the minimum number of colors needed to properly color ?$G$? such that no non-trivial automorphism ?$\phi$? of the graph ?$G$? fixes each color class of ?$G$?. In this paper, (1) We prove a lemma that may be considered a variant of the Motion lemma of A. Russell and R. Sundaram, A note on the asympotics and computational complexity of graph distinguishability, Electron. J. Combin. 5 (1998), R23 and use this to give examples of several families of graphs which satisfy ?$\chi_D(G) = \chi(G) +1$?. (2) We give an example of families of graphs that admit large automorphism groups in which every proper coloring is distinguishing. We also describe families of graphs with (relatively) very small automorphism groups which satisfy ?$\chi_D(G) = \chi(G + 1$?, for arbitrarily large values of ?$\chi(G)$?. (3) We describe non-trivial families of bipartite graphs that satisfy ?$\chi D(G > r$? for any positive integer ?$r$?Razlikovalno kromatsko število grafa ?$G$?, označeno z ?${\chi_D}(G)$?, je bilo najprej definirano kot minimalno število barv, potrebnih za pravilno barvanje grafa ?$G$?, pri katerem noben netrivialen avtomorfizem ?$\phi$? grafa ?$G$? ne fiksira vsakega barvnega razreda grafa ?$G$?. V tem članku: (1.) dokažemo lemo, ki jo lahko imamo za različico leme o gibanju in z njeno pomočjo konstruiramo primere različnih družin grafov, ki zadoščajo pogoju ?$\chi_D(G) = \chi(G) +1 $?. (2.) podamo primer družin grafov, ki dopuščajo velike grupe avtomorfizmov, v katerih je vsako pravo barvanje razlikovalno. Opišemo tudi družine grafov z (relativno) zelo majhnimi grupami automorfizmov, ki zadoščajo pogoju ?$\chi_D(G) = \chi(G) +1 $?, za poljubno velike vrednosti ?$\chi(G)$?. (3.) opišemo netrivialne družine dvodelnih grafov, ki zadoščajo pogoju ?$\chi D(G > r$? za vsako pozitivno celo število ?$r$?TEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije