Abstract:In this paper, we launch a systematic study of parameters concerning edge mappings of graphs. Inspired by Ramsey's theorem, the quantity $m(G,H)$ is defined to be the smallest integer $n$ such that for every $f:E(K_n)\rightarrow E(K_n)$ either there is an $f$-fixed copy of $G$ with $f(e)=e$ for all $e\in E(G)$, or an $f$-free copy of $H$ with $f(e)\notin E(H)$ for all $e\in E(H)$. Incorporating new ideas, we extend many old results from the 1980s and prove many new exact results, mostly concerning $m(T,K_r)$, where $T$ is a tree, and $m(G,K_{1,r})$. We also study further related parameters, most of them introduced in the 1980s, and obtain substantial progress regarding these parameters.
From: Balazs Patkos [view email]
[v1]
Thu, 1 Feb 2024 20:37:06 UTC (24 KB)
[v2]
Sat, 4 Jul 2026 07:28:33 UTC (24 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。