2
$\begingroup$

Let $G$ be a simple graph. We say this graph is self-index complementary ($SIC$) if $\lambda_1 (G)=\lambda_1 (\overline{G})$, where $\lambda_1(G)$ denotes the index of the adjacency matrix of the graph $G$. Index of a graph is its maximum eigenvalue.

In this case, I am not interested in the regular graphs. I found a method to generate an infinite family of irregular graphs which are $SIC$.

During my examination, I observed that such graphs have special structures. One of this property is as follow:

If $G$ is $SIC$ then it has at most two connected components.

I found all $SIC$ graphs up to $9$ vertices and the data verify the conjecture.

My question is: Is there any proof for this observation or is there any counter example?

Improve this question
$\endgroup$
2
  • $\begingroup$ Suppose $G$ has complete graphs $K_{p_1},\dots,K_{p_k}$ as its components where $k\geq 3$ and $p_1>p_2\geq\dots\geq p_k$. Then $G$ is not regular, has the complete multipartite graph $K_{p_1,\dots,p_k}$ as its complement, and $\lambda(G)=p_1-1$. The characteristic polynomial of $K_{p_1,\dots,p_k}$ is known: sciencedirect.com/science/article/pii/S0012365X1100327X. Can you arrange for $p_2,\dots,p_k\in\{0,1,\dots,p_1-1\}$ so that $p_1-1$ is a root of the polynomial appeared in that paper? $\endgroup$
    – KhashF
    Commented Mar 27, 2020 at 19:44
  • $\begingroup$ I do not think this method works, since the number of edges effects on the largest eigenvalue, and I think in the first place we must control the number of edges and triangles in both graphs and its complements. $\endgroup$
    – Shahrooz
    Commented Mar 27, 2020 at 19:51

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .