On clique immersions in line graphs

DOI10.1016/J.DISC.2020.112095zbMATH Open1448.05169arXiv1909.07964OpenAlexW3081920013MaRDI QIDQ2005686FDOQ2005686

Jessica McDonald, Michael Guyer

Publication date: 8 October 2020

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: We prove that if $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 when $G$ is a simple graph, $L(mG)$ 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 $tleq4$, but this equivalence fails in both directions when $tgeq5$.

Full work available at URL: https://arxiv.org/abs/1909.07964

Recommendations

• A minimum degree condition forcing complete graph immersion
• Clique immersion in graphs without a fixed bipartite graph
• Complete graph immersions in dense graphs
• Clique immersion in graph products
• Immersing small complete graphs

zbMATH Keywords

line graphcliqueimmersion

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Graph theory
• Characterizations of derived graphs
• Hadwiger's conjecture for \(K_ 6\)-free graphs
• Title not available (Why is that?)
• Graph Coloring and the Immersion Order
• Immersing small complete graphs
• Graph minors XXIII. Nash-Williams' immersion conjecture
• Hajós' conjecture for line graphs
• Hadwiger's conjecture for line graphs
• Graphe représentatif des aretes d'un multigraphe
• A structure theorem for strong immersions
• Forcing clique immersions through chromatic number

Cited In (6)

• Clique immersions in graphs of independence number two with certain forbidden subgraphs
• A note on the immersion number of generalized Mycielski graphs
• On the Number of Cliques in Graphs with a Forbidden Subdivision or Immersion
• A note on clique immersion of strong product graphs
• Clique immersion in graph products
• Totally odd immersions in line graphs

This page was built for publication: On clique immersions in line graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2005686)