Aug 2026· Electronic Journal of Combinatorics· Vol 33· 1 citation· 46 references
Abstract
A theorem of Li and Ning [Linear Algebra Appl. 515 (2017)] states that, for $n\geq4$, every balanced bipartite graph $G$ on $2n$ vertices with spectral radius $\lambda(G)\geq\sqrt{n(n-1)}$ contains a Hamilton path unless $G\simeq K_{n,n-1}\cup K_1$. Let $[n]=\{1,2,\ldots,n\}$. We prove a generalization of this theorem in the setting of graph transversals. Namely, for $n\geq4$, we show that given a family $\mathcal{G}=\{G_1,G_2,\ldots,G_{2n-1}\}$ of $2n-1$ bipartite graphs on a common set $V$ of $2n$ vertices with a common balanced bipartition, if $\lambda(G_i)\geq\sqrt{n(n-1)}$ for every $i\in [2n-1]$, then there exists a transversal Hamilton path on $V$ unless $G_1=G_2=\cdots=G_{2n-1}$ and $G_1\simeq K_{n,n-1}\cup K_1$.
We also show spectral analogue of transversal Hamilton cycle in bipartite graph families. Let $B_n^1$ be the graph obtained from $K_{n,n}$ by deleting all edges in its one subgraph $K_{n-1,1}$. Given a family $\mathcal{G}=\{G_1,G_2,\ldots,G_{2n}\}$ of $2n$ bipartite graphs on a common set $V$ of $2n$ vertices with a common balanced bipartition, for $n\geq4$, we prove that if $\lambda(G_i)\geq\lambda(B_n^1)$ for every $i\in [2n]$, then $\mathcal{G}$ contains a transversal Hamilton cycle, unless $G_1=G_2=\cdots=G_{2n}$ and $G_1\simeq B_n^1$. Our result extends a result of Li and Ning [Linear Multilinear Algebra 64 (11) (2016)].
Let ${\cal G}=\{G_1,\ldots,G_k\}$ be a collection of (not necessarily distinct) bipartite graphs on the same vertex bipartition $(X,Y)$, where $|X|=a$, $|Y|=b$ and $2\le k\le a\le b$. A \emph{rainbow matching} of ${\cal G}$ is a set of pairwise disjoint edges that can be chosen from distinct members of ${\cal G}$. Deno...
Zhi-Wei Guo, Nan-Xi Pan, Li Li et al.· 0 citations
For graphs $G$ and $H$, let $\mathbf N(G,H)$ denote the number of unlabeled, not necessarily induced copies of $H$ in $G$, and let $\mathbf N_{\mathcal P}(n,H)$ be the maximum of $\mathbf N(G,H)$ over all $n$-vertex planar graphs $G$. We prove that, for every fixed integer $m\geq 3$, $$\mathbf N_{\mathcal P}(n,C_{2m+1}...
Let $G$ be a simple graph on $n$ vertices and $e(G)$ edges. Let $\mu_1\geq \cdots \geq \mu_{n-1}\geq \mu_n=0$ be the Laplacian eigenvalues of $G$. For $k=1, \ldots, n$, let $S_k(G)=\sum_{i=1}^{k}\mu_i$. Brouwers conjecture asserts that for any $k\in\{1,\ldots, n\}$, $S_k(G)\leq e(G)+\binom{k+1}{2}$. In [Bounding the su...
For a connected graph $G$, let $\tau(G)$ denote the maximum number of pairwise edge-disjoint spanning trees, and let $\rho(G)$ be its adjacency spectral radius. For integers $n\ge1$, $k\ge2$, and $k\le\delta\le2k-1$, let $\mathcal{G}_{n,\delta}$ be the class of connected $n$-vertex graphs with minimum degree $\delta$,...
Let $S_k(G)$ denote the sum of the $k$ largest Laplacian eigenvalues of a connected graph $G$ of order $n$ and size $m$. Write $\mathrm{PA}_{n,\omega}$ for the graph obtained from an $\omega$-vertex clique by attaching $n-\omega$ pendant vertices to one of its vertices, and set \[ M_{n,k}:=\binom{k+1}{2}+n-k-1, \] the...
Let $Y_{n,r,q}$ be the graph obtained from the Tur\'an graph $T_{n,r}$ by adding $q$ pairwise disjoint edges inside a largest part, and let $c(n,F)$ be the minimum number of copies of $F$ created by adding a single edge to $T_{n,r}$. Fang, Li, Lin and Ma proved that for every color-critical graph $F$ with $\chi (F)=r+1...
Hongzhang Chen, Yong-Tao Li· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.