Clique structure and other network properties of the tensor product of Erdős–Rényi graphs

Işlak Ü., İncekara B.

Brazilian Journal of Probability and Statistics, vol.39, no.2, pp.185-203, 2025 (SCI-Expanded, Scopus) identifier

  • Publication Type: Article / Article
  • Volume: 39 Issue: 2
  • Publication Date: 2025
  • Doi Number: 10.1214/25-bjps630
  • Journal Name: Brazilian Journal of Probability and Statistics
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, zbMATH
  • Page Numbers: pp.185-203
  • Keywords: clique, clustering coefficient, Erdős–Rényi graph, graph product, Random graph
  • Middle East Technical University Affiliated: Yes

Abstract

We analyze the number of cliques of given size and the size of the largest clique in tensor product G × H of two Erdős–Rényi graphs G and H. Then an extended clustering coefficient is introduced and is studied for G × H. Restriction to the standard clustering coefficient has a direct relation to the local efficiency of the graph, and the results are also interpreted in terms of the efficiency. As a last statistic of interest, the number of isolated vertices is analyzed for G × H.