Publications

Chvátal-Erdős conditions and almost spanning trails.

Faculty Author(s): Zhan, Mingquan
Student Author(s): -
Department: MATH
Publication: Bulletin of the Malaysian Mathematical Sciences Society
Year: 2020
Abstract: For a graph $G$, let $\alpha'(G)$, $ess'(G)$, $\kappa(G)$, $\kappa'(G)$, $N_G(v)$ and $D_i(G)$ denote the matching number, essential edge connectivity, connectivity, edge connectivity, the set of neighbors of vertex $v$ and the set of degree $i$ vertices of a graph $G$, respectively. For $u,v \in V(G)$, define $u \sim v$ if and only if $u = v$ or both $u,v \in D_2(G)$ and $N_G(u) = N_G(v)$. Then, $\sim$ is an equivalence relation, and $[v] $ denotes the equivalence class containing $v$. A subgraph $H$ of $G$ is almost spanning if $H \subseteq G - D_1(G)$, $\bigcup_{j\ge 3}D_j(G)\subseteq V(H)$ and for any ${v\in D_2(G)}$, $|[v]-V(H)|\leq 1$. The authors extend the line graph version of the Chvátal-Erdo\H s theorem for a connected graph as follows: \roster \item If $ess'(G) \geq \alpha'(G)$, then $G$ has an almost spanning closed trail. \item If $ess'(G) \geq \alpha'(G) - 1$, then $G$ has an almost spanning trail. \item If $ess'(G) \geq \alpha'(G) + 1$, then for $e, e' \in E(G - D_1(G))$, $G - D_1(G)$ has an almost spanning trail starting from $e$ and ending at $e'$. \endroster
Link: Chvátal-Erdős conditions and almost spanning trails.