OpenAlex ·
Connectivity keeping pendant extensions of paths in $k$-connected triangle-free graphs
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2610.20101
- Original
- Read it at the publisher
- Topics
Abstract
Motivated by Mader's conjecture on connectivity keeping trees, we study the corresponding problem in triangle-free graphs. For positive integers $k,m$, we first prove that every $k$-connected triangle-free graph $G$ with $δ(G)\geq k+\left \lceil \frac{m}{2} \right \rceil $ contains a path $P$ of order $m$ such that $G-V(P)$ remains $k$-connected. Moreover, if $κ(G)=k$, then for every end $F$ of $G$ and every vertex $v\in F$, the path $P$ can be chosen in $G[F]$ with $v$ as an endvertex. If $κ(G)\geq k+1$, then any vertex of $G$ can be chosen as an endvertex of $P$. This result confirms the conjecture of Luo, Tian and Wu on connectivity keeping trees in bipartite graphs for all paths, and it also sharpens Fujita's path theorem to the optimal minimum degree bound. For an integer $i$ with $1\leq i\leq m-1$, let $P_m^+(i)$ denote the tree obtained from a path of order $m-1$ by adding one pendant vertex adjacent to its $i$th vertex. Let $(X,Y)$ be the bipartition of $P_m^+(i)$. We further prove that every $k$-connected triangle-free graph $G$ with $δ(G)\geq k+\max\{|X|,|Y|\}$ contains a subgraph $T\cong P_m^+(i)$ such that $G-V(T)$ remains $k$-connected. The minimum degree bound is sharp, and the result confirms the bipartite conjecture for all pendant extensions of paths.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
On the Hardy--Littlewood--Chowla conjecture
A simpler proof that there are no Landau--Siegel zeros
Failure of direct finiteness for group algebras in every odd characteristic
Kaplansky's conjectures fail for torsion-free hyperbolic groups in positive characteristic
An example of a non-sofic hyperbolic group
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.