A Note on Weak Saturation Number of Trees
Wenchong Chen, Xiao-Chuan Liu, Xu Yang · 2025
Read A Note on Weak Saturation Number of Trees by Wenchong Chen, Xiao-Chuan Liu, Xu Yang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-15626.txt.
Introduction
Wenchong Chen, Xiao-Chuan Liu, and Xu Yang estimate a graph number for tree shapes in a 2025 maths note. The number is the weak saturation number of a tree. It counts the fewest edges a sparse graph can hold before a set process fills it. Trees pose a clean test case for such estimates.
As a case study, the team examine caterpillars, a simple tree family. They get several tight estimates for those trees. For a broad range of growth rates, some caterpillars hit each rate. A tree is called good when its number is exactly its edge count minus one. The note gives a test for good trees. With one added trait on leaf spacing, that test fully sorts good trees.
Catalog record
| CREATOR | Wenchong Chen, Xiao-Chuan Liu, Xu Yang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 32 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-15626
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Note on Weak Saturation Number of Trees Wenchong Chen, Xiao-Chuan Liu, Xu Yang Abstract . In this paper, we estimate the weak saturation numbers of trees. As a case study, we examine caterpillars and obtain several tight estimates. In particular, this implies that for any α ∈ [ 1 , 2 ] \alpha\in[1,2] , there exist caterpillars with k k vertices whose weak saturation numbers are of order k α k^{\alpha} . We call a tree good if its weak saturation number is exactly its edge number minus one. We provide a sufficient condition for a tree to be a good tree. With the additional property that all leaves are at even distances from each other, this condition fully characterizes good trees. The latter result also provides counterexamples, demonstrating that Theorem 8 of a paper by Faudree, Gould and Jacobson (R. J. Faudree, R. J. Gould, and M. S. Jacobson. Weak saturation numbers for sparse graphs. Discussiones Mathematicae Graph Theory , 33(4): 677-693, 2013.) is incorrect. 1. Introduction We follow [ 10 ] for graph theory notation. Throughout, we consider only simple, finite, and undirected graphs. Given a graph F , a graph G is said to be weakly F -saturated if its non-edges can be added one by one in a specific order, such that each newly added edge forms a new copy of F . For any integer n , the weak saturation number of F , denoted \text{w-sat}(n,F) , is the minimum size of an n -vertex weakly F -saturated graph. This process produces a sequence of graphs, each with one additional edge, culminating in the complete graph K_{n} . This process is also referred to as an F -bootstrap percolation process. Bollobás [ 2 ] introduced both notions in 1968 and conjectured that \text{w-sat}(n,K_{k})={k\choose 2}-1+(n-k)(k-2) for any n\geq k , a result later proved by Lovász in [ 9 ] . Lovász’s proof involves flats in matroids representable over fields and is somewhat mysterious, given that this is a purely combinatorial problem. Consequently, several researchers have studied these problems, offering various proofs, including those by Frankl [ 6 ] , Kalai [ 7 ] , Alon [ 1 ] , and Yu [ 12 ] . It remains an open question whether a truly elementary combinatorial proof exists, as none of the above qualify. Determining the exact values of weak saturation numbers is generally very difficult. Aside from the complete graphs discussed above, a recent result states that \text{w-sat}(n,K_{t,t})={t\choose 2}+(t-1)(n-2t+1) , which was proved in [ 8 ] using the elegant linear algebra method. We also highlight a recent combinatorial approach by Terekhov and Zhukovskii [ 11 ] , which provides precise weak saturation numbers for certain graphs. Turning our attention to a more relaxed problem, we can ask for the correct order and leading coefficients for the weak saturation numbers of some fixed graph F with k vertices and with minimum degree \delta . A straightforward upper bound arises from constructing a copy of K_{k}\backslash\{e\} along with n-k additional vertices, each joining to \delta-1 vertices of that copy. This immediately implies that for any n\geq v(F) , \text{w-sat}(n,F)\leq{k\choose 2}-1+(\delta-1)(n-k)=(\delta-1)n+O(1) . However, there are no matching lower bounds in general. Faudree, Gould and Jacobson originally claimed the estimate \text{w-sat}(n,F)\geq(\frac{\delta}{2}-\frac{1}{\delta+1})n+o(n) in [ 5 ] , though their proof contained flaws. The result was later corrected by Terekhov and Zhukovskii in [ 11 ] . In this paper, we mainly discuss weak saturation number of trees. Likely because their weak saturation numbers are O(1) , trees, despite being the simplest and most fundamental types of graphs, have not been fully understood and were somewhat overlooked, with only a few results available, as seen in [ 4 , 5 ] . First, we note that the number \text{w-sat}(n,T) is always non-increasing. The proof will be provided in Section 2 . Proposition 1.1 . For any graph F with minimum degree 1 , \text{w-sat}(n,F) is non-increasing with respect to n for n\geq v(F) . Therefore, for a tree T , \text{w-sat}(n,T) remains constant for all sufficiently large n . We denote by \text{w-wat}(T) the limit number of \text{w-wat}(n,T) as n tends to infinity. In extremal graph theory, a famous rational exponent conjecture (Erdős and Simonovits [ 3 ] ) states that, for every rational number r\in(1,2) , there exists a graph whose Turán exponent equals r . However, for trees, the weak saturation number depends only on their size k and not on n . In this paper, we prove that all rational exponents between 1 and 2 can be realized by weak saturation numbers of trees in terms of their sizes. Theorem 1.2 . For any \alpha\in[1,2] , there exists a family \{T_{k}\}_{k\geq 5} of trees such that, where each T_{k} has k vertices, and \text{w-sat}(T_{k})=\Theta(k^{\alpha}) . A nondegenerate caterpillar C_{a_{1},a_{2},\cdots,a_{\ell}} , where a_{t}>0 , t=1,2,\cdots,\ell , is formed by adding a_{t} pendant edges to each v_{t} of a path P_{\ell}=(v_{1},v_{2},\cdots,v_{\ell}) , for every t=1,\cdots,\ell . Our next result gives a precise characterization of the weak saturation numbers for nondegenerate caterpillars. Theorem 1.3 . Consider a nondegenerate caterpillar T=C_{a_{1},a_{2},\ldots,a_{\ell}} on k+1 vertices, and write a=\min\{a_{t}\,\big|\ 1\leq t\leq\ell\} . Then we have (1) \text{w-sat}(T)=k-1 if and only if a\leq 2 . (2) If a>2 , then \text{w-sat}(T)=k-1+{a-1\choose 2} . A tree T is called a good tree if \text{w-sat}(T)=e(T)-1 . It is natural to explore the structure of good trees, and we prove the next theorem for this purpose. Theorem 1.4 . Suppose a tree T satisfies that the distances between any two leaves are even. Then T is a good tree if and only if there exists a leaf that is adjacent to a vertex of degree 2. The rest of the paper is organized as follows. In Section 2 , we will present some general estimates for trees and more generally graphs with at least one pendant edge. In Section 3 , we focus on caterpillars and prove Theorems 1.2 and 1.3 . In Section 4 we prove Theorem 1.4 . 2. General Estimates In this section, we present several general estimates for weak saturation numbers as well as the proof of Proposition 1.1 . We will use the following definition introduced in [ 5 ] . Definition 2.1 . Given a graph F , we define an induced subgraph S=K_{1,s} to be an end-star of F , if the center of S has degree s+1 in F and s of the other vertices of S have degree 1 in F . If F contains at least an end-star, the minimum end-degree of F , denoted by \delta_{e}(F) , is the minimum degree of the center of an end-star of F . The following simple lemma turns out to be crucial. Lemma 2.2 . Let F be a graph on k+1 vertices with minimum degree 1 and maximum degree \Delta=\Delta(F) . Suppose a graph G with v(G)\geq k+1 admits an induced subgraph H on k vertices such that \delta(H)\geq\Delta . Then G is weakly F -saturated. Proof. It suffices to show we can iteratively add edges to the graph G , until it becomes the complete graph K_{n} . (a) For any v\in V(H) and v^{\prime}\in V(G)-V(H)