Finding the edge ranking number through vertex partitions
An edge coloring c?:E?{1,2,,t} c ? : E ? { 1 , 2 ,  , t } of a graph G=(V,E) G = ( V , E ) is an edge t t -ranking if for any two edges of the same color, every path between them contains an intermediate edge with a larger color. The edge ranking number ? r ? ( G ) is the smallest value of t t such that G G has an edge t t -ranking. In this paper, we introduce a relation between edge ranking number and vertex partitions. By using the proposed recurrence formula, we show that the edge ranking number of the Sierpi?ski graph ? r ? ( S ( n , k ) ) = n ? r ? ( K k ) for any n,k?2 n , k ? 2 where Kk K k denotes a complete graph of k k vertices.
edge ranking vertex partitions coloring sierpi?ski graphs