Article ID Journal Published Year Pages File Type
4648713 Discrete Mathematics 2010 7 Pages PDF
Abstract

We say that a regular graph GG of order nn and degree r≥1r≥1 (which is not the complete graph) is strongly regular if there exist non-negative integers ττ and θθ such that |Si∩Sj|=τ|Si∩Sj|=τ for any two adjacent vertices ii and jj, and |Si∩Sj|=θ|Si∩Sj|=θ for any two distinct non-adjacent vertices ii and jj, where SkSk denotes the neighborhood of the vertex kk. We say that a graph GG of order nn is walk regular if and only if its vertex deleted subgraphs Gi=G∖︀iGi=G∖︀i are cospectral for i=1,2,…,ni=1,2,…,n. Let GG be a walk regular graph of order 4k+14k+1 and degree 2k2k which is cospectral to its complement G¯. Let HiHi be switching equivalent to GiGi with respect to Si⊆V(Gi)Si⊆V(Gi). We here prove that GG is strongly regular if and only if Δ(Gi)=Δ(Hi)Δ(Gi)=Δ(Hi) for i=1,2,…,4k+1i=1,2,…,4k+1, where Δ(G)Δ(G) is the number of triangles of a graph GG.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,