Batas Atas untuk Scrambling Index dari Graf Primitif

Abstract

The scrambling index of a primitive graph G, k(G), is the least positive integer k such that for each pair of distinct vertices u and v there is a vertex w with the property that there are u k ! w and v k ! w walk. For a primitive graph G with n vertices and smallest odd cycle of length s it is known that k(G) (s −1)/2 + (n −s). Let d{v,Cs} be the distance of the vertex v to the cycle Cs, so maxv2V d{v,Cs} n−s. This paper show that k(G) (s−1)/2+maxv2V d{v,Cs}. This paper also discuss family of primitive graphs whose scrambling index are (s − 1)/2 + maxv2V d{v,Cs}.

Scrambling index dari graf primitif G, k(G), adalah bilangan bulat positif terkecil k, sehingga untuk setiap pasangan titik u, v terdapat titik w sedemikian sehingga ter- dapat jalan u k ! w dan v k ! w. Untuk graf primitif G dengan n titik dan cycle ganjil terkecil Cs sepanjang s diketahui bahwa k(G) (s−1)/2+(n−s). Andaikan d{v,Cs} merupakan jarak dari titik v ke cycle Cs, maka maxv2V d{v,Cs} n − s. Tulisan ini memperlihatkan bahwa k(G) (s − 1)/2 + maxv2V d{v,Cs}. Tulisan ini juga membahas family dari graf primitif yang scrambling indexnya merupakan (s − 1)/2 + maxv2V d{v,Cs}.