On clique immersions in line graphs
2020
Abstract We prove that if L ( G ) immerses K t then L ( m G ) immerses K m t , where m G is the graph obtained from G by replacing each edge in G with a parallel edge of multiplicity m . This implies that when G is a simple graph, L ( m G ) satisfies a conjecture of Abu-Khzam and Langston. We also show that when G is a line graph, G has a K t -immersion iff G has a K t -minor whenever t ≤ 4 , but this equivalence fails in both directions when t ≥ 5 .
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
11
References
3
Citations
NaN
KQI