Structural Equivalence in Graphs and Complete Skeletons

MaRDI QIDQ6354404zbMATH OpenFDO

Authors Jonathan Higgins

Publication date 23 November 2020

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: Two vertices $u$ and $v$ of a graph $Gamma$ are strucuturally equivalent if and only if the transposition $(u,v)$ is in Aut($Gamma$), the automorphism group of $Gamma$. Some properties of structural equivalence and the group of vertex permutations generated by the transpositions in Aut($Gamma$) are discussed, along with the prime graphs of these groups. The notion of structural equivalence is used to develop a way of reconfiguring graphs into what are called their complete skeletons, which is closely related to compression graphs. Finally, the complete skeleton of a graph $Gamma$, denoted $Omega(Gamma)$, is used to find a formula for rank$(I+A(Gamma))$, which is helpful for determining the multiplicity of the -1 eigenvalue of $Gamma$.

This page was built for publication: Structural Equivalence in Graphs and Complete Skeletons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6354404)