On clique immersions in line graphs

DOI10.1016/J.DISC.2020.112095MaRDI QIDQ2005686zbMATH OpenOpenAlexFDO

Authors Michael Guyer, Jessica McDonald

Publication date 8 October 2020

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

line graphcliqueimmersion

Mathematics Subject Classification ID

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

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$.

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

Cites work

• scientific article; zbMATH DE number 3102312 (Why is no real title available?)
• A structure theorem for strong immersions
• Characterizations of derived graphs
• Graph coloring and the immersion order
• Graph minors XXIII. Nash-Williams' immersion conjecture
• Graph theory
• Graphe représentatif des aretes d'un multigraphe
• Hadwiger's conjecture for \(K_ 6\)-free graphs
• Hadwiger's conjecture for line graphs
• Hajós' conjecture for line graphs
• Immersing small complete graphs

Cited in

(8)

• Clique immersions in graphs of independence number two with certain forbidden subgraphs
• Biclique immersions in graphs with independence number 2
• 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
• Complete bipartite immersion in graphs with independence number two: a simple proof

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)