GRAPHS COSPECTRAL WITH MULTICONE GRAPHS $K_w \nabla L(P)$

NEW

Problem: Reconstructed statement. Let $P$ be the Petersen graph, $L(P)$ its line graph, $K_w$ the complete graph on $w$ vertices, and $\nabla$ the graph join. For every integer $w\ge 0$, the graph

$$\overline{K_w\nabla L(P)}$$

is determined by its signless Laplacian spectrum among finite simple graphs.

This matches the paper title and the standard notation $L(P)$ for the line graph of the Petersen graph. Since

$$\overline{K_w\nabla L(P)}=wK_1\sqcup \overline{L(P)},$$

the conjecture is about the signless Laplacian spectrum of this disconnected graph.

Result: The conjecture is true.

Let $H=\overline{L(P)}$. The Petersen graph has adjacency spectrum

$$3,1^5,(-2)^4.$$

Since $P$ is cubic with $10$ vertices and $15$ edges,

$$\operatorname{Spec}_A(L(P))=\{4,2^5,(-1)^4,(-2)^5\}.$$

Thus $H$ is $10$-regular on $15$ vertices with

$$\operatorname{Spec}_A(H)=\{10,1^5,0^4,(-3)^5\}.$$

Hence

$$\operatorname{Spec}_Q(H)=\{20,11^5,10^4,7^5\},$$

and

$$\operatorname{Spec}_Q(wK_1\sqcup H)=\{20,11^5,10^4,7^5,0^w\}.$$

Let $G$ be any graph with this $Q$-spectrum. The multiplicity of $0$ as a signless Laplacian eigenvalue equals the number of bipartite connected components, because

$$x^{T}Qx=\sum_{uv\in E(G)}(x_u+x_v)^2.$$

Therefore $G$ has exactly $w$ bipartite components.

We first show these bipartite components are isolated vertices. Suppose $B$ is a nontrivial connected bipartite component. Since $Q(B)$ is similar to the Laplacian $L(B)$, its positive eigenvalues are chosen from

$$\{20,11^5,10^4,7^5\}.$$

If $20$ occurred as an eigenvalue of $B$, then the largest Laplacian eigenvalue of $B$ would be $20$, but for a graph on $s$ vertices every Laplacian eigenvalue is at most $s$. Since $B$ has at most $16$ vertices, this is impossible.

Thus all positive Laplacian eigenvalues of $B$ lie in $\{7,10,11\}$, so its algebraic connectivity is at least $7$. For a connected noncomplete graph, the algebraic connectivity is at most the minimum degree, hence $\delta(B)\ge 7$. If $B$ has bipartition $(X,Y)$, then $|X|,|Y|\ge 7$. Since $B$ has at most $15$ vertices, either $(|X|,|Y|)=(7,7)$ or $(7,8)$. In the first case $B=K_{7,7}$, whose Laplacian spectrum contains $14$; in the second $B=K_{7,8}$, whose Laplacian spectrum contains $15$ and $8$. Neither is allowed. Therefore all bipartite components are isolated.

So $G=wK_1\sqcup Y$, where $Y$ has $15$ vertices and

$$\operatorname{Spec}_Q(Y)=\{20,11^5,10^4,7^5\}.$$

From the spectrum,

$$2m(Y)=20+5\cdot 11+4\cdot 10+5\cdot 7=150,$$

so $m(Y)=75$. Also

$$\operatorname{tr}(Q(Y)^2)=20^2+5\cdot 11^2+4\cdot 10^2+5\cdot 7^2=1650.$$

Since $\operatorname{tr}(Q^2)=2m+\sum_v d(v)^2$, we get

$$\sum_v d(v)^2=1500.$$

But

$$\left(\sum_v d(v)\right)^2=150^2=15\cdot 1500,$$

so equality holds in Cauchy–Schwarz, and every vertex of $Y$ has degree $10$. Hence

$$\operatorname{Spec}_A(Y)=\{10,1^5,0^4,(-3)^5\}.$$

Let $Z=\overline{Y}$. Then $Z$ is $4$-regular on $15$ vertices with

$$\operatorname{Spec}_A(Z)=\{4,2^5,(-1)^4,(-2)^5\}.$$

We show $Z\cong L(P)$.

From the spectrum,

$$\operatorname{tr}(A_Z^3)=4^3+5\cdot 2^3+4(-1)^3+5(-2)^3=60,$$

so $Z$ has $10$ triangles. Also

$$\operatorname{tr}(A_Z^4)=4^4+5\cdot 2^4+4(-1)^4+5(-2)^4=420.$$

For a $4$-regular graph on $15$ vertices,

$$\operatorname{tr}(A^4)=2m+4\sum_v\binom{d(v)}2+8C_4=60+360+8C_4,$$

so $C_4=0$. Thus $Z$ has no $4$-cycles.

Every edge of $Z$ lies in at most one triangle, since two common neighbors of an edge would create a $4$-cycle. But $Z$ has $30$ edges and $10$ triangles, so every edge lies in exactly one triangle. The triangles of $Z$ therefore form an edge partition.

Construct a graph $B$ whose vertices are the $10$ triangles of $Z$, and whose edges are the vertices of $Z$: a vertex $x\in V(Z)$ lies in exactly two triangles, so it joins those two triangle-vertices in $B$. Then $B$ is a simple cubic graph on $10$ vertices, and by construction

$$Z\cong L(B).$$

The line-graph spectrum relation for a cubic graph gives

$$\operatorname{Spec}_A(B)=\{3,1^5,(-2)^4\}.$$

Thus $B$ is a connected $3$-regular graph with exactly three adjacency eigenvalues, hence strongly regular with parameters

$$(10,3,0,1).$$

The unique graph with these parameters is the Petersen graph. Therefore $B\cong P$, so

$$Z\cong L(P),$$

and hence

$$Y\cong \overline{L(P)}.$$

Consequently

$$G\cong wK_1\sqcup \overline{L(P)} =\overline{K_w\nabla L(P)}.$$

Therefore $\overline{K_w\nabla L(P)}$ is determined by its signless Laplacian spectrum.

Citation: No external resolution is used; the proof above is self-contained apart from standard elementary spectral facts proved or verified in the argument.