prove that the only solution for the equation $L(G)=H \square K$ is $K=K_n$ ,$H=K_m$ and $G=K_{m,n}$.

188 Views Asked by At

suppose that $G$,$H$,$K$ are connected graphs with at least two vertices,prove that the only solution of the equation $L(G)=H \square K$ is $K=K_n$ ,$H=K_m$ and $G=K_{m,n}$.

because the eigenvalue of any line graph $L(G)$ is not fewer than -2 (as a theorem),if we suppose that $K$ and $H$ will be some thing else,some how I must make a contradiction. but I can't make it.

I don't what to do,any hint or guidance me to be in right way will be great ,thanks.

1

There are 1 best solutions below

3
On BEST ANSWER

You do not make clear if you are required to use an algebraic approach. There is a simple `elementary' solution.

Assume vertices $x$ and $y$ in $H$ are not adjacent. Let $P$ be a shortest $x,y$-path in $H$, $P=(x,a,b,\ldots,y)$ (where $a\ne y$, but $b$ may be equal to $y$). Now let $p$ and $q$ be two adjacent vertices in $K$ (these exist, because $K$ is connected and has at least two vertices).

Then the four vertices $(x,p),(a,p),(b,p),(a,q)$ of $H\square K$ induce a claw ($K_{1,3}$) and it is a trivial exercise to show that a linegraph cannot contain an induced claw.

So all vertices of $H$ must be adjacent. Now you can finish the proof :)