The Clustering Coefficient for Graph Products

Abstract

The clustering coefficient of a vertex v, of degree at least 2, in a graph Γ is obtained using the formula C(v)=2t(v)deg(v)(deg(v)−1), where t(v) denotes the number of triangles of the graph containing v as a vertex, and the clustering coefficient of Γ is defined as the average of the clustering coefficient of all vertices of Γ, that is, C(Γ)=1|V|∑v∈VC(v), where V is the vertex set of the graph. In this paper, we give explicit expressions for the clustering coefficient of corona and lexicographic products, as well as for the Cartesian sum; such expressions are given in terms of the order and size of factors, and the degree and number of triangles of vertices in each factor.

Keywords

• clustering coefficient
• graph product
• corona product
• lexicographic product
• Cartesian sum