All the eigenvalues of an integral graphs are integers. Integral graphs are extremely rare. They form an asymptotically vanishing fraction $2^{-\Omega(n)}$ among all graphs on $n$ vertices. It makes the construction of a new family of integral graphs a challenging task. Also, most of the known infinite family of integral graphs rely on Cayley graphs over Abelian groups. In this article, we introduce a new family of integral graphs obtained from the groups. The construction of our graphs from groups is different from the construction of Cayley graphs. A spectral uniqueness theorem is established, which shows that each member of the infinite family is determined by its adjacency spectrum among all finite simple graphs. We also present recursive constructions that generates larger members of the family from smaller ones, providing a scalable class of integral graphs. Finally, we investigate algebraic realizations of these graphs as complements of Proper Prime Order Element Graphs of finite $2$-groups and obtain conditions characterizing such realizations. We also observe that the graphs obtained from different non-isomorphic groups have cospectral graphs.
The inducibility problem asks for the maximum number of induced copies of a fixed graph among all graphs with a prescribed number of vertices. Inducibility has been an active area of research in extremal combinatorics, but determining all extremal graphs for explicitly defined patterns remains challenging, particularly...
Graphs defined on groups, such as power graphs, enhanced power graphs and commuting graphs, form a hierarchy under inclusion of edge sets. We develop an analogous theory for topological spaces. To a space X we attach five graphs on the vertex set X, all invariant under homeomorphisms: the specialization, inseparability...
The generating graph $\Gamma(G)$ of a group $G$ is the graph whose vertex set is $G$, where two distinct vertices are adjacent if and only if they generate $G$. In this paper, we systematically study the structure of generating graphs of finite abelian groups (non-cyclic) and determine the set of all generating pairs....
Haemers'conjecture for the generalized spectrum asserts that almost all graphs are determined by their generalized spectrum, that is, for almost all graphs $G$, every graph with the same spectrum as $G$ whose complement has the same spectrum as the complement of $G$ is isomorphic to $G$. We prove this conjecture by sho...
Let G be a finite group and let {\cal P}_e(G) denote its enhanced power graph. Thus two distinct group elements are adjacent whenever they lie in a common cyclic subgroup. This paper studies the algebraic connectivity of {\cal P}_e(G), that is, the second smallest eigenvalue of its Laplacian matrix. Since the identity...
Rosalio G. Artes, Allaizah Arcas, Rendon Cruz et al.· International Journal of Mat...· 0 citations
We study which graph classes determine every graph with simple spectrum up to isomorphism by homomorphism counts from their members. We show that such a class has unbounded treewidth and Euler genus and contains a graph with the complete graph on seven vertices as a minor. To prove these conditions, we construct pairs...
Takanori Maehara· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.