Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8897851 | Linear Algebra and its Applications | 2018 | 10 Pages |
Abstract
A class of non-oriented simple graphs is called Seidel switching self-complementary (s.s.c. for short) if the complement of any representing graph is in the same equivalence class. Relating the Seidel adjacency matrix of a graph with a Gram matrix, we introduce the 3-signature (s,t) of a switching class of n-vertex graphs. The numbers s and t are the numbers of positive and negative triples within any representing graph of the class. It appears that, for any s.s.c. class of n-vertex graphs, these numbers are equal, yielding (n3) even. Consequently if nâ¡3(mod4) then there is no s.s.c. class of n-vertex graphs. We also prove that this 3-signature depends only on the spectrum of the adjacency matrix of the graph. We then consider the switching classes of Paley conference graphs with 4k+2 vertices, 4k+1=pα, p an odd prime and α a positive integer. We reprove that these classes are s.s.c. Moreover, it is proven that all 4k-vertex graphs contained in a (4k+2)-vertex Paley conference graph are switching equivalent and their class is still a s.s.c. class. In addition, the 3-signature is generalized in view of obtaining a complete invariant of switching classes up to order 8.
Related Topics
Physical Sciences and Engineering
Mathematics
Algebra and Number Theory
Authors
Boumediene Et-Taoui, Augustin Fruchard,