Panjang Cycle dari Graf Jarang

Abstract

Let G be a d-reguler graph with n-vertices and girth g. Set of cycle length in graph G is denoted by C(G). Graph G is a sparse graph if and only if the ratio of the number of edges in the graph and the number of maximum edges is 1 2 . Sparsity of a graph can be indicated by a large girth. The less the number of edge is, the longer the path should be travelled by a graph to form a cycle. Therefore, the girth become larger. Furthermore, it was obtained the number of cycle length of sparse graph which denoted |C(G)| is a function of d and g.