2025/07/22 by Wang, Wei, Huang, Ximei
#05C50 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2507.16730
Complement-reducible graphs (or cographs) are the graphs formed from the single-vertex graph by the operations of complement and disjoint union. By combining the Johnson-Newman theorem on generalized cospectrality with the standard tools in the asymptotic enumeration of trees, we show that almost all cographs have a cospectral mate. This result can be viewed as an analogue to a well-known result by Schwenk, who proved that almost all trees have a cospectral mate.