Graf Primitif Jarang dengan Scrambling Index 1

Abstract

A connected graph G is primitive there is a positive integer k such that for every pair of vertices u and v there is a walk of length k from vertex u to vertex v. Scrambling index of a primitive graph G, denoted by k(G), is the smallest positive integer k such that for every pair of vertices u and v there is a vertex w such that we can get to w from u and v in G using a walk of length k. This paper discusses necessary and sufficient conditions for primitive graph with scrambling index 1. And than a primitive graph with n ≥ 3 vertices and scrambling index 1, the minimum number of edge is 3n−3 2 if n is odd and 3n−2 2 if n is even.