3
$\begingroup$

Let $\widehat{G}$ be the graph obtained by adding a vertex to a graph $G$ and joining it to all vertices in $V(G)$. Let $\sigma(G)$ be the number of non-positive eigenvalues of the adjacency matrix of $G$. By the interlacing theorem we have that $$\sigma(\widehat{G}) \in \{ \sigma(G), \sigma(G)+1\}\,.$$

Let us say that $G$ is inertia friendly whenever $\sigma(\widehat{G}) = \sigma(G)+1$. Making a simple computation it is not hard to see that any $r$-regular graph $(r > 0)$ is inertia friendly and so are all connected graphs on up to $4$ vertices.

The only two connected graphs of order $5$ that are not inertia-friendly are the $5$-path $P_5$ and the bull graph. Computing the sequence of connected graphs that are not inertia friendly one obtains the numbers $0,0,0,0,2,10,131,1580,42228,\ldots$

Given these lists its easy to verify that all the graphs have $P_4$ as an induced subgraph. Hence I wonder

Is it obvious that every cograph is inertia friendly?

It seems that a high proportion of connected graphs is inertia-friendly hence I wonder whether its possible to establish any other non-trivial properties about such graphs

What are some structural properties of inertia-friendly graphs?

I would like to understand inertia-friendly graphs so any property that distinguishes them is useful.

Note. The characteristic polynomial of $\widehat{G}$ is given by $$p_{\widehat{G}}(x) = (x+1)p_{G}(x) + (-1)^{n+1} p_{\overline{G}}(-x-1)\,,$$ where $n$ is the order of $G$.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Given a cograph $G$ it can be shown by induction (on the order of $G$) that $\widehat{G}$ (as defined above) has exactly one more negative eigenvalue than $G$.

Useful facts:

  • All cographs have a pair of vertices with either the same open or closed neighborhoods, respectively duplicate and coduplicate vertices.

  • No cograph has an eigenvalue in the range (-1,0).

  • Deletion of a duplicate vertex decreases the multiplicity of 0 in the resulting graph by 1.

  • Deletion of a coduplicate vertex decreases the multiplicity of -1 in the resulting graph by 1.

  • The rank of a cograph is equal to the number of distinct non zero rows.

  • Interlacing

A corollary is that all cographs without isolated vertices are inertia friendly.

What was your motivation for considering inertia-friendly graphs?

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .