GRAPHS COSPECTRAL WITH MULTICONE GRAPHS K_w ∇ 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

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

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

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

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

Hence

and

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

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

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

From the spectrum,

so $m(Y)=75$. Also

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

But

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

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

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

From the spectrum,

so $Z$ has $10$ triangles. Also

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

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

The line-graph spectrum relation for a cubic graph gives

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

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

and hence

Consequently

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.