Transversal panconnectedness in graph collections

Wanting Sun ; Guanghui Wang ; Lan Wei¹

¹Shandong University

The electronic journal of combinatorics, Tome 32 (2025) no. 4

Résumé

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

Détail

DOI : 10.37236/13790

Classification : 05C70, 05C15, 05C60, 05C38, 05C45
Mots-clés : Hamiltonicity, transversal in graph collections