Premium
Mader's conjecture for graphs with small connectivity
Author(s) -
Hong Yanmei,
Liu Qinghai
Publication year - 2022
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22831
Subject(s) - mathematics , corollary , combinatorics , conjecture , vertex (graph theory) , embedding , graph , discrete mathematics , order (exchange) , characterization (materials science) , tree (set theory) , computer science , materials science , finance , artificial intelligence , economics , nanotechnology
Mader conjectured that for any treeT$T$ of orderm$m$ , everyk$k$ ‐connected graphG$G$ with minimum degree at least⌊ 3 k 2 ⌋ + m − 1$\lfloor \frac{3k}{2}\rfloor +m-1$ contains a subtreeT ′ ≅ T$T^{\prime} \cong T$ such thatG − V ( T ′ )$G-V(T^{\prime} )$ isk$k$ ‐connected. In this article, we give a characterization for a subgraph to contain an embedding of a specified tree avoiding some vertex. As a corollary, we confirm Mader's conjecture fork ≤ 3$k\le 3$ .
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom