Let \(k\ge 1\) be an integer. Let \(G=(V,E)\) be a connected graph with \(n\) vertices and \(m\) edges. Suppose fires break out at two adjacent vertices. In each round, a firefighter can protect \(k\) vertices, and then the fires spread to all unprotected neighbors. For \(uv\in E(G)\), let \(sn_{k}(uv)\) denote the maximum number of vertices the firefighter can save when fires break out at the ends of \(uv\). The \(k\)-edge surviving rate \(\rho'_k(G)\) of \(G\) is defined as the average proportion of vertices saved when the starting vertices of the fires are chosen uniformly at random over all eages, i.e., \(\rho'_k(G)=\sum\limits_{uv\in E(G)}sn_{k}(uv)/nm\). In particular, we write \(\rho'(G)=\rho'_1(G)\). For a given class of graphs \(\mathcal{G}\) and a constant \(\varepsilon>0\), we seek the minimum value \(k\) such that \(\rho'_k(G)>\varepsilon\) for all \(G\in \mathcal{G}\). In this paper, we prove that for Halin graphs, this minimum value is exactly 1. Specifically, every Halin graph \(G\) satisfies \(\rho'(G)> 1/12\).
The Firefighter Problem was introduced by Hartnell [8] at a conference in Winnipeg, 1995, to model the containment of a spreading negative property within a network. Initially, fires break out at a set of vertices \(F\) in a graph \(G=(V,E)\). At every subsequent time step, the firefighter protects at most \(k\) vertices not yet on fire, and the fire spreads to all unprotected neighbors. The process ends when the fire can no longer spread.
The firefighter problem is hard even for \(f=k=1\) and trees of maximum degree 3 [4] or cubic graphs [9]. There are a number of different objectives that can be pursued, refer to the survey of Finbow and MacGillivray [5] for a general overview. We focus on maximizing the number of saved vertices. Additionally, we may restrict the cardinality of \(F\) to a fixed positive integer \(f\). Let \(sn_{k}(G,F)\) denote the maximum number of vertices in \(G\) that the firefighter can save when fires break out at \(F\). The \(k\)-surviving rate for \(f\) fires of a graph \(G\) is defined [11, 2, 5], as
\[\rho_{k}(G,f)=\frac{1}{\tbinom{n}{f}}\sum\limits_{F\in \tbinom{V(G)}{f}}\frac{ sn_{k}(G,F)}{n},\] where \(n\) is the order of \(G\) and \(\tbinom{V(G)}{f}\) denotes the set of all vertex subsets of order \(f\). For simplicity, we write \(sn(G, F)=sn_{1}(G, F)\), \(\rho(G,f)=\rho_{1}(G,f)\) and \(\rho_{k}(G)=\rho_{k}(G,1)\).
The surviving rate of graphs has gained significant attention since its introduction; see [1, 3, 7, 10, 12, 13]. Most results focus on single-fire sources, though recent work has explored multi-fire scenarios. If the firefighter protect \(k\) vertices with strategy \(D\) when fires break out at \(F\), then for any non-empty subset \(F'\subseteq F\), the same strategy \(D\) saves at least \(k\) vertices. Consequently, for fixed \(k\), \(sn_{k}(G,F)\le sn_{k}(G,F')\) for any non-empty subset \(F'\subseteq F\), leading to \[0< \rho_{k}(G,f)\le \cdots\le \rho_{k}(G,j)\le \rho_{k}(G,i)\le \cdots \le \rho_{k}(G,1)<1,\] for \(1 \le i\le j\le f\). Thus, the surviving rate for multi-fires generalizes the single-fire case.
For a tree \(T\) with maximum degree \(\Delta\), \(\rho(T,f)\ge 1-O(\frac{\log n(T)}{n(T)})\), where \(n(T)\) is the order of \(T\) and the constants implicit in the \(O(\cdot)\)-notation only depend on \(f\) and \(\Delta\) [2]. For fixed \(f\) and \(k\) with \(f\le k\), \(\rho_k(T,f)\ge 1-O(\frac{\log n(T)}{n(T)})\) holds for any tree \(T\) [2]. For square grids \(G_{\square}\), \(\rho(G_{\square},f)=1/4\) for fixed \(f\) [6].
This paper investigates a novel multi-fire variant. Let \(G=(V,E)\) be a connected graph with \(n\) vertices and \(m\) edges. Define \(sn_{k}(uv)\) as the maximum number of vertices saved when fires break out at the endpoints of edge \(uv\). The \(k\)-edge surviving rate \(\rho'_{k}(G)\) of \(G\) is defined by
\[\rho'_{k}(G)=\frac{\sum_{uv\in E(G)}sn_{k}(uv)}{nm}.\]
In particular, we write \(sn(uv)=sn_{1}(uv)\) and \(\rho'(G)=\rho'_{1}(G)\).
Wang et al. [13] showed that the \(k\)-surviving rate for single fires in almost all graphs approaches zero, implying the same for the \(k\)-edge surviving rate. Thus, for a given class of graphs \(\mathcal{G}\), we are interested in the minimum \(k\) such that \(\rho'_k(G)>\varepsilon\) for some constant \(\varepsilon>0\) and all \(G\in \mathcal{G}\).
A Halin graph is formed by a planar embedding of a tree \(T\) (with no degree-2 vertices) and connecting its leaves with a cycle \(C\) that crosses no edges, denoted \(T\cup C\). Cai and Wang [11] studied the surviving rate of Halin graphs and proved:
Theorem 1.1. [11] If \(G\) is a Halin graph with at least 5 vertices, then \(\rho(G)>3/10\).
We use the following legend for the figures in this paper: black vertices indicate fire sources, shaded vertices are on fire, square-boxed vertices are protected, and numbers beside vertices denote ignition times.
Our contributions are as follows. Section 2 fixes notation and provides examples. Section 3 derives a lower bound for the edge surviving number using vertex degrees. Section 4 establishes a key lemma applicable beyond Halin graphs, yielding a preliminary lower bound for \(\rho^{\prime}(G)\). Structural properties of Halin graphs refine this bound. Section 5 proposes open problems for further investigation.
For a graph \(G=(V, E)\) and a vertex \(v \in V, d(v)\) denotes the degree of \(v\) in \(G\), and \(N(v)\) denotes the set of neighbors of \(v\) (i.e., vertices adjacent to \(v\) ). A \(d\)-vertex is a vertex of degree \(d\), and \(\Delta\) denotes the maximum degree of \(G\).
The join of \(G\) and \(H\), denoted \(G \bigvee H\), is obtained from the disjoint union of \(G\) and \(H\) by adding edges joining every vertex of \(G\) to every vertex of \(H\). The join \(C_n \bigvee K_1\) is called a wheel and denoted \(W_n\). The operation of contracting an edge \(uv\) involves deleting \(uv\) and identifying \(u\) and \(v\) into a single vertex. The graph \(G-X\) is the subgraph of \(G\) obtained by deleting the set of vertices \(X\).
A rooted tree is a tree \(T\) with one vertex \(r\) designated as the root. For each vertex \(v\) in \(T\), its neighbor on the unique \((r, v)\)-path in \(T\) is the parent of \(v\), and each remaining neighbor is a child of \(v\). A vertex \(u\) is a descendant of \(v\) if \(v\) lies on the unique \((r, u)\)-path in \(T\). A rooted subtree \(T_v\) of \(T\) consists of \(v\) (as its root) and all descendants of \(v\).
For fixed positive integers \(k\) and \(f\), the following monotonicity holds: if firefighters protect vertices \(\left(D_1, D_2, \ldots\right)\) (where \(D_i\) denotes vertices defended in round \(i\) ) to save \(k\) vertices in \(G\), then for any spanning subgraph \(H\) of \(G\), they can protect the same vertices in \(H\) to save at least \(k\) vertices. This implies a relationship between surviving rates of a graph and its spanning subgraphs:
Fact 2.1. Let \(k\) and \(f\) be fixed positive integers. For any spanning subgraph \(H\) of a graph \(G\), \(\rho_{k}(H,f)\ge \rho_{k}(G,f)\).
This monotonicity is crucial for proving lower bounds on the \(k\)-surviving rate. However, it does not extend to the \(k\)-edge surviving rate. For example:
Example 2.2. The star graph \(K_{1,n}\) is a spanning subgraph of the wheel graph \(W_{n}\). However, \(\rho'(K_{1,n})=1/(n+1)\) and \(\rho'(W_{n})=1/2-2/(n+1)\). It follows that \(\rho'(K_{1,n}) < \rho'(W_{n})\) as \(n\) tends to infinity. In contrast, \(\rho(K_{1,n}) = \rho(W_{n})=1\) as \(n\) tends to infinity.
Example 2.3. Let \(G=P_n\bigvee\{x,y\}\) where \(\{x,y\}\) is an independent set. The graph \(K_{2,n}\) is a spanning subgraph of \(G\). Here, \(\rho'_{2}(G)=(n+3)/(3n-1)\) and \(\rho'_{2}(K_{2,n})=2/n\). When \(n\) tends to infinity, \(\rho'_2(K_{2,n}) < \rho'_2(G)\).
These examples demonstrate that the edge surviving rate differs significantly from the surviving rate for \(f\) fires when \(f\) is a fixed positive integer.
We assume a planar embedding of a Halin graph \(G\) is given, where all vertices in the cycle \(C\) lie on the outer face. All vertices not on \(C\) (i.e., non-leaf vertices of the tree \(T\) ) are internal vertices, and the neighbors of each vertex are ordered counterclockwise. Cai and Wang [11] proved that for Halin graphs, at least a constant proportion of vertices can be saved on average when a fire breaks out at a single vertex. They established a lower bound for the surviving number of a vertex in terms of its degree:
Lemma 3.1. [11] Let \(G\) be a Halin graph with \(n\ge 7\) vertices. For every vertex \(v\) in \(G\), \[sn(G, v)\ge \frac{n-1}{d(v)}.\]
Inspired by Lemma 3.1, we derive an analogous result for the edge surviving number based on the sum of degrees of adjacent vertices:
Lemma 3.2. Let \(G=T\cup C\) be a Halin graph with \(n\ge 8\) vertices and \(uv\in E(G)\). If \(u\) and \(v\) satisfy one of the following:
(1) Both are internal vertices;
(2) \(u,v\in C\) and share a common parent \(w\) with \(d(w)\ge 4\), then
\[sn(uv)\geq\frac{n-2}{d(u)+d(v)-2}.\]
Proof. Assume \(uv\) satisfies the stated condition. Construct a new Halin graph \(G^*\) by contracting \(uv\) into a vertex \(v^{*}\), resulting in \(|G^*|=n-1 \geq 7\). Observe that \(d(v^{*})=d(u)+d(v)-2\) or \(d(v^{*})=d(u)+d(v)-3\). By Lemma |reflemma1, \(\operatorname{sn}\left(v^*\right) \geq \frac{n-2}{d\left(v^*\right)}\). Hence,
\[sn(uv)=sn(v^{*})\geq\frac{n-2}{d(v^{*})}\ge \frac{n-2}{d(u)+d(v)-2}.\] ◻
Lemma 3.3. Let \(G=T\cup C\) be a Halin graph with \(n\geq 8\) vertices. For every edge \(uv\) in \(E(G)\) with \(d(u)+d(v)\le9\), \[sn(uv)\ge \begin{cases} \frac{n-2}{4}& \ \ \ \text{$uv \in C $;}\\ \frac{n-2}{15}& \ \ \ \text{$uv \in T$}. \end{cases}\]
Proof. If two adjacent vertices \(u\) and \(v\) satisfy the condition of Lemma 3.2, the bound holds. We therefore address the remaining cases: either \(uv\) is an edge in \(C\) or one of \(u, v\) is a leaf of \(T\).
Case 1. \(uv\) is an edge in \(C\).
Subcase 1.1. \(u,v\) share a common parent \(w\) with \(d(w)=3\).
Let \(z\in N(w)\backslash \{u,v\}\) and consider \(T-\{u,v,w\}\) as a tree rooted at \(z\). Label the subtrees rooted at the children of \(z\) counterclockwise. Call the first one the leftmost subtree, and the last one the rightmost subtree. We show \(sn(uv)\geq(n-2)/4\).
Assume the rightmost subtree \(T^{\prime}\) contains at least \((n-2) / 4\) vertices. Protect its rightmost vertex, leftmost vertex, and root in sequence (Figure 1), yielding \(sn(uv) \geq(n-2)/4\).
Both the leftmost and rightmost subtrees of \(z\) contain fewer than \((n-2)/4\) vertices. In this case, let \(S\) denote the tree rooted at \(z\) after deleting both the leftmost and rightmost subtree of \(z\) from \(T-\{u,v,w\}\). Then \(S\) contains at least \((n-4)/2\ge 2\) vertices as \(n\geq 8\). Without loss of generality, we may assume that the leftmost subtree of \(T-\{u,v,w\}\) contains at least as many vertices as the rightmost subtree of \(T-\{u,v,w\}\). If the leftmost subtree of \(T-\{u,v,w\}\) contains at least two vertices, then \(C\) contains at least two more vertices from \(u\) to the leftmost vertex of \(S\), and we can save all vertices in \(S\) by protecting vertices in the order shown in Figure 2(a), implying \(sn(uv)\geq(n-2)/4\).
Otherwise, both the leftmost and rightmost subtrees of \(T-\{u,v,w\}\) contain one vertex, and thus \(S\) has \(n-5\) vertices. We protect \(z\) first, then the rightmost vertex of \(S\). At this point, the leftmost vertex of \(S\) is on fire. From now on, we contain the fire to spread along the cycle \(C\) counterclockwise by protecting the unique internal neighbor \(w\) of the vertex \(x\) most recently on fire until we have the situation that the internal vertex \(w\) has been protected already. When this happens, we protect the right neighbor \(x^{'}\) of \(x\) on \(C\) (do nothing if \(x^{'}\) has been protected already), and the fire can no longer spread (see Figure 2(b)). Therefore we save more than half of the vertices in \(S\), and thus \(sn(uv)>(n-5)/2\ge (n-2)/4\) for \(n\ge 8\).
Subcase 1.2. \(u\), \(v\) have distinct parents.
Let \(u'\) and \(v'\) be the neighbor of \(u\) and \(v\) in \(T\), respectively. Consider \(T-\{u,v\}\) as a tree rooted at \(v'\). Order the subtrees rooted at the children of \(v'\) counterclockwise, labeling the first as the leftmost subtree and the last as the rightmost subtree. We show that \(sn(uv)\ge (n-2)/4\).
Assume one of these subtrees contains at least \((n-2)/4\) vertices. Without loss of generality, let \(u\) lie to the left of \(v\), and suppose the rightmost subtree \(T^{\prime}\) of \(v^{\prime}\) contains at least \((n-2)/4\) vertices. If \(C\) contains at least two vertices from \(u\) to the leftmost vertex of \(T^{\prime}\), protect the rightmost vertex, root, and leftmost vertex of \(T^{\prime}\) in sequence (Figure 3(a)), yielding \(sn(uv) \geq(n-2)/4\). Otherwise, \(T^{\prime}\) has \(n-5\) vertices. Protect the rightmost vertex of \(T^{\prime}\), then its root. When the leftmost vertex ignites, contain the fire along \(C\) using the strategy from Subcase 1.1 (Figure 3(b)), and thus \(sn(uv)>(n-5)/2\ge (n-2)/4\) for \(n\ge 8\).
If both of the leftmost and rightmost subtrees of \(v'\) contain fewer than \((n-2)/4\) vertices, let \(S\) denote the tree rooted at \(v'\) after deleting both the leftmost and rightmost subtrees of \(v'\) from \(T-\{u,v\}\). Then \(S\) contains at least \((n-4)/2\ge 2\) vertices for \(n\ge 8\). Without loss of generality, we may assume that the leftmost subtree of \(v'\) contains at least as many vertices as the rightmost subtree of \(v'\). If the leftmost subtree of \(v'\) contains at least three vertices, then \(C\) contains at least two more vertices from \(u\) to the leftmost vertex of \(S\), and we can save all vertices in \(S\) by protecting vertices in the order shown in Figure 4(a), implying \(sn(uv)\ge (n-2)/4\). Otherwise, the leftmost subtree contains two vertices and rightmost subtrees contains one vertex, and thus \(S\) has \(n-5\) vertices. We protect vertex \(v'\) first, then the rightmost vertex in \(S\). At this point, the leftmost vertex of \(S\) is on fire, and we protect vertices in \(S\) as we did in Subcase 1.1 (see Figure 4(b)). Therefore we save more than half of the vertices in \(S\), and \(sn(uv)>(n-5)/2\ge (n-2)/4\) for \(n\ge 8\).
Case 2. Exactly one of \(u, v\) is a leaf of \(T\).
Without loss of generality, assume \(u\) is a leaf and \(v\) is an internal vertex of \(T\). We prove that \(sn(uv)\ge (n-2)/15\).
Consider \(T-\{u\}\) as a tree rooted at \(v\), with subtrees ordered counterclockwise around \(v\). Let \(w\) be adjacent to \(v\) which is not \(u\) and regard \(T_w\) as a tree rooted \(w\), where \(T_w\) is immediately left of the rightmost subtree and immediately right of the leftmost subtree. There is a subtree \(T_{w}\) with at least \((n-2)/5\) vertices as \(d(v)\le 6\). Let \(T_r(w)\) and \(T_l(w)\) denote the subtrees to the right and left of \(T_w\), respectively. In particular, \(T_r(w)\) is empty if \(T_w\) is the rightmost subtree of \(T_v\), and \(T_l(w)\) is empty if \(T_w\) is the leftmost subtree of \(T_v\). As \(d(v)\ge 3\), at most one of \(T_l(w)\) and \(T_r(w)\) is an empty set.
If one of \(T_l(w)\) and \(T_r(w)\), say \(T_l(w)\), contains at least two vertices, and \(T_r(w)\) contains at least one vertex, we can save all vertices in \(T_w\) by first protecting \(w\), then the rightmost vertex of \(T_w\), followed by the leftmost vertex of \(T_w\) (see Figure 5(a)). Thus, \(sn(uv)\ge (n-2)/5>(n-2)/15\).
If \(T_l(w)\) and \(T_r(w)\) each contain exactly one vertex. We first protect vertex \(w\) and then the rightmost vertex of \(T_w\). At this point, the leftmost vertex in \(T_w\) is on fire, and we deal with \(T_w\) as we did for \(S\) in Subcase 1.1 to contain the fire to spread along the cycle \(C\) counterclockwise (see Figure 5(b)). Therefore we save at least \(1+(n_w-1)/2\) vertices in \(T_w\), where \(n_w\) is the number of vertices in \(T_w\), which yields \(sn(uv)\geq 1+(n_w-1)/2=(n_w+1)/2\ge (n+3)/10>(n-2)/15\).
Otherwise, one of \(T_l(w)\) and \(T_r(w)\) is empty, say \(T_r(w)\), that is \(T_w\) is the rightmost subtree of \(T_v\). We order subtrees rooted at the children of \(w\) counterclockwise around \(w\). If the rightmost subtree of \(w\) contains at least \((n-2)/15\) vertices, then we protect vertices in order shown in Figure 6(a), implying \(sn(uv)\ge (n-2)/15\). Otherwise, let \(S\) denote the subtree rooted at \(w\) after deleting the rightmost subtree of \(w\) from \(T-\{u\}\). Then \(S\) contains at least \(2(n-2)/15\) vertices. We first protect vertex \(w\) and then the rightmost vertex of \(S\). At this point, the leftmost vertex in \(S\) is on fire, and we deal with similar to the above to contain the fire to spread along the cycle \(C\) counterclockwise(see Figure 6(b)). Therefore we save at least \(1+(|S|-1)/2\) vertices in \(S\), which yields \(sn(uv)\geq 1+(|S|-1)/2=(|S|+1)/2\ge (n-2)/15\). ◻
First, we prove a key lemma applicable to graph families beyond Halin graphs. Using this lemma, we derive a preliminary lower bound. Subsequently, we refine this bound by leveraging properties specific to Halin graph constructions.
Lemma 4.1. Let \(G\) be a graph with \(n\) vertices and \(m\) edges. Supppse there exists an edge weight function \(w\) with total weight is at least \(cm\) for some constant \(c>0\). Let \(E^{*}\) denote edges satisfying \(sn_k(uv)\ge ln\), for integer \(k\) and real number \(l\) with \(0<l<1\). Assume further that there exist constants \(\beta < c\) and \(\alpha \ge c\) such that \(w(uv)\le \alpha\) for \(uv\in E^{*}\) and \(w(uv)\le \beta\) for \(E \backslash E^*\). Then \(\rho'_{k}(G)\ge \frac{(c-\beta)l}{\alpha – \beta}.\)
Proof. From the assumptions:
\[\begin{aligned} cm \le \sum\limits_{uv\in E(G)}w(uv)&=\sum\limits_{uv\in E^{*}}w(uv)+\sum\limits_{uv\in E\backslash E^{*}}w(uv)\\ &\le \alpha m^{*}+\beta(m-m^{*}) ~ (\textrm{where} ~ m^{*}=|E^{*}|)\\ &= (\alpha-\beta)m^{*}+\beta m. \end{aligned}\]
Since \(\alpha-\beta>0\), we get \(m^{*}\ge \frac{c-\beta}{\alpha-\beta}m\).
For edges \(uv\in E\backslash E^{*}\), the firefighter can save at least \(k\) vertices.
\[\begin{aligned} \sum\limits_{uv\in E(G)}sn_{k}(uv)&=\sum\limits_{uv\in E^{*}}sn_{k}(uv)+\sum\limits_{uv\in E(G)\backslash E^{*}}sn_{k}(uv)\\ &\ge (ln-k)m^{*}+km\\ &\ge \frac{(c-\beta)l}{\alpha-\beta}nm+\frac{\alpha-c}{\alpha-\beta}km\\ &\ge \frac{(c-\beta)l}{\alpha-\beta}nm. \end{aligned}\]
Therefore,
\[\rho'_{k}(G)=\frac{\sum\limits_{uv\in E(G)}sn_{k}(uv)}{nm}\ge \frac{(c-\beta)l}{\alpha-\beta}.\] ◻
Lemma 4.2. Let \(G=T\cup C\) be a Halin graph with \(n\) vertices and \(m\) edges. Define \(E^{*}=\{uv\in E(G)| d(u)+d(v)\le 9\}\). There exists a weight function \(w(uv)\) for a edge \(uv\in E(G)\) such that:
(1) \(\sum\limits_{uv\in E(G)}w(uv)>\frac{m}{2}\).
(2) If \(uv\in E^{*}\), then \(w(uv)\le \frac{2}{3}\).
(3) If \(uv\in E\backslash E^{*}\), then \(w(uv)\le \frac{10}{21}\).
Proof. Recall that a Halin graph has at least 4 vertices and at most \(2n-2\) edges. Define the weight function
\[w(uv)=\frac{1}{d(u)}+\frac{1}{d(v)},\] for every edge in \(E(G)\). We verify the three properties:
(1) By double counting,
\[\sum\limits_{uv\in E(G)}w(uv)=\sum\limits_{uv\in E(G)}\frac{1}{d(u)}+\frac{1}{d(v)}=n\ge \frac{m+2}{2}>\frac{m}{2}.\]
(2) For \(uv\in E^{*}\), since \(d(u)+d(v)\le 9\) and the minimum degree of Halin graph is at least 3, we obtain
\[w(uv)\le \frac{1}{3}+\frac{1}{3}=\frac{2}{3}.\]
(3) For \(uv\in E\backslash E^{*}\), \(d(u)+d(v)\ge 10\). By the fact that, the greater the difference between two numbers, the smaller the product, when the sum is a constant. It follows that
\[w(uv)=\frac{1}{d(u)}+\frac{1}{d(v)}=\frac{d(u)+d(v)}{d(u)d(v)}\le \frac{1}{3}+\frac{1}{7}=\frac{10}{21}.\] ◻
Theorem 4.3. Every Halin graph \(G\) with \(n\ge 4\) vertices satisfies \(\rho'(G)\ge \frac{1}{125}\).
Proof. Let \(E^{*}=\{uv\in E(G)| d(u)+d(v)\le 9\}\). By Lemma 3.3, \(sn(uv)\ge \frac{n-2}{15}\ge \frac{8n}{125}\) for \(uv\in E^{*}\). Apply Lemma 4.1 and Lemma 4.2 with parameters \(c=\frac{1}{2}\), \(l=\frac{8}{125}\), \(\alpha=\frac{2}{3}\) and \(\beta=\frac{10}{21}\). ◻
Lemma 4.4. Let \(G=T\cup C\) be a Halin graph with \(n\) vertices and \(m\) edges. Then \(\|C\| > (m+3)/3\), where \(\|C\|\) denotes the number of edges in \(C\).
Proof. Let \(n_d\) denote the number of \(d\)-vertices in \(T\). Thus, \(n_1\) denotes the number of edges of \(C\) as well as the leaves of \(T\). We use \(\|T\|\) to denote the number of edges in \(T\). It follows that \(m=\|T\|+\|C\|=n-1+n_1.\)
For tree \(T\),
\[\sum\limits_{v\in V(T)}d(v)=2\|T\|=2(n-1).\]
Thus,
\[\sum\limits_{d=1}^{\Delta}dn_d=2(n-1)=2(\sum\limits_{d=1}^{\Delta}n_d-1).\]
This implies \[n_1=\sum\limits_{d=3}^{\Delta}(d-2)n_{d}+2\ge \sum\limits_{d=3}^{\Delta}n_d+2=(n-n_1)+2.\]
And so \[n_1\ge \frac{n+2}{2}=\frac{m+3-n_1}{2}.\]
Hence, \[n_1\ge \frac{m+3}{3}.\] ◻
Theorem 4.5. Every Halin graph \(G=T\cup C\) with \(n\ge 4\) vertices satisfies \(\rho'(G)> \frac{1}{12}\).
Proof. By Lemma 3.3, \(sn(uv)\ge \frac{n-2}{4}\) for \(uv\in C\). Thus,
\[\begin{aligned} \sum\limits_{uv\in E(G)}sn(uv)&=\sum\limits_{uv\in C}sn(uv)+\sum\limits_{uv\in T}sn(uv)\\ &\ge \frac{n-2}{4}\cdot \|C\|+1\cdot \|T\|\\ &> \frac{n-2}{4}\cdot \frac{m+3}{3}+(n-1)\\ &\ge \frac{nm}{12}+\frac{15n-2m-18}{12}\\ &\ge \frac{nm}{12}+\frac{11n-14}{12} \ \ \ \ (\text{as} \ m\le 2n-2)\\ &\ge \frac{1}{12}nm. \end{aligned}\]
Therefore,
\[\rho'(G)=\frac{\sum\limits_{uv\in E(G)}sn(uv)}{nm}> \frac{1}{12}.\] ◻
In this paper, we introduced the concept of the edge surviving rate for graphs in the firefighter problem and investigated this rate for Halin graphs.
While Halin graphs exhibit constant lower bounds on their edge surviving rates, the bounds we established are not tight. Improving these bounds remains an open challenge. For Halin graphs, it remains unclear whether their asymptotic 1-edge surviving rate approaches 1. Notably, for \(n\)-wheels \(W_n\), \(\rho'_{k}(W_n)=1/2\) as \(n\) tends to infinity. However, we conjecture that Halin graphs with bounded maximum degree may satisfy \(\lim\limits _{n \rightarrow \infty} \rho^{\prime}(G)=1\).
Problem 5.1. For Halin graphs \(G\) with \(n\) vertices and bounded maximum degree, determine whether \(\lim\limits_{n\to \infty}\rho'(G)=1\).
Additionally, for fixed \(f\), \(n\)-wheels \(W_n\) satisfy \(\rho(W_n, f)\) approaching 1 as \(n\rightarrow \infty\). This motivates.
Problem 5.2. For Halin graphs \(G\) on \(n\) vertices and fixed integer \(f\), determine whether \(\lim\limits_{n\to \infty}\rho(G,f)=1\).
Finally, outerplanar graphs [11], \(K_4\)-minor free graphs [11], graphs with bounded treewidth [1], \(k\)-degenerate graphs [13], planar graphs [7, 10, 12] are known to have positive surviving rates. A natural extension is to investigate whether these classes also exhibit positive edge surviving rates.