Transversal Panconnectedness in Graph Collections

Abstract

Given a collection $\mathcal{G} =\{G_1,G_2,\dots,G_m\}$ of graphs on the common vertex set $V$ of size $n$, a graph $H$ with vertices in $V$ is rainbow in $\mathcal{G}$ if there exists an injection $\varphi :E(H)\rightarrow [m]$ such that $e \in E(G_{\varphi(e)})$ for all $e\in E(H)$. We say $H$ is {a} transversal in $\mathcal{G}$ if $|E(H)|=m$. Denote $\delta(\mathcal{G}):=\min\left\{\delta(G_i): i\in [m]\right\}$. For vertices $x,\,y \in V$, let $d_{\mathcal{G}}(x,y)$ be the length of the shortest rainbow path (if exists) connecting $x$ and $y$ in $\mathcal{G}$. We say $\mathcal{G}$ is transversal panconnected if for any two vertices $x, y \in V$, there exists a rainbow path on $k$ vertices inside $\mathcal{G}$ joining $x$ and $y$ for every integer $k\in[d_{\mathcal{G}}(x,y)+1, n]$. In this paper, we provide a tight bound on $\delta(\mathcal{G})$ to ensure that $\mathcal{G}$ is transversal panconnected. It generalizes the result of [Williamson, Period. Math. Hungar., 1977] to the transversal version and improves the result of [Li, Li and Li, J. Graph Theory, 2023].