On joins of a clique and a co-clique as star complements in regular graphs

preprint2022arXivOpen access

Abstract

In this paper we consider rr-regular graphs GG that admit the vertex set partition such that one of the induced subgraphs is the join of an ss-vertex clique and a tt-vertex co-clique and represents a star complement for an eigenvalue μμ of GG. The cases in which one of the parameters s,ts, t is less than 2 or μ=rμ=r are already resolved. It is conjectured in [J. Wang, X. Yuan, L. Liu, Regular graphs with a prescribed complete multipartite graph as a star complement, Linear Algebra Appl.~579 (2019) 302--319] that if s,t≥2s, t\geq 2 and μ≠rμ\neq r, then μ=−2,t=2μ=-2, t=2 and G=(s+1)K2‾G=\overline{(s+1)K_2}. For μ=−tμ=-t we verify this conjecture to be true. We further study the case in which μ≠−tμ\neq-t and confirm the conjecture provided t2−4μ2t−4μ3=0t^2-4μ^2t-4μ^3=0. For the remaining possibility we determine the structure of a putative counterexample and relate its existence to the existence of a particular 2-class block design. It occurs that the smallest counterexample would have 1265 vertices.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.