Clique immersion in graph products

2019/08/27 by Karen L. Collins, Collins, Karen L., Megan E. Heenehan +3
Computer Science · Mathematics · #05c #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1908.10457

openalex publication_date 2019/08/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let G,H be graphs and G*H represent a particular graph product of G and H. We define im(G) to be the largest t such that G has a K_t-immersion and ask: given im(G)=t and im(H)=r, how large is im(G*H)? Best possible lower bounds are provided when * is the Cartesian or lexicographic product, and a conjecture is offered for each of the direct and strong products, along with some partial results.

Related

• Totally odd immersions of complete graphs in graph products
• A Note on the Immersion Number of Generalized Mycielski Graphs
• Immersions of large cliques in graphs with independence number 2 and bounded maximum degree
• Forcing clique immersions through chromatic number
• On clique immersions in line graphs