On clique immersions in line graphs (Q2005686): Difference between revisions

A pair of adjacent edges \(uv\) and \(vw\) in a graph are split off from their common vertex \(v\) by deleting the edges \(uv\) and \(vw\), and adding the edge \(uw\) (unless it forms a loop, i.e., \(u=w\)). Given graphs \(G\), \(H\), we say that \(G\) has an \(H\)-immersion if \(H\) can be obtained from a subgraph of \(G\) by splitting off pairs of edges and removing isolated vertices. In this paper, it is shown that for any \(m\geq 2\) if line graph \(L(G)\) immerses \(K_{t}\) then \(L(mG)\) immerses \(K_{mt}\), where \(mG\) is the graph obtained from \(G\) by replacing each edge in \(G\) with a parallel edge of multiplicity \(m\). This implies that if \(G\) is a simple graph, then \(L(mG)\) satisfies a conjecture of \textit{F. N. Abu-Khzam} and \textit{M. A. Langston} [Lect. Notes Comput. Sci. 2697, 394--403 (2003; Zbl 1276.05042)]. Another result is that when \(G\) is a line graph, \(G\) has a \(K_{t}\)-immersion iff \(G\) has a \(K_{t}\)-minor whenever \(t\leq 4\), but this equivalence fails in both directions when \(t\geq 5\).