|
A graph is called rainbow if each of its edges has a di erent color. Anti-Ramsey numer ar(G;H) is the maximum number of colors such that we are able to color the edges of a graph Gwith this number of colors without creating any rainbow copy of H. It was de ned in [1] and since then widely studied. The results for a variety of pairs of graphs can be found in [2]. Hanoi graphs Hⁿp are the graph theoretical model of well-known Towers of Hanoi puzzle with p pegs and n discs. The vertices of the graph are permissible states of discs on pegs, coded by the appropriate integer sequences, and the two vertices are adjacent if and only if there is a legal move from one state to another. This model was proposed firstly in [4] for classical puzzle with three discs. It occurs that some of graph properties and parameters, such as hamiltonicity, planarity, chromatic chromatic number and index, are not dificult to establish for Hanoi graphs in general case. The survey of known results can be found in [3]. In the talk we will consider ar(Hⁿp;Hmq) for various values of p;n;q;m. Among others we will show the exact value for ar(Hnp;Hmp),m≤n.
|
