Pascal Zongo

René Dorville

Elisée Gouba

Joseph Ki-Zerbo

Method for identifying spatial reservoirs of malaria infection and control strategies

Keywords: Control, Optimization, Metapopulation, Basic reproductive number, cost-effectiveness analysis

Managing spatial reservoirs of malaria infection plays a crucial role in effective disease control. In this paper, a reservoir of infection refers to one or more interconnected subpopulations that sustain the epidemic at the level of the metapopulation to which applying a (linear) control strategy suffices to eradicate the disease in the whole system. We propose a numerical method to explain the steps for identifying reservoirs of malaria infection within n connected regions with the explicit movement of human population from the previous theoretical results in order to design an efficient computational tool. Furthermore, we determine the minimal percentage (critical vaccination fraction) of susceptible individuals in the reservoirs that should be protected to eliminate malaria. The costs and cost-effectiveness of malaria control interventions were analysed considering two strategies of control. (i) protecting the minimal fraction of susceptible individual; (ii) protecting any fraction greater than the minimal fraction. Cost-effectiveness analysis shows that the less cost and more effective strategy is to vaccinate (or protect) the minimal fraction of susceptible human in the reservoir of infection to halt outbreak. A numerical example provides insight into the efficiency of this approach.

I. INTRODUCTION

Malaria is a mosquito-borne infections disease caused by protozoa of the genus plasmodium (parasite). It is estimated that about 1.5-3 million of people, mostly children, die of malaria every year [START_REF] Who | The World Health Report[END_REF]. Malaria control requires an integrated approach, including prevention and prompt treatment [START_REF] Who | Guidelines for the Treatment of Malaria[END_REF].

The parasites are transmitted indirectly from human to human by the bite of infected female mosquitoes of the genus Anopheles. There is some natural acquired partial immunity to the pathogen in humans developed after many years of repeated infections [START_REF] Aron | Mathematical modeling of immunity to malaria[END_REF], [START_REF] Drakeley | Transmission reducing immunity is inversely related to age in plasmodium falciparum gametocyte carriers[END_REF], [START_REF] Kaslow | Transmission-blocking immunity against malaria and other vector-borne diseases[END_REF], [START_REF] Ponnudurai | Transmission blockade of Plasmodium falciparum: its variability with gametocyte numbers and concentration of antibody[END_REF].

Models have already been proposed to provide an explicit framework for understanding malaria transmission dynamics in human population for over 100 years [START_REF] Chitnis | Bifurcation analysis of a mathematical model for malaria transmission[END_REF], [START_REF] Ducrot | A mathematical model for malaria involving differential susceptibility, exposedness and infectivity of human host[END_REF], [START_REF] Mandal | Mathematical models of malariaa review[END_REF], [START_REF] Ngwa | A mathematical model for endemic malaria with variable human and mosquito populations[END_REF] and references there in. Human movement has rarely been taken into account in models. Recently, it was shown that the role of human movement plays a significant role on disease reemergence and persistence [START_REF] Arino | Quarantine in a multispecies epidemic model with spatial dynamics[END_REF], [START_REF] Brauer | Mathematical Models in Population Biology and Epidemiology[END_REF], [START_REF] Martens | Malaria on the move: human population movement and malaria transmission[END_REF]. There are two standard approaches to study the spatial dynamics of vector borne disease such as malaria: partial differential equations [START_REF] Lou | A reaction-diffusion malaria model with incubation period in the vector population[END_REF], [START_REF] Xiao | Mathematical Biology Transmission dynamics for vector-borne diseases in a patchy environment[END_REF], [START_REF] Xu | A reaction-diffusion model of dengue transmission[END_REF], [START_REF] Yu | A nonlocal spatial model for Lyme disease[END_REF] and meta-population models [START_REF] Arino | A metapopulation model for malaria with transmission-blocking partial immunity in hosts[END_REF], [START_REF] Lee | the role of residence times in two-patch dengue transmission dynamics and optimal strategies[END_REF], [START_REF] Xiao | Mathematical Biology Transmission dynamics for vector-borne diseases in a patchy environment[END_REF]. More precisely, in [START_REF] Arino | A metapopulation model for malaria with transmission-blocking partial immunity in hosts[END_REF], a metapopulation malaria model was proposed using SI and SIRS models for the vectors and hosts, respectively. The mobility of human population has been proved to have a significant impact on the epidemic behavior. For example, the impact of the movement of human population on malaria transmission in different realistic situations: from rural into urban areas and colonization of heretofore unused territories was performed. Using type reproduction numbers approach developed in [START_REF] Heesterbeek | The type-reproduction number T in models for infectious disease control[END_REF], [START_REF] Roberts | A new method to estimate the effort required to control an infectious disease[END_REF], the authors identify the reservoirs of infection and evaluate the effect of control measures. We point out that the reservoirs of infection remain variously and loosely defined in the literature [START_REF] Ghinai | Malaria epidemiology in central Myanmar: identification of a multi-species asymptomatic reservoir of infection[END_REF], [START_REF] Haydon | Identifying reservoirs of infection: a conceptual and practical challenge[END_REF], [START_REF] Shannon | Sub-clinical P. falciparum infections act as year-round reservoir for malaria in the hypoendemic Chittagong Hill Districts of Bangladesh[END_REF], [START_REF] Viana | Assembling evidence for identifying reservoirs of infection[END_REF]. In this paper, a reservoir of infection is a subpopulation to which applying a (linear) control strategy suffices to eradicate the disease in the whole system [START_REF] Arino | A metapopulation model for malaria with transmission-blocking partial immunity in hosts[END_REF], [START_REF] Heesterbeek | The type-reproduction number T in models for infectious disease control[END_REF], [START_REF] Roberts | A new method to estimate the effort required to control an infectious disease[END_REF]. A reservoir may comprise multiple connected subpopulation of human and/or mosquitoes. Thus to reduce or eliminate malaria over time, a control should be applied simultaneously in the different reservoirs of infection, but the minimal fraction of susceptible individuals of each reservoir to be protected is not specified, thus a control like that should be cost a great deal of money. Therefore arise the following question, what minimal fraction of each group of the reservoir should be protected to eliminate malaria? This minimal fraction can be interpreted as the critical vaccination fraction (fraction of population to vaccinate to halt outbreak).

The main purpose of this paper is threefold: (i) to explain the steps for identifying reservoirs of malaria infection from the theoretical results derived in [START_REF] Arino | A metapopulation model for malaria with transmission-blocking partial immunity in hosts[END_REF] in order to design an efficient computational tool; (ii) determine the minimal percentage of susceptible individuals in the reservoir namely, those that should be protected to eliminate the malaria over time in the whole of the region; (iii) analysis the cost and cost-effectiveness when controlling infection within the reservoir from the minimal percentage of susceptible individuals to protect. Cost-effectiveness analysis is very important because it compares the costs and health effects of an intervention to assess the extent to which it can be regarded as providing value for money [START_REF] Alphey | A Model Framework to Estimate Impact and Cost of Genetics-Based Sterile Insect Methods for Dengue Vector Control[END_REF], [START_REF] Rich | An integrated epidemiologicaleconomic analysis of foot and mouth disease : applications to the southern cone of South America[END_REF]. This informs decision-makers who have to determine where to allocate limited healthcare resources.

II. DESCRIPTION OF MODEL FORMULATION

In this section we give a summary of the model as already discussed in [START_REF] Arino | A metapopulation model for malaria with transmission-blocking partial immunity in hosts[END_REF] before to extend it. The space was split into n geographical regions. For each geographical unity i, i = 1, . . . , n, human population was divided into three subclasses: susceptible S H,i (t), infectious I H,i (t) and semiimmune R H,i (t). Total size of the human population H i (t) = S H,i (t) + I H,i (t) + R H,i (t) and the mosquito population into two subclasses: susceptible S V,i (t) and infectious I V,i (t). Humans were assumed move from patch to patch but the movement of mosquitoes was neglected, so humans were assumed do not change their epidemiological status during travel. The model was read as follows:

Total mosquito population

V i (t) = S V,i (t)+I V,i (t).
for each i = 1, . . . , n, dS H,i dt = Λ H,i + β H,i R H,i + ρ H,i I H,i -µ H,i S H,i -Φ H,i S H,i + n j=1 m S ij S H,j - n j=1 m S ji S H,i , dI H,i dt = Φ H,i S H,i -ǫ H,i I H,i + n j=1 m I ij I H,j - n j=1 m I ji I H,i , dR H,i dt = α H,i I H,i -δ H,i R H,i + n j=1 m R ij R H,j - n j=1 m R ji R H,i , dS V,i dt = Λ V,i -µ V,i S V,i -Φ V,i S V,i , dI V,i dt = Φ V,i S V,i -µ V,i I V,i (1)
with initial conditions S H,i (0), S V,i (0) > 0,

I H,i (0), R H,i (0), I V,i (0) ≥ 0, ǫ H,i = α H,i + γ H,i + ρ H,i + µ H,i , δ H,i = β H,i + µ H,i .
In the above formulation, m π ij , π = S, I, R, denote the constant rate of travel of humans from patch j to patch i, for all i, j = 1, . . . , n, i = j. M π = [m π ij ], π = S, I, R, is the travel rate matrices. The matrices M π , π = S, R, was assumed to be irreducible and m π ii = 0, for π = S, I, R and i = 1, . . . , n. In this paper, we use the force of infection derived in [START_REF] Chitnis | Bifurcation analysis of a mathematical model for malaria transmission[END_REF] as follows:

Φ H,i = a V,i a H,i V i a V,i V i + a H,i H i σ ViHi I V,i V i , (2a)
Φ V,i = a V,i a H,i H i a V,i V i + a H,i H i σ HiVi I H,i H i + σ HiVi R H,i H i . (2b)

A. Disease free state

An equilibrium solution of system (1) at which there is no disease in any of the patches is called a disease-free equilibrium. The local stability of this point is governed by the basic reproduction number denoted by R 0 . This latter is the expected number of secondary cases produced by a typical infective individual introduced into a completely susceptible population, in the absence of any control measure [START_REF] Diekmann | On the definition and the computation of the basic reproduction ratio R0 in models for infectious diseases in heterogeneous populations[END_REF]. Next generation approach was used to derive R 0 (see [START_REF] Van Den Driessche | Reproduction numbers and subthreshold endemic equilibria for compartmental models of disease transmission[END_REF]). When R 0 < 1 the infection will die out in the long run. But if R 0 > 1 the infection will be able to spread in a population. It was shown that when disease induce mortality is large, a backward bifurcation may occur at R 0 = 1, that to say, reduce R 0 below 1 is not always sufficient to eliminate malaria.

B. Reservoir of infection

In this paper, a subgroup of patches is said to be a reservoir of infection when only targeting a control strategy which linearly reduce the number of susceptible is sufficient to eliminate the malaria in the whole of the patches. Define by J h = {H 1 , H 2 . . . , H n } the set of humans population, it was shown that a control only targeted on human population was possible to eliminate malaria. In this paper we focus on a control type targeted only to the human population. A new next generation operator M J h was defined by

M J h = [R HiHj ] 1≤i,j≤n , (3)
where R HiHj can be interpreted as the expected number of secondary infected humans in patch j that would arise from a single infected human case in patch i, in a situation where all the patches contain a completely susceptible population. Moreover we have

ρ(M J h ) < 1 ⇔ R 0 < 1 (4)
where ρ(A) is the spectral radius of a matrix A (see [START_REF] Arino | A metapopulation model for malaria with transmission-blocking partial immunity in hosts[END_REF] for details).

C. Sufficient condition for a patch to be a reservoir of infection

In [START_REF] Arino | A metapopulation model for malaria with transmission-blocking partial immunity in hosts[END_REF], it was shown that if there exists some patch ℓ in the subset {1, 2, . . . , n} such that R H ℓ H ℓ ≥ 1, then patch ℓ is an infection reservoir. In this case, we need to target simultaneously a control to the whole of susceptible population of the reservoir to eliminate malaria over time.

III. MINIMAL AND EFFICIENT CONTROL

From results obtained in [START_REF] Arino | A metapopulation model for malaria with transmission-blocking partial immunity in hosts[END_REF], arise the following question: What minimal fraction of each group of the reservoir should be protected to eliminate malaria?

Let J res be the set of reservoirs of infection. From section II-C, we have

J res = {ℓ ∈ {1, 2, . . . , n} : R H ℓ H ℓ ≥ 1} (5)
In the sequel, denotes by p the number of patches reservoirs, it is clear that p = cardinal(J res ) so that (np) represents the number of un-reservoirs patches while n is the number of patches. From [START_REF] Heesterbeek | The type-reproduction number T in models for infectious disease control[END_REF], one can define a new next generation matrix as follows:

M Jres = E T J h M J h [I n -(I n -P J h )M J h ] -1 E J h , (6)
where E J h and P J h are, respectively, n × p and n × n projection matrices satisfying (E J h ) jj = (P J h ) jj = 1 for j ∈ J res and (E J h ) jj = (P J h ) jj = 0 otherwise. M Jres is a p × p matrix satisfying ρ(M Jres ) < 1 ⇔ R 0 < 1. In the sequel, we set

M Jres = [M ij ] 1≤i,j≤p . (7)
The entries of M Jres are similar in concept to the entries of M J h .

A. Formulation of the objective function

Let S * H ℓ be the number of susceptible individuals within each patch ℓ at the disease free equilibrium, ℓ = 1, . . . , p. this number is obtained from Theorem [START_REF] Ducrot | A mathematical model for malaria involving differential susceptibility, exposedness and infectivity of human host[END_REF] in [START_REF] Arino | A metapopulation model for malaria with transmission-blocking partial immunity in hosts[END_REF].

Let f ℓ denotes the fraction of these susceptible that should be protected in patch ℓ. Then,

S * H ℓ f ℓ (resp. S * H ℓ (1 -f ℓ )
) represents the number of protected (resp. not protected) individuals at the disease-free state in the patch ℓ, ℓ = 1, . . . , p.

The fraction of susceptible in the whole population is denoted by F = (f 1 , f 2 , . . . , f p ) and those who will not need to be protected is denoted by

F = (1-f 1 , 1-f 2 , . . . , 1-f p ).
From now, one can define a new next generation matrix with variable F denoted by M Jres (F ) :

M Jres (F ) =      (1 -f 1 )M 11 (1 -f 2 )M 12 • • • (1 -f p )M 1p (1 -f 1 )M 21 (1 -f 2 )M 22 • • • (1 -f p )M 2p . . . . . . . . . . . . (1 -f 1 )M p1 (1 -f 2 )M p2 • • • (1 -f p )M pp      Note that when F = 0 then M Jres (F ) = M Jres .
To determine the minimal fractions of susceptible individuals, we set

ρ(M Jres (F )) = 1 ⇔ ρ(M Jres ) = 1 ⇔ R 0 = 1. (8)
Now, one can formulate the objective function to minimized as follows:

min 0≤F ≤1 J (F ) = p ℓ=1 S * H ℓ f ℓ , (9a)
subject to the constraint ρ(M Jres (F )) = 1

Existence of an unique solution of Eqs (9 can be easily derived by a similar argument as in [START_REF] Hill | The critical fraction for heterogeneous epidemic models[END_REF]. A powerful tool for numerical solving of Eqs ( 9) is the method of Lagrange multipliers [START_REF] Lasdon | Optimization theory for large systems[END_REF]. In the sequel we denote by F * = (f * 1 , . . . , f * p ) T the solution of Eq [START_REF] Van Den Driessche | Reproduction numbers and subthreshold endemic equilibria for compartmental models of disease transmission[END_REF].

B. Dynamics of system (1) with control over time

We recall that the minimal control is obtained by solving Eqs. [START_REF] Van Den Driessche | Reproduction numbers and subthreshold endemic equilibria for compartmental models of disease transmission[END_REF]. To test its effect on the dynamic of the system (1), we define a new force of infection, Φ H,i (t), with the value of the minimal control as follows:

Φ H,i (t) = (1 -f * i )Φ H,i (t) if i ∈ J res Φ H,i (t) otherwise. ( 10
)
for all i = 1, . . . , n. In the above equation, Φ H,i (t) represents the initial force of infection defined in Eq. ( 2), J res represents the set of reservoirs of infection defined by Eq (5), the control is only introduced within the reservoir of infection.

C. Analysis of Optimal control

We point out that the minimal control derived in the previous section is not an optimal control. The minimal control does not depend on the time, it is constant over time. An optimal control can be considered when we would like to apply a prevention depending of the time with a given final time T for disease eradication as well as budget constraint, this type of control was already investigated in [START_REF] Zorom | Optimal Control of a Spatio-Temporal Model for Malaria: Synergy Treatment and Prevention[END_REF]. In that case an optimal control problem can be formulated in the set of the identified reservoirs {1, . . . , p} ⊂ {1, . . . , n} with the following objective (cost) functional:

J(f ) = p i=1 T 0 I H,i (t) + R H,i (t) + a i 2 f 2 i (t) dt - p i=1 C i S H,i (T ) (11)
where f = (f 1 , f 2 , . . . , f p ). I H,i and R H,i represent the number of infectious and semi-immune in patch i respectively, p is the number of reservoirs patches, (np) represents the number of unreservoirs patches while n is the number of patches. The term ai 2 f 2 i (t) is the cost of prevention with a i > 0 are the weight factor in the cost of control. C i S H,i (T ) is the fitness of the susceptible at the end of the process as a result of the prevention efforts implements for the patch i = 1, . . . , p. Using a similar argument as in [START_REF] Zorom | Optimal Control of a Spatio-Temporal Model for Malaria: Synergy Treatment and Prevention[END_REF] and under suitable condition one can prove the existence of an optimal control.

D. Methodology for numerical implementation

Here, we present the steps for numerical implementation. Step 3: Compute M J h from in [3, Eq. ( 17)].

Step 4: Compute M Jres from Eq. (6).

Step 5: Solving Eq. ( 9) to find minimal control.

Step 6: Solving Eqs. (1) using the minimal control obtained in step 5 to represent the dynamic of malaria model.

IV. COSTS AND COST-EFFECTIVENESS OF MALARIA CONTROL FOR TWO STRATEGIES

Cost-effectiveness analysis compares the costs and health effects of an intervention to assess the extent to which it can be regarded as providing value for money [START_REF] Alphey | A Model Framework to Estimate Impact and Cost of Genetics-Based Sterile Insect Methods for Dengue Vector Control[END_REF], [START_REF] Rich | An integrated epidemiologicaleconomic analysis of foot and mouth disease : applications to the southern cone of South America[END_REF]. This informs decision-makers who have to determine where to allocate limited healthcare resources. It is performed in this section to assess the effectiveness of a control targeted on the minimal fraction obtained in previous section considering two strategies of control over a reference period T -T I , where T I is the initial time for which the control is introduced and T the final time.

Strategy 1 : Protecting the minimal fraction of susceptible individuals to eliminate malaria in the reservoir of infection over the period T -T I .

Strategy 2 : Protection of any fraction of susceptible individuals greater than the minimal fraction for eradicate malaria at the same over the period T -T I .

To achieve this purpose for our above strategies, we need to compare the differences between the cost and health outcome. This is done by calculating the incremental cost effectiveness ratio (ICER) defined as follows:

ICER = C * -C HE * -HE (12)
where HE * (resp. HE) denotes the health effect of strategy 1 (resp. strategy 2) and C * (resp. C) denotes the present value (at time t = 1) of costs for the whole project of strategy 1 (resp. strategy 2). A similar method is used in [START_REF] Okosun | Impact of optimal control on the treatment of HIV/AIDS and screening of unaware infectives[END_REF].

A. Method to calculate costs C (resp. C * ) for strategy 2 (resp. strategy 1) Let c t ℓ denotes financial cost of protecting one individual for one unit of time t (here one month) in patch ℓ. Because f l S * H l is the number of individuals to be protect in patch ℓ then c t ℓ f ℓ S * H ℓ is the total required financial cost to protect all individuals in patch ℓ = 1, . . . , p. It follows that the total cost allowed to strategy 2 (resp. strategy 1) is given by

C t = p l=1 c t l f l S * H l , and
C * t = p l=1 c t l f * l S * H l t = 1, . . . , T
When cost effectiveness ratios are reported with discounting of future costs and benefits due to the longer-term implementation time, if we denote by r s the social discount rate, we have

C * := T t=1 C * t (1 + r) t-1 and C := T t=1 C t (1 + r) t-1 ,

B. Method to calculate health effect of strategy 1 HE (resp. of strategy 2 HE

* ) HE = 1 T -T I T TI p l=1 S f H l (t)dt and HE * = 1 T -T I T TI p l=1 S f * H l (t)dt,
where S f H l (t) denote the number of susceptible at time t when Φ H,i (t) = Φ H,i and S f * H l (t) denote the number of susceptible at time t when Φ H,i (t) = (1f * i )Φ H,i .

V. SIMULATION EXPERIMENTS

A. Parameters values

To test the method, we have assumed that the travel rates of humans depend on the distance between cities. We set

M S = M I = M R = 10 -3 n -1 • [|i -j|], 2 ≤ i,

B. Results and Discussion

The computation provides the basic reproductive number value: R 0 = 1.3239. That to say, without control, one has malaria that persists in the human population.

1) Reservoir of infection: Numerical implementation of the method shown in Appendix allowed to identify the set of reservoirs shown on Table II andFigure 2) Dynamics of system [START_REF] Alphey | A Model Framework to Estimate Impact and Cost of Genetics-Based Sterile Insect Methods for Dengue Vector Control[END_REF] with/ or without minimal control: Figure 2 show the endemicity of malaria without control. Indeed, Although others cities are not reservoirs of The comparison between ICER(1) and ICER(2) shows a cost saving of 7,2325 for strategy 1 over strategy 2. The ICER for strategy 1 indicates the strategy 2 is "strongly dominated". Strategy 2 is then more costly and less effective than strategy 1. With this result, we therefore conclude that strategy 1 is the less cost and most effective.

VI. CONCLUSION

In this article, we have extended the model derived in [START_REF] Arino | A metapopulation model for malaria with transmission-blocking partial immunity in hosts[END_REF] to give a numerical method to explain the steps for identifying reservoirs of malaria infection within n connected regions with the explicit movement of human population. This method is intended to design an efficient computational tool.

In the one hand, we have shown how to determine the minimal percentage of susceptible individuals in the reservoirs that should be protected to eliminate malaria over time in the whole population. The minimal percentage quantifies the degree of malaria risk in the reservoirs areas. It is regulated by the mobility flux of human population between patches. Thus for the public health decision makers, when datasets on human migration flux, demographic and epidemic are known, this method can aid to estimate the minimal percentage of susceptible individuals to be protected. We have explained that the minimal percentage is not necessarily an optimal control but allows to reduce the cost of intervention. It is constant over time. An optimal control can be considered when we would like to apply a preventative depending of the time with a given final time T for disease eradication as well as a budget constraint. In that case we have shown how to formulate such a problem.

In the second hand, the costs and cost-effectiveness of malaria control interventions is performed considering two strategies of control: (i) protecting the minimal fraction of susceptible individual; (ii) protecting any fraction greater than the minimal fraction. Cost-effectiveness analysis shows that the less cost and more effective strategy is to protect the minimal fraction of susceptible individual in the reservoir of infection. Biologically relevant parameters have been estimated and used to fulfill numerical simulations of the model. These simulations was implemented through an example using Matlab (www.matlab.org). Simulation of the evolution over month of the density of human in infectious class (I H,i ) and semi-immune class (R H,i ), as well as the density of infectious mosquitoes (I V,i ) for 20 cities was shown on Figure 23. Together with the both Figures and the Cost-infectiveness results, we argue that Strategy (ii) is then more costly and less effective than strategy (i). With this result, we therefore conclude that strategy (i) is the less cost and most effective, namely the minimal fraction of population to vaccinate (or protect) to halt outbreak is efficient.

Our study will be useful for spatial vaccination programs in which optimization methods are needed to minimize the costs. Moreover thanks to this study, when the datasets on human migration flux, demographic and epidemic are known, one can estimate the minimal percentage of susceptible individuals to be protected. The method developed in this paper may be allow to the implementation of a software for monitoring spatio-temporal variations in malaria epidemic risk.

Step 1 : 2 :

 12 Compute principal next generator matrix K from [3, Theorem 3]. Step Compute next generator matrix extracted K from [3, Corollary 1].

1 .

 1 Cities number 2,3,5,6,8,10,12,13,15,16 and 20 represent the reservoirs of infection based on the value of the minimal fraction F * := (f * 1 , . . . , f * 20 ). Indeed, one considers that a city ℓ is a reservoir when f * ℓ = 0.

Fig. 1 .

 1 Fig. 1. This figure shows the cities which represent reservoirs of infection when we use the data in Table III and the algorithm presented in this paper. Cities number 2,3,5,6,8,10,12,13,15,16 and 20 represent the reservoirs of infection while cities 1,4,7,9,11,14,17,18,19 are not. Moreover this figure provides the minimal percentage (i.e. 100F * , where F * := (f * 1 , . . . , f * 20 ) is shown on Table (II)) of human within each reservoir that should be protected to eliminate malaria in the whole of the population (human and mosquitoes).

[

Fig. 2 .

 2 Fig. 2. Simulation of the evolution over month of the density of human in infectious class (I H,i ) and semi-immune class (R H,i ), as well as the density of infectious mosquitoes (I V,i ) for 20 cities when we have no control measures. Initial condition: S H,i (0) = 500, i = 1, . . . , 20, I H,1 (0) = 10, and I H,i (0) = 0, i=2,. . . , 20; R H,i (0) = 0, i = 1, . . . , 20; S V,i (0) = 100, i = 1, . . . , 20; I V,i (0) = 0, i = 1, . . . , 20.

[

Fig. 3 .

 3 Fig. 3. Simulation of the evolution over month of the density of human in infectious class (I H,i ) and semi-immune class (R H,i ), as well as the density of infectious mosquitoes (I V,i ) for 20 cities when the minimal percentage of susceptible human shown in Table II are protected 100 months post-infection. Initial condition: S H,i (0) = 500, i = 1, . . . , 20, I H,1 (0) = 10, and I H,i (0) = 0, i=2,. . . , 20; R H,i (0) = 0, i = 1, . . . , 20; S V,i (0) = 100, i = 1, . . . , 20; I V,i (0) = 0, i = 1, . . . , 20.

  Table III summarizes the model parameters as well as their biological interpretation and Table I summarizes the state variables.

TABLE II THE

 II MINIMAL FRACTION F * AND THE MAXIMAL FRACTION F DEPENDING OF THE PARAMETERS VALUES OF a H AND a V .

	City	1	2	3	4	5	6	7
	a H	1.6	2	2.5	1.5	2.1	2.3	1.2
	a V	0.6	0.65	0.35	0.4	0.3	0.5	0.2
	F *	0	0.6	0.80	0	0.63	0.70	0
	F	0	1	1	0	1	1	0
	City	8	9	10	11	12	13	14
	a H	1.9	1.7	2.4	1.6	2	2.5	1.5
	a V	0.55	0.8	0.45	0.6	0.65	0.35	0.4
	F *	0.48	0	0.70	0	0.51	0.72	0
	F	1	0	1	0	1	1	0
	City	15	16	17	18	19	20
	a H	2.1	2.3	1.2	1.9	1.7	2.4
	a V	0.3	0.5	0.2	0.55	0.8	0.45
	F *	0.56	0.65	0	0	0	0.71
	F	1	1	0	0	0	1

TABLE III BASELINE

 III VALUES FOUND IN THE LITERATURE[START_REF] Arino | A metapopulation model for malaria with transmission-blocking partial immunity in hosts[END_REF],[START_REF] Ducrot | A mathematical model for malaria involving differential susceptibility, exposedness and infectivity of human host[END_REF],[START_REF] Chitnis | Bifurcation analysis of a mathematical model for malaria transmission[END_REF],[START_REF] Zongo | Modélisation mathématique de la dynamique de la transmission du paludisme[END_REF]. WE HAVE ASSUMED THAT THE PARAMETERS ARE IDENTICAL IN ALL THE PATCHES EXCEPTED a H,i THAT VARIES FROM A PATCH TO ANOTHER AND THE RATE OF TRAVEL m π ij THAT DEPENDS ON THE DISTANCE BETWEEN PATCHES.

	Symbol	Description	Values
	Λ H,i :	recruitment into the susceptible class	0.4
	α H,i :	rate of progression from the
		infectious to the semi-immune class	0.0035
	ρ H,i :	rate of recovery from being infectious	0.035
	β H,i :	rate of recovery from being semi-immune	5.5 × 10 -4
	γ H,i :	disease induced death rate	9 × 10 -5
	µ H,i :	natural death rate	5 × 10 -4
	Λ V,i :	recruitment into the susceptible class	500
	µ V,i :	natural death rate	0.04
	σ H i V i :	probability of transmission from an infect-
		ious human to a susceptible mosquito	0.48.
	σ H i V i :	probability of transmission from a semi-
		immune human to a susceptible mosquito	0.048
	σ V i H i :	probability of transmission from an infec-
		tious mosquito to a susceptible human	0.022
	a H,i :	maximum number of mosquito bites
		a human can receive per unit time	Table II
	a V,i :	number of times one mosquito would
		bite humans per unit time	Table II
	M π :	π = S, I, R rate of travel
		of humans from patch j to patch i	Eq. (13)


Messaouda Ahmane

Isma Bouchemakh

Éric Sopena

On the Broadcast Independence Number of Caterpillars

Keywords: Independence, Distance, Broadcast independence, Caterpillar. MSC 2010: 05C12, 05C69

Let G be a simple undirected graph. A broadcast on G is a function

, where d G (u, v) denotes the distance between u and v in G. The broadcast independence number of G is then defined as the maximum cost of an independent broadcast on G.

In this paper, we study independent broadcasts of caterpillars and give an explicit formula for the broadcast independence number of caterpillars having no pair of adjacent trunks, a trunk being an internal spine vertex with degree 2.

Introduction

All the graphs we consider in this paper are simple and loopless undirected graphs. We denote by V (G) and E(G) the set of vertices and the set of edges of a graph G, respectively.

For any two vertices u and v of G, the distance d G (u, v) between u and v in G is the length (number of edges) of a shortest path joining u and v. The eccentricity e G (v) of a vertex v in G the maximum distance from v to any other vertex of G. The minimum eccentricity in G is the radius rad(G) of G, while the maximum eccentricity in G is the diameter diam(G) of G. Two vertices u and v with d G (u, v) = diam(G) are said to be antipodal.

A function f : V (G) → {0, . . . , diam(G)} is a broadcast if for every vertex v of G, f (v) ≤ e G (v). The value f (v) is called the f -value of v. Given a broadcast f on G, an f -broadcast vertex is a vertex v with f (v) > 0. The set of all f -broadcast vertices is denoted V + f . If u ∈ V + f is a broadcast vertex, v ∈ V (G) and d G (u, v) ≤ f (u), we say that u f -dominates v. In particular, every f -broadcast vertex f -dominates itself. The cost cost(f ) of a broadcast f on G is given by cost

(f ) = v∈V (G) f (v) = v∈V + f f (v).
A broadcast f on G is a dominating broadcast if every vertex of G is f -dominated by some vertex of V + f . The minimum cost of a dominating broadcast on G is the broadcast domination number of G, denoted γ b (G). A broadcast f on G is an independent broadcast if every fbroadcast vertex is f -dominated only by itself. The maximum cost of an independent broadcast In this paper, we determine the broadcast independence number of caterpillars having no pair of adjacent trunks. The paper is organised as follows. We introduce in the next section the main definitions and a few preliminary results on independent broadcasts of caterpillars. We then consider in Section 3 the case of caterpillars having no pair of adjacent trunks and prove our main result, which gives an explicit formula for the broadcast independence number of such caterpillars. We finally propose a few directions for future research in Section 4.

Preliminaries

Let G be a graph and H be a subgraph of G. Since d H (u, v) ≥ d G (u, v) for every two vertices u, v ∈ V (H), every independent broadcast f on G satisfying f (u) ≤ e H (u) for every vertex u ∈ V (H) is an independent broadcast on H. Hence we have:

Observation 4 If H is a subgraph of G and f is an independent broadcast on G satisfying f (u) ≤ e H (u) for every vertex u ∈ V (H), then the restriction f H of f to V (H) is an independent broadcast on H.

A caterpillar of length k ≥ 0 is a tree such that removing all leaves gives a path of length k, called the spine. Following the terminology of [START_REF] Seager | Dominating Broadcasts of Caterpillars[END_REF], a non-leaf vertex is called a spine vertex and, more precisely, a stem if it is adjacent to a leaf and a trunk otherwise. A leaf adjacent to a stem v is a pendent neighbour of v. We will always draw caterpillars with the spine on a horizontal line, so that we can speak about the leftmost of rightmost spine vertex of a caterpillar.

Note that a caterpillar of length 0 is nothing but a star K 1,n , for some n ≥ 1. The independent broadcast number of a star is easy to determine. Observation 5 For every integer n ≥ 1,

β b (K 1,n ) = n.
Indeed, an optimal broadcast f of K 1,n is obtained by setting to 1 the f -value of every pendent vertex of K 1,n , if n > 1, or of one of the two vertices of K 1,1 . Therefore, in the rest of the paper, we will only consider caterpillars of length k ≥ 1.

Let

N * = N \ {0}. We denote by CT (λ 0 , . . . , λ k ), k ≥ 1, with (λ 0 , . . . , λ k ) ∈ N * × N k-1 × N * , the caterpillar of length k ≥ 1 with spine v 0 . . . v k such that each spine vertex v i has λ i pendent neighbours. Note that for any caterpillar CT of length k ≥ 1, diam(CT ) = k + 2.
For every i such that λ i > 0, 0 ≤ i ≤ k, we denote by 1 i , . . . , λ i i the pendent neighbours of v i . Moreover, we denote by CT [a, b], 0 ≤ a ≤ b ≤ k, the subgraph of CT induced by vertices v a , . . . , v b and their pendent neighbours. The caterpillar CT (1, 0, 2, 1, 1, 2, 1, 0, 3) is depicted in Figure 1.

Let f be an independent broadcast on a caterpillar CT = CT (λ 0 , . . . , λ k ). We denote by f * the associated mapping from {v 0 , . . . , v k } to N defined by

f * (v i ) = f (v i ) + j=λ i j=1 f ( j i ), if λ i > 0, and f * (v i ) = f (v i ) otherwise,
for every i, 0 ≤ i ≤ k. Intuitively speaking, when λ i > 0, f * (v i ) gives the "weight" of the star-graph consisting of the vertex v i together with its pendent neighbours.

We will say that two independent broadcasts f 1 and f 2 on CT are similar whenever f * 1 = f * 2 . Observe that any two similar independent broadcasts have the same cost.

From Observation 1, we get that β b (CT ) ≥ 2(k+1) for every caterpillar CT = CT (λ 0 , . . . , λ k ). In particular, the function

f c on V (CT ) defined by f c ( 1 0 ) = f c ( 1 k ) = k + 1 and f c (u) = 0 for every vertex u ∈ V (CT ) \ { 1 0 , 1 k
} is an independent broadcast on CT with cost 2(k + 1). In the following, we will call any independent broadcast f similar to f c and such that

|V + f | = 2 a canonical independent broadcast.
The following lemma shows that, for any caterpillar CT = CT (λ 0 , . . . , λ k ), no independent broadcast f on CT with f (v) > 0 for some stem v can be optimal.

Lemma 6 If CT = CT (λ 0 , . . . , λ k ) is a caterpillar of length k ≥ 1 and f is an independent broadcast on CT with f (v i ) > 0 for some stem v i , 0 ≤ i ≤ k, then there exists an independent broadcast f on CT with cost(f ) > cost(f ).

Proof. Since f (v i ) > 0 and f is an independent broadcast, we have f ( j i ) = 0 for every j,

1 ≤ j ≤ λ i . Consider the function f defined by f (v i ) = 0, f ( 1 i ) = f (v i ) + 1 and f (u) = f (u) for every vertex u ∈ V (CT ) \ {v i , 1 i }. Since d CT ( 1 i , u) = d CT (v i , u) + 1 for every vertex u ∈ V (CT ) \ { 1
i }, we get that f is an independent broadcast on CT . Moreover, we clearly have cost(f ) = cost(f ) + 1.

The following lemma shows that for every optimal independent broadcast on a caterpillar, at least one pendent vertex of each of the end-vertices of the spine is a broadcast vertex.

Lemma 7 Let CT = CT (λ 0 , . . . , λ k ) be a caterpillar of length k ≥ 1. If f is an optimal independent broadcast on CT , then f * (v 0 ) -f (v 0 ) = 0 and f * (v k ) -f (v k ) = 0.
Proof. We know by Lemma 6 that f (v 0 ) = 0. Suppose, contrary to the statement of the lemma, that f ( j 0 ) = 0 for every j, 1 ≤ j ≤ λ 0 . Let u be the f -broadcast vertex that dominates 1 0 and let f (u) = x. By Lemma 6, u is either a leaf or a trunk. If u is a leaf, say u = j i , 1 ≤ i ≤ k, 1 ≤ j ≤ λ i , let f be the mapping defined by f ( 1 0 ) = x + i, f (u) = 0 and f (u ) = f (u ) for every vertex u ∈ V (CT ) \ { 1 0 , u}. Note that every vertex which was f -dominated by u is now f -dominated by 1 0 . The mapping f is thus an independent (cost(f ) + i)-broadcast on CT , contradicting the optimality of f .

If u is a trunk, say u = v i , 1 ≤ i ≤ k -1, we similarly define a mapping f by letting f ( 1 0 ) = x + i + 1, f (u) = 0 and f (u ) = f (u ) for every vertex u ∈ V (CT ) \ { 1 0 , u}. The mapping f is thus an independent (cost(f ) + i + 1)-broadcast on CT , again contradicting the optimality of f . The case f ( j k ) = 0 for every j, 1 ≤ j ≤ λ k , follows by symmetry.

Observe that Lemma 7 can be extended to trees as follows:

Lemma 8 Let T be tree and T be a subtree of T , of order at least 2, with root r. Let f be an optimal independent broadcast on T . If r is an f -broadcast vertex, then T contains at least one other f -broadcast vertex. In particular, if T is a subtree of height 1 (that is, e T (r) = 1), then f (r) = 0.

Proof. Suppose to the contrary that f (r) > 0 and f (u) = 0 for every vertex u ∈ V (T ) \ {r}.

Let t = e T (r) and t = e T -(T -r) (r). If f (r) < t , the independent broadcast f given by f (v) = f (r) for some vertex v in T with d T (r, v) = t and f (u) = f (u) for every vertex u ∈ V (T ) \ {v} is such that cost(f ) = cost(f ) + f (r), contradicting the optimality of f . If f (r) ≥ t , then r is the unique f -broadcast vertex, which implies cost(f ) < 2(diam(T )-1), again contradicting the optimality of f by Observation 1.

Hence t > f (r) ≥ t . Let now v be any neighbour of r in T . Since t > f (r) ≥ t , we have e T (v) = e T (r) + 1 = t + 1 > f (r) + 1. The function f defined by f (r) = 0, f (v) = f (r) + 1 and f (u) = f (u) for every vertex u ∈ V (T ) \ {r, v} is therefore an independent broadcast on T with cost(f ) = cost(f ) + 1, contradicting the optimality of f . This completes the proof.

3 Caterpillars with no pair of adjacent trunks

In this section we determine the broadcast independence number of caterpillars with no pair of adjacent trunks. We first introduce some notation and useful lemmas. We say that an independent broadcast f of a caterpillar CT is an optimal non-canonical independent broadcast on CT if

(i) |V + f | = 2 or f * = f * c (f is non-canonical)
, and (ii) for every independent broadcast f on CT with

|V + f | = 2 or f * = f * c , cost(f ) ≥ cost(f ) (f is
optimal among all non-canonical independent broadcasts).

Let CT = CT (λ 0 , . . . , λ k ) be a caterpillar of length k ≥ 1 with no pair of adjacent trunks. We denote by

λ(CT ) = i=k i=0 λ i
the number of leaves of CT , and by

τ (CT ) = |{i | 1 ≤ i ≤ k -1 and λ i = 0}|
the number of trunks of CT .

We will compute the broadcast independence number of a caterpillar with no pair of adjacent trunks by counting the number of some specific patterns. More precisely, we say that a pattern of length p + 1, Π = π 0 . . . π p , p ≥ 0, π i ∈ N for every i, 0 ≤ i ≤ p, occurs in a caterpillar CT = CT (λ 0 , . . . , λ k ) if there exists an index i 0 , 0 ≤ i 0 ≤ k -p, such that CT [i 0 , i 0 + p] = CT (π 0 , . . . , π p ), that is, λ i 0 +j = π j for every j, 0 ≤ j ≤ p. We will also say that the caterpillar CT contains the pattern Π and that the subgraph CT (λ i 0 , . . . , λ i 0 +p ) of CT is an occurrence of the pattern Π. For instance, the caterpillar CT (1, 0, 2, 1, 1, 2, 1, 0, 3), depicted on Figure 1, contains once the pattern 211 and twice the pattern 10.

We now extend the notation for patterns as follows:

• By π + i , we mean a spine vertex having at least π i pendent neighbours; • By π - i , we mean a spine vertex having at most π i pendent neighbours; • By [Π, we mean that the pattern Π occurs and starts at the leftmost stem v 0 ,

• By Π], we mean that the pattern Π occurs and ends at the rightmost stem v k ,

• By {Π, Π }, we mean either the pattern Π or the pattern Π .

• By π 0 (π 1 π 2 ) +r π 3 , we mean a maximal pattern of the form

π 0 π 1 π 2 π 3 or π 0 π 1 π 2 . . . π 1 π 2 r times, r ≥ 2 π 3 ,
where maximal here means that the subpattern π 1 π 2 is repeated at least once and as many times as possible.

• By π 0 (π 1 π 2 ) * r π 3 , we mean a maximal pattern of the form

π 0 π 3 , π 0 π 1 π 2 π 3 or π 0 π 1 π 2 . . . π 1 π 2 r times, r ≥ 2 π 3 ,
where maximal here means that the subpattern π 1 π 2 is repeated as many times as possible.

[11 We can also combine these notations, so that, for instance, π + i ] denotes that the rightmost stem v k has at least π i pendent neighbours, and {π i , [}Π denotes either the pattern π i Π or the pattern [Π.

+ 1 + 11 + 1 + 2 -(02 -) +r 1 + 02 -(02 -) * r ]
One can check that the caterpillar CT (1, 0,

, depicted on Figure 1, contains once each of the four patterns [START_REF] Blair | Broadcast domination algorithms for interval graphs, series-parallel graphs and trees[END_REF][START_REF] Bouchemakh | On a conjecture of Erwin[END_REF], 2 + ] and 2111 + , twice the pattern 0{2, 3}, and thrice the pattern 1 + 1 + 1 + . On the other hand, the caterpillar CT (1, 0, 2, 0, 2, 0, 2, 1, 0, 3) contains only once the pattern 1 + 0(20) +r 1 + , namely on the sub-caterpillar CT (1, 0, 2, 0, 2, 0, 2) with explicit pattern 1020202.

For any pattern Π and any caterpillar CT , we will denote by # CT (Π) the number of occurrences of the pattern Π in CT . Moreover, if M is an occurrence of Π in CT , we define the value

α 1 (M ) = max{0, # M (1) -1},
that is, the number of stems v i in M with λ i = 1 minus 1-or 0 if M contains no such stem-, and the value

α 2 (M ) = α 1 (M ) + # M ([1 + ) + # M (1 + ]),
that is, α 1 (M ) plus 0, 1 or 2, depending on whether M contains no end-vertex of CT , one end-vertex of CT or both end-vertices of CT , respectively. We then extend the functions α 1 and α 2 to the whole caterpillar CT by setting

α 1 (CT ; Π) = M occurrence of Π α 1 (M ) and α 2 (CT ; Π) = M occurrence of Π α 2 (M ).
Finally, for any caterpillar CT , we define the value β * (CT ) as follows:

β * (CT ) = λ(CT ) + τ (CT ) + # CT ({1 + , [}1{1 + , ]}) + α 1 (CT ; 1 + 2 -(02 -) +r 1 + ) + α 2 (CT ; 02 -(02 -) * r 0) + α 2 (CT ; [2 -(02 -) * r 0) + α 2 (CT ; 02 -(02 -) * r ]).
Sample patterns involved in the above formula are illustrated in Figure 2. In the figure, a pattern with a line to the left or right hand side of its spine cannot occur at the left or right end of the caterpillar, respectively. A pattern with a dashed line to the left or right hand side of its spine can occur at the left or right end of the caterpillar, respectively, or in the middle of the caterpillar. A dashed edge is an optional edge (used for pattern 2 -, corresponding to a spine vertex with either one or two pendent neighbours).

Let us say that two distinct occurrences of patterns overlap if they share a common vertex. Due to the specific structure of the patterns used in the above formula (and, in particular, of the maximality of the number of repetitions of subpatterns of the form Π +r or Π * r ), we have the following:

Observation 9 In every caterpillar CT of length k ≥ 1,
1. no occurrence of the pattern 02 -(02 -) * r 0 can overlap with an occurrence of a pattern

{1 + , [}1{1 + , ]}, 1 + 2 -(02 -) +r 1 + , 02 -(02 -) * r 0, [2 -(02 -) * r 0 or 02 -(02 -) * r ],
2. no occurrence of the pattern [2 -(02 -) * r 0 can overlap with an occurrence of a pattern

{1 + , [}1{1 + , ]}, or 1 + 2 -(02 -) +r 1 + ,
3. no occurrence of the pattern 02 -(02 -) * r ] can overlap with an occurrence of a pattern

{1 + , [}1{1 + , ]} or 1 + 2 -(02 -) +r 1 + , 4. if two occurrences of the patterns [2 -(02 -) * r 0 and 02 -(02 -) * r ] overlap, then CT is a caterpillar with pattern [2 -(02 -) * r ].
We first prove that every caterpillar with no pair of adjacent trunks admits an independent broadcast f with cost(f ) = β * (CT ).

Lemma 10 Every caterpillar CT = CT (λ 0 , . . . , λ k ) of length k ≥ 1, with no pair of adjacent trunks, admits an independent broadcast f with cost(f ) = β * (CT ).

Proof. We will construct a sequence of independent broadcasts f 1 , . . . , f 4 , step by step, such that cost(f 4 ) = β * (CT ). Each independent broadcast f i , 2 ≤ i ≤ 4, is obtained by possibly modifying the independent broadcast f i-1 and is such that cost(f i ) ≥ cost(f i-1 ). Moreover, for each independent broadcast f i , 1 ≤ i ≤ 4, we will have f i (v) = 0 whenever v is a stem. These modifications are illustrated in Figures 3 and4, using the same drawing conventions as in Figure 2. Only useful broadcast values are given in these figures. These figures should help the reader to see that all the proposed modifications lead to a new valid independent broadcast.

Step 1. Let f 1 be the mapping defined by f 1 (v) = 1 if v is a pendent vertex or a trunk, and

f 1 (v) = 0 otherwise. Clearly, f 1 is an independent broadcast on CT with cost(f 1 ) = λ(CT ) + τ (CT ).
Step 2. Let f 2 be the mapping defined by

f 2 (v) = 2 if v = 1 i for some i, 0 ≤ i ≤ k, such that (i) λ i = 1, (ii) i = 0 or λ i-1 ≥ 1, and (iii) i = k or λ i+1 ≥ 1, and f 2 (v) = f 1 (v) otherwise (see Figure 3(a)). Again, f 2 is an independent broadcast on CT with cost(f 2 ) = cost(f 1 ) + # CT ({1 + , [}1{1 + , ]}).
Step 3. Suppose that CT contains the pattern 1 + 2 -(02 -) +r 1 + , of length 2r + 3, and let M = CT [i 0 , i 0 +2r +2] be the corresponding occurrence of this pattern. We thus have f 2 (v) = 1 for every trunk of M and for every pendent neighbour of a stem vertex v j on M with i 0 + 1 ≤ j ≤ i 0 + 2r + 1. Hence, the cost of the restriction

f 2 of f 2 to M is cost(f 2 ) = f * 2 (v i 0 ) + λ(M [i 0 + 1, i 0 + 2r + 1]) + τ (M ) + f * 2 (v i 0 +2r+2 ).
We modify f 2 as follows, to obtain

f 3 . If the subgraph M [i 0 + 1, i 0 + 2r + 1] contains a stem vertex v i with λ i = 1, we let 1 1 -→ 2 1 1 1 1 -→ 1 2 1 (a) From f 1 to f 2 1 1 1 1 1 1 1 -→ 1 1 0 3 0 1 1 (b) From f 2 to f 3 , pattern 1 + 201021 + , cost(f 3 ) = cost(f 2 ) + (1 -1) 1 1 1 1 1 1 1 1 1 1 1 -→ 1 1 0 3 0 3 0 0 3 0 2 (c) From f 2 to f 3 , pattern 1 + 2010201011 + , cost(f 3 ) = cost(f 2 ) + (3 -1)
Figure 3: Proof of Lemma 10: from f 1 to f 3

• f 3 ( 1 i 0 +1 ) = 2 if λ i 0 +1 = 1, • f 3 ( 1 i 0 +2r+1 ) = 2 if λ i 0 +2r+1 = 1, • f 3 ( 1 i 0 +2j+1 ) = 3 (and f 3 ( 2 i 0 +2j+1 ) = 0 if λ i 0 +2j+1 = 2) for every j, 1 ≤ j ≤ r -1, • f 3 (v i 0 +2j ) = 0 for every j, 1 ≤ j ≤ r, (see Figure 3(b) and (c)). The cost of the restriction f 3 of f 3 on M is then cost(f 3 ) = cost(f 2 ) + max{0, # M [i 0 +1,i 0 +2r+1] (1) -1} = cost(f 2 ) + α 1 (M ).
By Observation 9, two occurrences of the pattern 1 + 2 -(02 -) +r 1 + can only overlap on their end-vertices. Therefore, doing the above modification for every occurrence of the pattern

1 + 2 -(02 -) +r 1 + in M , the so-obtained independent broadcast f 3 satisfies cost(f 3 ) = cost(f 2 ) + α 1 (CT ).
Step 4. Suppose first that CT contains the pattern 02 -(02 -) * r 0, of length 2r + 3, and let

M = CT [i 0 , i 0 + 2r + 2], i 0 ≥ 1, i 0 + 2r + 2 ≤ k -1,
be the corresponding occurrence of this pattern. We thus have f 2 (v) = 1 for every trunk of M and for every pendent neighbour of a stem vertex v j on M with i 0 + 1 ≤ j ≤ i 0 + 2r + 1. Hence, the cost of the restriction

f 3 of f 3 to M is cost(f 3 ) = f * 3 (v i 0 ) + λ(M ) + τ (M [i 0 + 1, i 0 + 2r + 1]) + f * 3 (v i 0 +2r+2
). We modify f 3 as follows, to obtain

f 4 . If the subgraph M [i 0 + 1, i 0 + 2r + 1] contains a stem vertex v i with λ i = 1, we let • f 4 ( 1 i 0 +2j+1 ) = 3 (and f 4 ( 2 i 0 +2j+1 ) = 0 if λ i 0 +2j+1 = 2) for every j, 0 ≤ j ≤ r, • f 4 (v i 0 +2j ) = 0 for every j, 0 ≤ j ≤ r, (see Figure 4(a)). The cost of the restriction f 4 of f 4 on M is then cost(f 4 ) = cost(f 3 ) + max{0, # M (1) -1} = cost(f 3 ) + α 2 (M ).
Suppose now that CT contains the pattern [2 -(02 -) * r 0, of length 2r + 2, and let M = CT [0, 2r + 1] be the corresponding occurrence of this pattern. Doing the same type of modification as above (see Figure 4(b)), the cost of the restriction

f 4 of f 4 on M is then cost(f 4 ) = cost(f 3 ) + max{0, # M (1) -1} + 1 = cost(f 3 ) + α 2 (M ).
Finally, if CT contains the pattern 02 -(02 -) * r ] and CT is not a caterpillar with pattern [2 -(02 -) * r ], the same type of modification leads to the same property.

By Observation 9, no two occurrences of the patterns 02 -(02 -) * r 0 and [2 -(02 -) * r 0 (or 02 -(02 -) * r 0 and 02 -(02 -) * r ]) can overlap. Therefore, doing the above modification for every occurrence of these patterns in M , the so-obtained independent broadcast

f 4 satisfies cost(f 4 ) = cost(f 3 ) + α 2 (CT ) = β * (CT ).
This completes the proof.

The next lemma shows that if f is an optimal non-canonical independent broadcast on a caterpillar CT with no pair of adjacent trunks, with cost(f ) > 2(diam(CT ) -1), then there exists an optimal non-canonical independent broadcast f on CT such that the f -values of the pendent neighbours of v 0 and v k only depend on the values of λ 0 , λ 1 and λ k-1 , λ k , respectively: Lemma 11 Let CT = CT (λ 0 , . . . , λ k ) be a caterpillar of length k ≥ 1, with no pair of adjacent trunks. If f is an optimal non-canonical independent broadcast on CT with cost(f ) > 2(diam(CT ) -1), then there exists an optimal non-canonical independent broadcast f on CT , thus with cost( f ) = cost(f ), such that, for every i ∈ {0, k}, we have

f 3 to f 4 1. if λ i = 1 and λ i ≥ 1, then f ( 1 i ) = 2, 2. if λ i = 1 and λ i = 0, then f ( 1 i ) = 3, 3. if λ i = 2 and λ i ≥ 1, then f ( 1 i ) = f ( 2 i ) = 1, 4. if λ i = 2 and λ i = 0, then f ( 1 i ) = 3 and f ( 2 i ) = 0, 5. if λ i ≥ 3, then f ( j i ) = 1 for every j, 1 ≤ j ≤ λ i , where i = 1 if i = 0, or i = k -1 if i = k.
Proof. Note first that if such a broadcast f exists, then, by Lemma 6, f (u) = 0 for every stem u of CT . Therefore, the value of 1≤j≤λ i f ( j i ) cannot be strictly less than the value claimed in the lemma since otherwise it would contradict the optimality of f . By symmetry, it is enough to prove the lemma for the pendent neighbours of v 0 . Let CT 0 = CT (λ 0 , . . . , λ k ) be a minimal counterexample, with respect to the subgraph order, to the lemma. That is, every sub-caterpillar of CT 0 satisfies the statement of the lemma and, for every optimal non-canonical independent broadcast f on CT 0 with cost(f ) > 2(diam(CT ) -1), there is a pendent neighbour, say 1 0 without loss of generality, of v 0 such that f ( 1 0 ) = x and x is strictly greater than the value claimed by the lemma (note that, in case 3, if f ( 1 0 ) = 2 (resp. 0) and f ( 2 0 ) = 0 (resp. 2), then we can equivalently assign the value 1 to both of them). We will prove that such a minimal counterexample cannot exist.

Let f 0 be any such independent broadcast on CT 0 for which the value f ( 1 0 ) = x is minimal. We thus have x ≥ 3 whenever λ 1 > 0 or λ 0 ≥ 3 (since in this latter case we can assign value 1 to each of the at least three pendent neighbours of v 0 , and thus x = 2 would imply that f 0 is not optimal), and x ≥ 4 whenever λ 1 = 0.

Since f 0 ( 1 0 ) = x > 1, we have f * 0 (v i ) = 0 for every i, 1 ≤ i ≤ x -2, and f 0 (v x-1 ) = 0. Moreover, x -1 < k since f 0 is a non-canonical independent broadcast, and v x-1 cannot be a trunk, since otherwise we could set f 0 ( 1 0 ) = x + 1 (recall that, by Lemma 6, f 0 (v i ) = 0 for every stem v i , and thus f 0 (v x ) = 0), contradicting the optimality of f 0 .

Let now CT 1 = (λ x-1 , . . . , λ k ) be the caterpillar obtained from CT 0 by deleting vertices v 0 , . . . , v x-2 and their pendent neighbours (see Figure 5(a)). Note that f 0 (u) = 0 for every such deleted vertex u = 1 0 . Let f 1 denote the restriction of f 0 to V (CT 1 ). Since f 0 ( 1 0 ) = x, we get

f 1 (u) = f 0 (u) ≤ max{e CT 1 (u), d CT 0 (u, 1 0 )} ≤ e CT 1 (u)
for every vertex u ∈ V (CT 1 ), so that f 1 is an independent broadcast on CT 1 by Observation 4. Moreover, since diam(CT 1 ) = diam(CT 0 ) -x + 1, we have

cost(f 1 ) = cost(f 0 ) -x > 2(diam(CT 0 ) -1) -x = 2(diam(CT 1 ) -1) + x -2.
Since x > 1, we thus have cost(f 1 ) ≥ 2(diam(CT 1 ) -1). Therefore, since CT 0 is a minimal counterexample, we get that either f 1 is a canonical independent broadcast on CT 1 or there exists an optimal non-canonical independent broadcast f 1 on CT 1 with cost(f 1 ) ≥ cost(f 1 ) and f 1 satisfies the statement of the lemma. Suppose first that f 1 is a canonical independent broadcast. This implies cost(f 1 ) = 2(diam(CT 1 ) -1).

Hence, cost(f 0 ) = cost(f 1 ) + x = 2(diam(CT 1 ) -1) + x < 2(diam(CT 0 ) -1), which contradicts our assumption on cost(f 0 ). Therefore, there exists an optimal non-canonical independent broadcast f 1 on CT 1 with cost(f 1 ) ≥ cost(f 1 ) satisfying the statement of the lemma. If cost(f 1 ) > cost(f 1 ), the mapping f 0 given by f 0 (u) = f 1 (u) for every vertex u ∈ V (CT 1 ) and f 0 (u) = f 0 (u) for every vertex u ∈ V (CT 0 ) \ V (CT 1 ), is a non-canonical independent broadcast f 0 on CT 0 (since x ≥ 3) that contradicts the optimality of f 0 .

Hence, f 1 is optimal and thus satisfies the statement of the lemma. Let f1 be the noncanonical independent broadcast satisfying items 1 to 5 of the lemma, and let m = max f1 ( j x-1 ), 1 ≤ j ≤ λ x-1 .

We consider two cases, depending on whether v x-2 is a stem or not. Recall that v x-2 = v 0 , since x ≥ 3.

1. λ x-2 > 0.
Let f 0 be the non-canonical independent broadcast on CT 0 given by f 0

( 1 0 ) = x -1, f 0 ( 1 x-2 ) = 2, f 0 (u) = 0 for every vertex u ∈ V (CT 0 ) \ (V (CT 1 ) ∪ { 1 0 , 1 x-2 })
, and either f 0 (u) = f1 (u) for every vertex u ∈ V (CT 1 ), if m ≤ 2 (see Figure 5(b)), or f 0 ( 1x-1 ) = 2 and f 0 (u) = f1 (u) for every vertex u ∈ V (CT 1 )\{ 1

x-1 }, if m = 3 (see Figure 5(c)). We then get cost(f 0 ) = cost(f 0 ) + 1 if m ≤ 2, contradicting the optimality of f 0 , or cost(f 0 ) = cost(f 0 ) if m = 3, in which case either f 0 satisfies items 1 to 5 of the lemma or contradicts the minimality of x.

2. λ x-2 = 0.

If x = 3, then λ 1 = 0 which implies x ≥ 4, a contradiction. Hence, we have x ≥ 4, and thus v x-3 = v 0 . Let f 0 be the non-canonical independent broadcast on CT 0 given by

f 0 ( 1 0 ) = x-2, f 0 ( 1 x-3 ) = 2, f 0 (u) = 0 for every vertex u ∈ V (CT 0 )\(V (CT 1 )∪{ 1 0 , 1
x-3 }), and f 0 (u) = f1 (u) for every vertex u ∈ V (CT 1 ) (see Figure 5(d)). We then get cost(f 0 ) = cost(f 0 ), and thus either f 0 satisfies items 1 to 5 of the lemma or contradicts the minimality of x.

This concludes the proof.

We now consider the internal stems of a caterpillar. Recall that, by Lemma 6, f (v i ) = 0 for every internal stem v i of CT , 1 ≤ i ≤ k -1. The next lemma shows that if f is an optimal non-canonical independent broadcast on a caterpillar CT with no pair of adjacent trunks, with cost(f ) > 2(diam(CT ) -1), then there exists an optimal non-canonical independent broadcast f on CT such that f

* (v i ) -f (v i ) = f * (v i ) > 0 for every internal stem v i of CT , 1 ≤ i ≤ k -1.
Lemma 12 Let CT = CT (λ 0 , . . . , λ k ) be a caterpillar of length k ≥ 1, with no pair of adjacent trunks. If f is an optimal non-canonical independent broadcast on CT with cost(f ) > 2(diam(CT ) -1), then there exists an optimal non-canonical independent broadcast f on CT , thus with cost( f ) = cost(f ), such that:

1. f satisfies the five items of Lemma 11, 2. for every i,

1 ≤ i ≤ k -1, if λ i > 0, then f * (v i ) > 0.
Proof. We know by Lemma 11 that there exists an optimal non-canonical independent broadcast f on CT , with cost( f ) = cost(f ), satisfying the five items of Lemma 11. Moreover, one suppose that f has been chosen in such a way that V + f contains the largest possible number of pendent vertices.

Suppose to the contrary that there exists a vertex v i , 1 ≤ i ≤ k -1, with λ i > 0 and f * (v i ) = 0, and that for every j < i, f * (v j ) > 0 whenever λ j > 0. We consider three cases.

1. i = 1 or i = k -1.
By symmetry, it suffices to consider the case i = 1. By Lemma 11, we know that f ( j 0 ) ≤ 2 for every j, 1 ≤ j ≤ λ 0 . Therefore, no pendent neighbour of v 1 is f -dominated by a pendent neighbour of v 0 . Let y be the vertex of CT that f -dominates the pendent neighbours of discussed in Case (a) above, we necessarily have λ i-1 > 0. Moreover, we necessarily have f (y 1 ) = 3 and f (y 2 ) ≥ 2. Let now g be the mapping defined as follows. For every vertex u of CT , let

x v 0 v 1 v x-1 v k (a) The sub-caterpillar CT 1 x 0 m v 0 v x-2 v x-1 -→ x -1 2 m v 0 v x-2 v x-1 (b) λ x-2 > 0 and m ≤ 2 x 0 3 v 0 v x-2 v x-1 -→ x -1 2 2 v 0 v x-2 v x-1 (c) λ x-2 > 0 and m = 3 x 0 m v 0 v x-3 v x-2 v x-1 -→ x -2 2 m v 0 v x-3 v x-2 v x-1 (d) λ x-2 = 0
g(u) =              f (y 1 ) -1 if u = y 1 , f (y 2 ) -1 if u = y 2 , 2 if u = 1 i , 1 if u = 1 i , u is f -dominated only by y 2 and d CT (u, y 2 ) = f (y 2 ), f (u) otherwise.
Note here that no vertex at distance f (y 1 ) from y 1 can be f -dominated only by y 1 . Indeed, suppose that such a vertex, say w, exists. Clearly, w cannot be "to the left of v i " since this would imply w = v i-3 and λ i-2 = 0, but in that case w is also f -dominated by at least one of its pendent neighbours. On the other hand, w cannot be "to the right of v i " since in that case w would also be f -dominated by y 2 . Again, using similar arguments, the above-defined mapping is a non-canonical independent broadcast on CT with cost(g) ≥ cost( f ) and the contradiction arises as in Cases 1 and 2.

We thus get a contradiction in each case. This completes the proof.

Our aim now is to prove that if f is an optimal non-canonical independent broadcast on a caterpillar CT with no pair of adjacent trunks, with cost(f ) > 2(diam(CT ) -1), then cost(f ) = cost(β * ) (Lemma 16 below). We first prove that for every such broadcast f , f (v i ) ≤ 1 for every trunk v i . This easily follows from Lemma 12.

Lemma 13 Let CT = CT (λ 0 , . . . , λ k ) be a caterpillar of length k ≥ 1, with no pair of adjacent trunks. If f is an optimal non-canonical independent broadcast on CT with cost(f ) > 2(diam(CT ) -1), then there exists an optimal non-canonical independent broadcast f on CT , thus with cost( f ) = cost(f ), such that:

1. f satisfies the two items of Lemma 12, 2. for every i,

1 ≤ i ≤ k -1, if λ i = 0, then f * (v i ) ≤ 1.
Proof. We know by Lemma 12 that there exists an optimal non-canonical independent broadcast f on CT satisfying the two items of Lemma 12, so that, in particular, f * (v j ) > 0 for every stem v j , 0 ≤ j ≤ k. Since CT has no pair of adjacent trunks, and f is independent, we thus necessarily have f

* (v i ) ≤ 1 for every trunk v i , 1 ≤ i ≤ k -1.
Finally, the next lemma will show that the cost of any optimal non-canonical independent broadcast on a caterpillar CT of length k ≥ 1 with no pair of adjacent trunks cannot exceed the value β * (CT ).

We first introduce more notation. Let CT be a caterpillar of length k ≥ 1, with no pair of adjacent trunks. We denote by σ a sequence of consecutive spine vertices in CT , that is, σ = v i . . . v i+ -1 , with ≤ k+1 and 0 ≤ i ≤ k-+1. For such a given sequence σ = v i . . . v i+ -1 , we denote by t σ the number of trunks in σ, that is,

t σ = |{v j | i ≤ j ≤ i + -1 and λ j = 0}| .
If f is an independent broadcast on CT , we then denote by f * (σ) the weight of σ, that is,

f * (σ) = 0≤j≤ -1 f * (v i+j ).
Lemma 14 Let CT = CT (λ 0 , . . . , λ k ) be a caterpillar of length k ≥ 1, with no pair of adjacent trunks, and f be an optimal non-canonical independent broadcast on CT with cost(f ) > 2(diam(CT ) -1). Then there exists an optimal non-canonical independent broadcast f on CT , thus with cost( f ) = cost(f ), such that:

1. f satisfies the two items of Lemma 13. Proof. We consider the six items of the lemma.

For every

i, 0 ≤ i ≤ k, if λ i ≥ 3, then f * (v i ) ≤ λ i . 3. If v a v a+1 , 0 ≤ a < k, is an occurrence of the pattern 1 + 2 -(resp. of the pattern 2 -1 + ), then f * (v a+1 ) ≤ 2 (resp. f * (v a ) ≤ 2).
1. We know by Lemma 13 that there exists an optimal non-canonical independent broadcast f on CT satisfying the two items of Lemma 13, so that, in particular, f * (v i ) > 0 for every stem v i , 0 ≤ i ≤ k and f * (v j ) ≤ 1 for every trunk v j , 1 ≤ j ≤ k -1. We thus assume for all following items that such an optimal non-canonical independent broadcast f on CT has been chosen.

2. Suppose to the contrary that there exists some i, 0 ≤ i ≤ k, with f * (v i ) > λ i ≥ 3. This implies that v i has exactly one pendent neighbour, say 1 i without loss of generality, which is an f -broadcast vertex. Since f ( 1 i ) ≥ 4, we necessarily have a stem v with d CT (v i , v) ≤ 2 and f * (v) = 0, contradicting our assumption that f satisfies Lemma 12.

3. Let v a v a+1 , 0 ≤ a < k, be an occurrence of the pattern 1 + 2 -(the case 2 -1 + is similar, by symmetry). By Lemmas 6 and 12, we know that f * (v a ) > 0 and f (v a ) = 0. This clearly implies f * (v a+1 ) ≤ 2.

4. Let v a σv b = v i v i+1 . . . v i+2r+2 be an occurrence of the pattern 1 + 2(02) +r 1 + , for some i, 0 ≤ i ≤ k -2r -2. We thus have t σ = r. Since f satisfies Lemma 13, we have f * (v i ) > 0, f * (v i+2r+2 ) > 0, f * (v i+2j+1 ) > 0 for every j, 0 ≤ j ≤ r, and f * (v i+2j ) ≤ 1 for every j,

1 ≤ j ≤ r. This implies f * (v i+1 ) ≤ 2, f * (v i+2r+1 ) ≤ 2, and f * (v i+2j+1 ) ≤ 3 for every j, 1 ≤ j ≤ r -1. (1)
We consider three subcases, according to the number of trunks in σ that are broadcast vertices.

(a) f (v i+2j ) = 1 for every j, 1 ≤ j ≤ r.

In that case, every pendent vertex in σ is an f -broadcast vertex, with f -value 1. This gives f * (σ) = λ(σ) + τ (σ) ≤ 2(r + 1) + r = 3r + 2 = 3t σ + 2, if v a σv b is an occurrence of the pattern 1 + 2(02) +r 1 + , and

f * (σ) = λ(σ) + τ (σ) ≤ 1 + 2r + r = 3r + 1 = 3t σ + 1,
otherwise (since we have at least one stem in σ with f -value 1). (b) f (v i+2j ) = 0 for every j, 1 ≤ j ≤ r.

In that case, by (1), we get f * (σ) ≤ 2 + 3(r -1) + 2 = 3r + 1 = 3t σ + 1.

(c) Not all trunks in σ have the same f -value. Suppose that f has been chosen in such a way that the number of trunks in σ with f -value 0 is maximal. In that case, σ contains two consecutive trunks, say v i+2j 0 and v i+2j 0 +2 , 1 ≤ j 0 ≤ r -1, with f (v i+2j 0 ) = 0 and f (v i+2j 0 +2 ) = 1, without loss of generality (by symmetry). This implies f * (v i+2j 0 +1 ) = λ i+2j 0 +1 ≤ 2. We can then modify f by setting f (v i+2j 0 ) = f (v i+2j 0 +2 ) = 0, f ( 1 i+2j 0 +1 ) = 3 (and f ( 2 i+2j 0 +1 ) = 0 if λ i+2j 0 +1 = 2), contradicting our assumption on the maximality of the number of trunks with f -value 0. Therefore, this case cannot occur and we are done.

5. The proof uses the same ideas as the proof of the previous case. Let σ = v i v i+1 . . . v i+2r+2 be an occurrence of the pattern 02 -(02 -) * r 0, for some i, 1 ≤ i ≤ k -2r -3. We thus have t σ = r + 2. Since f satisfies Lemma 13, we have

0 < f * (v i+2j+1 ) ≤ 3 for every j, 0 ≤ j ≤ r, (2)
and f * (v i+2j ) ≤ 1 for every j, 0 ≤ j ≤ r + 1.

We consider three subcases, according to the number of trunks in σ that are broadcast vertices.

(a) f (v i+2j ) = 1 for every j, 0 ≤ j ≤ r + 1.

In that case, every pendent vertex in σ is an f -broadcast vertex, with f -value 1. This gives f *

(σ) = λ(σ) + τ (σ) ≤ 2(r + 1) + r + 2 = 3r + 4 = 3t σ -2,
if σ is an occurrence of the pattern 02(02) * r 0, and

f * (σ) = λ(σ) + τ (σ) ≤ 1 + 2r + r + 2 = 3r + 3 = 3t σ -3,
otherwise (since we have at least one stem in σ with f -value 1). (b) f (v i+2j ) = 0 for every j, 0 ≤ j ≤ r + 1.

In that case, by ( 2) and (3), we get f * (σ) ≤ 3(r + 1) = 3r + 3 = 3t σ -3.

(c) Not all trunks in σ have the same f -value. Suppose that f has been chosen in such a way that the number of trunks in σ with f -value 0 is maximal. In that case, σ contains two consecutive trunks, say v i+2j 0 and v i+2j 0 +2 , 0 ≤ j 0 ≤ r, with f (v i+2j 0 ) = 0 and f (v i+2j 0 +2 ) = 1, without loss of generality (by symmetry). This implies f * (v i+2j 0 +1 ) = λ i+2j 0 +1 ≤ 2. We can then modify f by setting f

(v i+2j 0 ) = f (v i+2j 0 +2 ) = 0, f ( 1 i+2j 0 +1 ) = 3 (and f ( 2 i+2j 0 +1 ) = 0 if λ i+2j 0 +1 = 2
), contradicting our assumption on the maximality of the number of trunks with f -value 0. Therefore, this case cannot occur and we are done.

6. Let v 0 . . . v 2r+1 be an occurrence of the pattern [2 -(02 -) * r 0 (the case 02 -(02 -) * r ] is similar, by symmetry). We first prove that for every i, 0 ≤ i ≤ r, f * (v 2i ) + f * (v 2i+1 ) ≤ 3. By Lemma 13, we know that f (v 2i+1 ) ≤ 1. If f (v 2i+1 ) = 1, we then have f ( j 2i ) ≤ 1 for every pendent neighbour j 2i of v 2i , and thus f * (v 2i ) ≤ λ 2i ≤ 2. On the other hand, if f (v 2i+1 ) = 0, we have f * (v 2i ) ≤ 3 (which implies f ( j 2i ) = 3 for a pendent neighbour j 2i of v 2i ) since otherwise we would have f * (v 2i+2 ) = 0, contradicting Lemma 12. In both cases, we thus get the desired inequality. Since σ contains exactly r + 1 = t σ distinct pairs of vertices of the form (v 2i , v 2i+1 ), we get

f * (σ) = i=r i=0 f * (v 2i ) + f * (v 2i+1 ) ≤ 3(r + 1) = 3t σ .
By Lemma 14, we know that there exists an optimal non-canonical independent broadcast f with cost( f ) = cost(f ) which satisfies all items of Lemma 14. We have proved that the non-canonical independent broadcast f 4 constructed in the proof of Lemma 10 also satisfies all items of Lemma 14. Thanks to Lemma 15, we thus have cost(f ) = cost( f ) ≤ cost(f 4 ) = β * (CT ), which completes the proof.

We are now able to state our main result, which determines the broadcast independent number of any caterpillar with no pair of adjacent trunks.

Theorem 17 Let CT = CT (λ 0 , . . . , λ k ) be a caterpillar of length k ≥ 1, with no pair of adjacent trunks. The broadcast independence number of CT is then given by:

β b (CT ) = max 2(diam(CT ) -1), β * (CT ) .
Proof. We know by Observation 1 that β b (CT ) ≥ 2(diam(CT ) -1) and we already observed that the canonical independent broadcast f c on CT satisfies cost(f c ) = 2(diam(CT ) -1). According to Lemma 10, it is thus enough to prove that for any optimal non-canonical independent broadcast f on CT with cost(f ) > 2(diam(CT ) -1), cost(f ) ≤ β * (CT ), which directly follows from Lemma 16.

In several cases, the value of β * (CT ) has a simple expression. Consider for instance a caterpillar CT , of length k ≥ 1, having no trunk. We then have β * (CT ) = λ(CT ) + n 1 (CT ), where n 1 stands for the number of spine vertices having exactly one pendent vertex. Since λ(CT ) ≥ n 1 (CT ) + 2(k + 1 -n 1 (CT )) = 2k + 2 -n 1 (CT ) (spine vertices have either one or at least two pendent neighbours), we get β * (CT ) ≥ 2k + 2, with equality if and only if CT contains no stem with at least three pendent neighbours. Since 2(diam(CT ) -1) = 2k + 2, we get the following corollary of Theorem 17.

Corollary 18 Let CT be a caterpillar of length k ≥ 1 having no trunk. We then have β b (CT ) = 2k + 2 = 2(diam(CT ) -1) if CT has no stem with at least three pendent neighbours, and β b (CT ) = λ(CT ) + n 1 (CT ) otherwise.

Moreover, thanks to Observation 4, we can also give the broadcast independent number of caterpillars having adjacent trunks but no stem with at least three pendent neighbours.

Corollary 19 Let CT be a caterpillar of length k ≥ 1. If CT has no stem with at least three pendent neighbours, then β b (CT ) = 2k + 2 = 2(diam(CT ) -1).

Finally, note that if every stem in a caterpillar CT of length k ≥ 1 with no pair of adjacent trunks has at least three pendent neighbours, then no pattern involved in the definition of β * (CT ) can appear in CT . In that case, since τ (CT ) ≤

Concluding remarks

In this paper, we studied independent broadcasts of caterpillars and gave an explicit formula for the broadcast independence number of caterpillars having no pair of adjacent trunks. This result concerns a quite restricted subclass of the class of trees, but the broadcast independence number is certainly a difficult parameter to determine for trees, and probably even for caterpillars. It should be noticed here that the computational complexity of the decision problem associated with the broadcast independence number is not known yet, even for trees, although this question was already posed in [START_REF] Dunbar | Broadcasts in graphs[END_REF] and [START_REF] Hedetniemi | Unsolved Algorithmic Problems on Trees[END_REF]. (The only complexity result about a broadcast parameter, among those introduced in [START_REF] Dunbar | Broadcasts in graphs[END_REF], is due to Heggernes and Lokshtanov [START_REF] Heggernes | Optimal broadcast domination in polynomial time[END_REF], who proved that computing the broadcast domination number γ b (G) of any graph G can be done in polynomial time.)

Finally, we consider that the following questions are of particular interest.

1. Can we determine the broadcast independence number of caterpillars? (We should notice here that for caterpillars with adjacent trunks, Lemmas 6 and 7 still hold, while Lemma 12 does not. This explains why we think that this might be a not so easy question.) where k is the maximum size of a set of pairwise antipodal vertices in T ?

Figure 1 :

 1 Figure 1: The caterpillar CT (1, 0, 2, 1, 1, 2, 1, 0, 3)

Figure 2 :

 2 Figure 2: Sample patterns involved in the definition of β * (CT )

1 Figure 4 :

 14 Figure 4: Proof of Lemma 10: from f 3 to f 4

Figure 5 :

 5 Figure 5: Configurations for the proof of Lemma 11

4 . 5 . 6 .

 456 If v a σv b is an occurrence of the pattern 1 + 2 -(02 -) +r 1 + , then f * (σ) ≤ 3t σ + 2 if v a σv b is an occurrence of the pattern 1 + 2(02) +r 1 + , and f * (σ) ≤ 3t σ + 1 otherwise. If σ is an occurrence of the pattern 02 -(02 -) * r 0, then f * (σ) ≤ 3t σ -2 if v a σv b isan occurrence of the pattern 02(02) * r 0, and f * (σ) ≤ 3t σ -3 otherwise. If σ is an occurrence of the pattern [2 -(02 -) * r 0 or of the pattern 02 -(02 -) * r ], then f * (σ) ≤ 3t σ .

k 2

 2 and λ(CT ) ≥ 3 k 2 + 1 , we getβ * (CT ) = λ(CT ) + τ (CT ) > 2k + 2 = 2(diam(CT ) -1).Therefore, we have:Corollary 20 Let CT be a caterpillar of length k ≥ 1, with no pair of adjacent trunks. If all stems in CT have at least three pendent neighbours, then β b (CT ) = λ(CT ) + τ (CT ).

2 . 4 .

 24 Can we determine the broadcast independence number of other subclasses of the class of trees? In particular, what about k-ary trees? 3. Can we characterize the set of caterpillars CT for which β b (CT ) = 2(diam(CT ) -1)? (Partial answers are given by Corollaries 18 and 19.) More generally, can we characterize the set of trees T for which β b (T ) = k(diam(T ) -1),

Faculty of Mathematics, Laboratory L'IFORCE, University of Sciences and Technology Houari Boumediene (USTHB), B.P. 32 El-Alia, Bab-Ezzouar, 16111 Algiers, Algeria.

Univ. Bordeaux, Bordeaux INP, CNRS, LaBRI, UMR 5800, F-33400 Talence, France.

v 1 (note that y is necessarily unique), and g be the mapping defined as follows. For every vertex u of CT , let

, u is f -dominated only by y and d CT (u, y) = f (y), f (u) otherwise.

We claim that the mapping g is a non-canonical independent broadcast on CT with cost(g) ≥ cost( f ). Indeed, all vertices x with d CT (x, y) < f (y) that were f -dominated by y are still g-dominated by y, and all vertices x = 1 1 with d CT (x , y) = f (y) that were f -dominated only by y are now g-broadcast vertices with g(x ) = 1 (note that since every such x was f -dominated only by y, we have g(z) = f (z) = 0 for every neighbour z of x ). Now, if there exists a vertex z which is f -dominated only by y, we get cost(g) ≥ cost( f )+1, contradicting the optimality of f . If no such vertex exists, we get cost(g) = cost( f ) and V + g contains more pendent vertices than V + f , contrary to our assumption. 2. i = 2 and λ 1 = 0, or i = k -2 and λ k-1 = 0.

By symmetry, it suffices to consider the case i = 2. By Lemma 11, we know that f ( j 0 ) ≤ 3 for every j, 1 ≤ j ≤ λ 0 . Therefore, no pendent neighbour of v 2 is f -dominated by a pendent neighbour of v 0 . Let y be the (unique) vertex of CT that f -dominates the pendent neighbours of v 2 (note that we necessarily have f (y) ≥ 2). If y = v 3 and f (v 3 ) = 3 (since f * (v 0 ) > 0, we necessarily have f (v 3 ) ≤ 3), we define the mapping g as follows. For every vertex u of CT , let

Otherwise (including the case y = v 3 and f (v 3 ) = 2), the mapping g is defined by

for every vertex u of CT . In both cases, the mapping g is again a non-canonical independent broadcast on CT with cost(g) ≥ cost( f ). Indeed, all vertices x with d CT (x, y) < f (y) -1 that were f -dominated by y are g-dominated by 2 1 (if y = v 3 ) or still g-dominated by y (if y = v 3 ), and all vertices x = 1 2 with f (y) -1 ≤ d CT (x , y) ≤ f (y) that were f -dominated only by y are now either g-broadcast vertices (if d CT (x , y) = f (y) -1) or g-dominated by a vertex x with d CT (x , y) = f (y) -1 and g(x ) = 1. We then get a contradiction as in Case 1.

3. 2 < i < k -2, or i = 2 and λ 1 > 0, or i = k -2 and λ k-1 > 0.

In this case, we have f * (v j ) > 0 for every vertex v j with j < i and λ j > 0. Note also that we have at least two such vertices v j with j < i and λ j > 0. By symmetry, it suffices to consider the cases 2 < i < k -2, and i = 2 (with λ 1 > 0). We consider three subcases.

(a) Suppose first that the pendent neighbours of v i are f -dominated only by a vertex y = v j 0 or y = k 0 j 0 with j 0 < i and 1 ≤ k 0 ≤ λ j 0 . Observe that the pendent neighbours of v i cannot be f -dominated by two such vertices, say y and y , since we would have d CT (y, y ) < d CT (y, 1 i ) so that f would not be independent. Since f * (v j ) > 0 for every j < i such that λ j > 0, we necessarily have, by Lemma 6, either y is a pendent neighbour of v i-1 , if λ i-1 > 1, or a pendent neighbour of v i-2 , if λ i-1 = 0. Moreover, since f * (v j ) > 0 for every j < i such that λ j > 0, and since we have at least two such vertices, we necessarily have f (y) ≤ 3. This implies in particular λ i-1 > 0, as otherwise we would have f (y) ≤ 3 and d CT (y, 1 i ) = 4, contradicting the fact that y f -dominates 1 i , and thus y is a pendent neighbour of v i-1 . Let now g be the mapping defined as follows. For every vertex u of CT , let

Again, the mapping g is a non-canonical independent broadcast on CT with cost(g) ≥ cost( f ). Indeed, all vertices x with d CT (x, y) < f (y) that were f -dominated by y are still g-dominated either by y, and all vertices x = 1 i with d CT (x , y) = f (y) that were f -dominated only by y are now g-broadcast vertices.

We then get a contradiction as in Cases 1 and 2. (b) Suppose now that the pendent neighbours of v i are f -dominated only by a vertex y = v j 0 (with λ j 0 = 0) or y = k 0 j 0 (1 ≤ k 0 ≤ λ j 0 ), with j 0 > i. Observe that, using the same argument as in Case (a), such a vertex y must be unique. Moreover, we necessarily have f (y) ≥ 2. If λ i-1 = 0, we consider two cases, as we did in Case 2. If y = v i+1 and f (v i+1 ) = 3, we define the mapping g by

for every vertex u of CT . Otherwise, the mapping g is defined by

for every vertex u of CT . Otherwise, that is, λ i-1 > 0, we define the mapping g as follows. For every vertex u of CT , let

otherwise.

Again, using similar arguments, in each case the above-defined mapping is a noncanonical independent broadcast on CT with cost(g) ≥ cost( f ) and the contradiction arises as in Cases 1 and 2. (c) Suppose finally that the pendent neighbours of v i are f -dominated both by a vertex y 1 = v j 1 or y 1 = k 1 j 1 with j 1 < i and 1 ≤ k 1 ≤ λ j 1 , and by a vertex

with j 2 > i and 1 ≤ k 2 ≤ λ j 2 (again, both y 1 and y 2 must be unique). In that case, as

This completes the proof.

The following lemma states that Lemma 14 covers all possible caterpillars that admit a non-canonical independent broadcast with sufficiently large cost.

Lemma 15 If CT = CT (λ 0 , . . . , λ k ) is a caterpillar of length k ≥ 1, with no pair of adjacent trunks, such that there exists an optimal non-canonical independent broadcast f on CT with cost(f ) > 2(diam(CT ) -1), then Lemma 14 gives an upper bound on cost(f ).

Proof. Let CT = CT (λ 0 , . . . , λ k ) be a caterpillar of length k ≥ 1, with no pair of adjacent trunks, f be an optimal non-canonical independent broadcast on CT with cost(f ) > 2(diam(CT ) -1), and v i , 0 ≤ i ≤ k, a spine vertex of CT .

If λ i ≥ 3, then f * (v i ) = λ i by item 5 of Lemma 11, and thus by item 1 of Lemma 14.

If λ i = 0, then f * (v i ) ≤ 1 by item 2 of Lemma 13, and thus by item 1 of Lemma 14. Suppose now that 1 ≤ λ i ≤ 2. If i = 0 or i = k, then f * (v i ) ≤ 3 by items 1 to 4 of Lemma 11, and thus by item 1 of Lemma 14. We assume now that 1

The remaining case is thus 1 ≤ i ≤ k -1, λ i-1 = 0 and λ i+1 = 0. We consider the set of all occurrences of a pattern, in which 0's and 2 -'s alternate, that contain vertices v i-1 , v i and v i+1 . Let σ = v a v a+1 . . . v b , 0 ≤ a ≤ i -1 < i + 1 ≤ b ≤ k be such an occurrence with maximal length. Note here that we necessarily have v a = v i and v b = v i . We consider three cases.

By the maximality of σ, we necessarily have λ a-1 ≥ 3 and λ b+1 ≥ 3. Therefore, the value of f * (σ) is bounded by item 5 of Lemma 14.

. This contradicts our assumption on the value of cost(f ), and thus this case cannot occur.

Therefore, in all cases, either f * (v i ) or f * (σ) for an occurrence σ of a pattern containing v i is bounded by some item of Lemma 14. This concludes the proof.

Using Lemmas 14 and 15, we can now prove that no optimal non-canonical independent broadcast f on CT with cost(f ) > 2(diam(CT ) -1) and cost(f ) > β * (CT ) exists.

Lemma 16

Let CT = CT (λ 0 , . . . , λ k ) be a caterpillar of length k ≥ 1, with no pair of adjacent trunks, and f be an optimal non-canonical independent broadcast on CT with cost(f ) > 2(diam(CT ) -1). We then have cost(f ) ≤ β * (CT ).

Proof. Let us denote by f 4 the non-canonical independent broadcast on CT constructed in the proof of Lemma 10, thus with cost(f 4 ) = β * (CT ). By considering the four steps involved in the construction of f 4 , it clearly appears that f 4 satisfies the five items of Lemma 11, item 2 of Lemma 12 and item 2 of Lemma 13. Therefore, f 4 satisfies item 1 of Lemma 14. Moreover, if v i is a trunk that does not appear in any pattern considered in Lemma 14, then f 4 (v i ) = 1. Indeed, the f 4 -value of v i is set to 1 in step 1 of Lemma 10 and is not modified in steps 2 to 4.

We now prove that f 4 satisfies the five last items of Lemma 14 and that, in each case, the upper bound is attained. We will refer to steps 1 to 4 of the proof of Lemma 10 and to the corresponding intermediate independent broadcasts f 1 to f 3 . Recall first that in step 1, every trunk and every pendent vertex is assigned the value 1.

1. Item 2 of Lemma 14.

If v i is a stem with λ i ≥ 3, the value of its pendent neighbours is not modified in steps 2 to 4. Therefore, we get

Let v a v a+1 , 0 ≤ a < k, be an occurrence of the pattern 1 + 2 -(the case 2 -1 + is similar, by symmetry). Note here that if v a+1 is the leftmost vertex of an occurrence of the pattern 1 + 2(02) +r 1 + , then the value of its pendent neighbours is not modified in step 3.

If λ a+1 = 1, then, in step 2, the value of 1 a+1 is set to 2 and not modified in step 4. If λ a+1 = 2, then the value of the pendent neighbours of v a+1 is not modified in steps 2 and 4. Therefore, f * 4 (v a+1 ) = 2 in both cases. 3. Item 4 of Lemma 14.

Let v a σv b = v i v i+1 . . . v i+2r+2 be an occurrence of the pattern 1 + 2 -(02 -) +r 1 + , for some i, 0 ≤ i ≤ k -2r -2. In that case, we have t σ = r. If v a σv b is an occurrence of the pattern 1 + 2(02) +r 1 + , the value of the vertices of σ are not modified in steps 2 to 4. Therefore, we have f * 4 (σ) = f * 1 (σ) = 2(r+1)+r = 3r+2 = 3t σ +2. Suppose now that σ contains at least one stem having only one pendent neighbour. In step 3, the value of 1 i+1 is set to 2 if λ i+1 = 1, the value of 1 i+2r+1 is set to 2 if λ i+2r+1 = 1, the value of 1 i+2j+1 , 1 ≤ j ≤ r -1, is set to 3 (and the value of 2 i+2j+1 is set to 0 if λ i+2j+1 = 2), and the value of every trunk is set to 0. We thus get

4. Item 5 of Lemma 14.

Let σ = v i v i+1 . . . v i+2r+2 be an occurrence of the pattern 02 -(02 -) * r 0, for some i, 1 ≤ i ≤ k -2r -3. In that case, we have t σ = r + 2. If σ is an occurrence of the pattern 02(02) * r 0, the value of the vertices of σ are not modified in steps 2 to 4. Therefore, we have f * 4 (σ) = f * 1 (σ) = 2(r + 1) + r + 2 = 3r + 4 = 3t σ -2. Suppose now that σ contains at least one stem having only one pendent neighbour. In step 3, the value of 1 i+2j+1 , 0 ≤ j ≤ r, is set to 3 (and the value of 2 i+2j+1 is set to 0 if λ i+2j+1 = 2), and the value of every trunk is set to 0. We thus get f * 4 (σ) = f * 3 (σ) = 3(r + 1) = 3r + 3 = 3t σ -3.

5. Item 6 of Lemma 14. Let v 0 . . . v 2r+1 be an occurrence of the pattern [2 -(02 -) * r 0 (the case 02 -(02 -) * r ] is similar, by symmetry). In that case, we have t σ = r + 1.

In step 3, the value of 1 2j , 0 ≤ j ≤ r, is set to 3 (and the value of 2 2j is set to 0 if λ 2j = 2), and the value of every trunk is set to 0. We thus get f * 4 (σ) = f * 3 (σ) = 3(r + 1) = 3r + 3 = 3t σ .