Bounds for scrambling index of primitive graphs

4th International Conference on Operational Research

Izar, Shaflina^1 ; Mardiningsih^1 ; Zuhri^2 ; Harleni, Sylvi^3

Department of Mathematics, University of Sumatera Utara, Medan

20155, Indonesia^1

STIM SUKMA Medan, KOPERTIS AREA 1, Medan, Indonesia^2

Fakultas Sains Dan Teknologi, Universitas Islam Negeri Sumatera Utara, Medan, Indonesia^3

关键词: Connected graph;    Graph G;    Maximum distance;    Positive integers;    Scrambling indices;    Upper Bound;   

Others  :  https://iopscience.iop.org/article/10.1088/1757-899X/300/1/012083/pdf
DOI  :  10.1088/1757-899X/300/1/012083

来源: IOP

【 摘 要 】

A connected graph is primitive provided there is a positive integer m such that for each pair of vertices u and v there is a walk of length m connecting u and v. The scrambling index of a primitive graph G is the smallest positive integer k such that for each pair of vertices u and v there is a vertex w such that there exist a walk of length k connecting u and w and a walk of length k connecting v and w. For a primitive graph G with smallest cycle Csof length s, we present an upper bound on the scrambling index of G that depends on s and the maximum distance between vertices in G and the cycle Cs. We then classify the graphs that satisfy the upper bound.