The Spectrum of Weighted Lexicographic Product on Self-Complementary Graphs

Abstract

The lexicographic product, a powerful binary operation in graph theory, offers methods for creating a novel graph by establishing connections between each vertex of one graph and every vertex of another. Beyond its fundamental nature, this operation is found in various applications across computer science disciplines, including network analysis, data mining, and optimization. In this paper, we give a definition of the weight function to the lexicographic product graph $G[H]$ , which enables us to capture the intricate interplay among the vertices of the constituent graphs and facilitate a deeper understanding of their relationships. We derive an expression for the spectrum of $G[H]$ by using the spectrums of $G$ and $H$ if the graph $H$ is a self-complementary graph. Through a systematic analysis and careful computations, we derive a comprehensive expression for the spectrum of $G[H]$ . Remarkably, we reveal an intriguing characteristic pertaining to self-complementarity within the weighted lexicographic product graph. Specifically, we show that the weighted lexicographic product graph can be self-complementary if this graph is a product of two connected weighted self-complementary graphs. Furthermore, we delve into the geometric properties of the lexicographic product, specifically examining the Ricci curvature for the product of two regular graphs. Through rigorous analysis, we have discovered that the lexicographic product of two regular graphs exhibits a lower bound on the Ricci curvature.

Keywords

• Lexicographic product
• self-complementary
• spectrum
• Ricci curvature