Primitive graphs with small exponent and small scrambling index

4th International Conference on Operational Research

Surbakti, Ita Y.^1 ; Suwilo, Saib^1 ; Butar-Butar, Ericha A.^1 ; Oktaviani, Helda^1

Department of Mathematics, Universitas Sumatera Utara, Medan

20155, Indonesia^1

关键词: Connected graph;    Edge-sets;    Graph G;    N cycles;    Positive integers;    Scrambling indices;    Vertex set;   

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

来源: IOP

【 摘 要 】

A connected graph G is primitive provide there is a positive integer k such that for each pair of vertices u and v there is a uv-walk of length k. The smallest of such positive integer k is the exponent of G and is denoted by exp(G). The scrambling index of a primitive graph G, denoted by k(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 is a uw-walk and a vw-walk of length k. By an n-chainring CR(n) we mean a graph obtained from an n-cycle by replacing each edge of the n-cycle by a triangle. By a (q,p)-dory, D(q,p), we mean a graph with vertex set V(D(q,p)) = V(Pq× Pp) ∪ {w1, w2} and edge set E(D(q,p)) = E(Pq× Pp) ∪ {w1- (ui,v1) : i = 1, 2,, q}∪{w2-(ui,vp) : i = 1, 2,, q}, where Pnis a path on n vertices. We discus the exponent and scrambling index of an n- chainring and (q, p)-dory. We present formulae for exponent and scrambling index in terms of their diameter.