Is L(H) = L(G) :: Is line graph of a hypergraph is also a line graph of a graph ??

68 Views Asked by At

The line graph of a hypergraph is the graph whose vertex set is the set of the hyperedges of the hypergraph $\{E_1,...E_m\}$, with two hyperedges adjacent when they have a nonempty intersection.

My question if $G$ is a line graph of some hypergraph $H$, is $G$ also a line graph of some other graph $G'$ ?

I'm pretty sure that this question has a positive answer, but I do not know how to prove it.

Any idea will be useful!

1

There are 1 best solutions below

2
On BEST ANSWER

No. $K_{1,3}$ is the line graph of the hypergraph $(\{v_1,v_2,v_3\},\{\{v_1,v_2,v_3\},\{v_1\},\{v_2\},\{v_3\}\})$ but by Beineke's characterization of line graphs it is not the line graph of any graph.