Spanning tree-connected subgraphs and spanning closed trails with small degrees

arXiv2205.05044MaRDI QIDQ6398786FDOQ6398786

Authors: Morteza Hasanvand 

Publication date: 10 May 2022

Abstract: Let $G$ be a graph, let $m$ be a positive integer, and let $f$ be a positive integer-valued function on $V(G)$. In this paper, we show that if for all $SsubseteqV(G)$, ${\displaystyle }$Omega_m(Gsetminus S)le sum_{vin S}�ig(f(v)-2m�ig)+m+Omega_m(G[S]),${\displaystyle }$ then $G$ has a spanning $m$-tree-connected subgraph $H$ containing an arbitrary given subgraph with maximum degree at most $m$ such that for each vertex $v$, $d_H(v)lef(v)$, where $G[S]$ denotes the induced subgraph of $G$ with the vertex set $S$ and $Omeg{a}_m(G_0)$ is a parameter to measure $m$-tree-connectivity of a given graph $G_0$. By applying this result, we prove that every $k$-edge-connected graph $G$ has a spanning $m$-tree-connected subgraph $H$ such that for each vertex $v$, $$, where $kge2m$; also if $G$ is $k$-tree-connected, then $H$ can be found such that for each vertex $v$, $$, where $kgem$. Next, we prove that if for all $SsubseteqV(G)$, ${\displaystyle }$frac{1}{2}Omega_2(Gsetminus S)le sum_{vin S}(f(v)-3/2)+1,${\displaystyle }$ then $G$ admits a spanning closed trail meeting each vertex $v$ at most $f(v)$ times. From this result, we conclude that every $4$-tough graph of order at least three admits a spanning closed trail meeting each vertex at most twice. This result confirms a weaker version of a long-standing conjecture due to Chv'atal (1973).

This page was built for publication: Spanning tree-connected subgraphs and spanning closed trails with small degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6398786)