# Mathematical certification of motion planning on uncertain terrain with
limited perception: a case study

Nikolaos Skouloudis and Alexandre Megretski

###### Abstract.

We design a controller for an agent whose mission is to reach a stationary
target while avoiding a family of obstacles which are not known a-priori. The
agent moves in the two dimensional plane with non-trivial double integrator
dynamics and receives only local information from its surroundings. Under mild
assumptions on the family of obstacles (smoothness, sufficient distance from
each other, bounded curvature, etc), we prove that our control algorithm
yields guaranteed obstacle avoidance and convergence to the target.

##  1 Problem Setup

This article presents a case study of an agent moving in a two dimensional
plane filled with multiple stationary obstacles (not known a-priori) with the
aim of reaching a known fixed target while avoiding collisions with the
obstacles. The target is located at the origin and we consider a family of
non-intersecting sets (obstacles) in the two dimensional plane. The boundary
of each obstacle is assumed to be a smooth curve of bounded curvature, without
self-intersections. Equivalently, the boundary of the i-th obstacle is the set
$\left\\{f_{i}(s):s\in[0,1]\right\\}$, where $f_{i}:[0,1]\to\mathbb{R}^{2}$
and satisfies

$\displaystyle\left\lvert\dot{f}_{i}\right\rvert$ $\displaystyle=$
$\displaystyle v_{0},$ $\displaystyle\ddot{f}_{i}$ $\displaystyle=$
$\displaystyle\frac{v_{0}w_{i}}{r_{0}}S\dot{f}_{i}.$ (1)

Here $v_{0}$ and $r_{0}$ are the fixed growth-rate and the minimum radius of
curvature of any obstacle boundary curve, $\lvert w_{i}\rvert\leq 1$ is
relative curvature of the $i$th boundary curve and $S$ is a rotation matrix by
$\frac{\pi}{2}$. We also assume that the obstacles are sufficiently far away
from each other and that the boundary curve of each obstacle allows sharp
turning (see §A.2), namely,

######  Assumption 1.

  1. (i)

$d_{H}\left(f_{i}\left([0,1]\right),f_{j}\left([0,1]\right)\right)\geq\frac{8}{5}r_{0}$
for all $i,j$,

  2. (ii)

For every $p\in f_{i}\left([0,1]\right)$ we have $B(p+r_{0}n_{p},r_{0})\bigcap
f_{i}\left([0,1]\right)=\emptyset$,

where $d_{H}\left(X,Y\right)$ denotes the Hausdorff distance between
$X\subset\mathbb{R}^{2}$ and $Y\subset\mathbb{R}^{2}$, $B(x,r)$ is the open
ball centred at $x\in\mathbb{R}^{2}$ with radius $r>0$ and $n_{p}$ is the
outward normal unit vector to the obstacle boundary curve at
$p\in\mathbb{R}^{2}$. We stress that condition (ii) can be dropped when the
obstacles are convex.
On the other had, we assume that the agent has double integrator dynamics,

$\begin{bmatrix}\dot{x}\\\ \dot{v}\end{bmatrix}\in\begin{bmatrix}v\\\
\frac{a_{0}u}{v_{0}}Sv\end{bmatrix},$ (2)

where $(x,v)\in\mathbb{R}^{4}$ denotes the agent’s position and velocity,
$a_{0}=\frac{v_{0}^{2}}{r_{0}}$ is the nominal acceleration of the agent and
$u\in\mathbb{R}$ is the control action. We also define $r_{a}$ to be the
minimum turning radius of the agent and consider bounded actuation $\lvert
u\rvert\leq M$ where $M=\frac{r_{0}}{r_{a}}:=5$ (see §A.1 for a justification
in selecting the latter value). Note that the agent moves at a constant
velocity $\lvert v\rvert=v_{0}$ which concurs with the growth-rate of the
obstacle boundary curve, however this does not pose significant restrictions
in the family of obstacles that are considered as it is not an intrinsic curve
property (reparametrization). With no loss in generality, we allow the initial
velocity, $v(0)$, to point in the direction of the origin, i.e.
$v(0)=-v_{0}\frac{x(0)}{\left\lvert x(0)\right\rvert}$. We allow discontinuous
and causal control with multiple but finite mode switches, thus existence and
well posedness of solutions to (2) should be verified (see §2.1).
Moreover, we assume that the agent receives information about its surroundings
via a depth sensor, which is modelled as a vector of length
$d_{m}=\frac{4}{5}r_{0}$ starting from the agent’s location and oriented at an
angle $\phi$ from the agent’s velocity vector. In proximity of an obstacle,
the sensor provides: (i) $d$, the distance (henceforth depth measurement)
between the agent’s location and the point on the obstacle’s boundary curve
intersecting the depth sensor vector (henceforth impact point) and (ii)
$\psi$, the angular separation between $\dot{f}$ at the impact point and the
depth sensor vector. If the depth measurement is not less than $d_{m}$, the
agent does not detect the presence of obstacles and the sensor returns only
the depth measurement, i.e. $d=d_{m}$. Control of the sensor orientation is
modelled in continuous time,

$\dot{\phi}=u_{s},$ (3)

where the sensor is initially parallel to the velocity, i.e. $\phi(0)=0$, and
the sensor actuation is limited $\left\lvert
u_{s}\right\rvert\leq\gamma=\frac{1}{10}\frac{a_{0}}{v_{0}}$.
The goal of this case case study is to design for $u$ and $u_{s}$ and
theoretically guarantee that the agent reaches the origin while avoiding
collisions with obstacles.

##  2 Control Algorithm

In this section we describe the control algorithm that will certify
convergence to the origin of the agent. The idea is to track the line passing
through the origin with gradient $v(0)$ (henceforth termed the attraction
line) in absence of obstacles in the agent’s local horizon. Once an obstacle
is detected, the agent should follow the obstacle at a sufficiently close
distance so that no other obstacles appear in the agent’s horizon (this phase
will be called the tracking). The obstacle should stop following the obstacle
once it is in in proximity of the attraction line. Note that, once an obstacle
is detected the agent needs to reorient its velocity and sensor direction
(recall that in absence of obstacles the sensor is parallel to the velocity)
in order to be able to handle tracking, i.e. during tracking we expect the
velocity to be almost parallel to the tangent of the obstacle curve and the
sensor to be orthogonal to the velocity. The latter phase of reorientation
will be termed locking. Similarly, the agent needs to adjust its orientation
once tracking ends in favour of following the attraction line. This phase is
called unlocking. We will thus dedicate the reminder of this article in
finding an appropriate control law for tracking, locking and unlocking. Note
that a controller has to also be designed in order to track the attraction
line, but as is described in §A.2, we can use the control designed for the
immediate locking section.

###  2.1 Controller Modes

The controller has four modes corresponding to (i) following the attraction
line, (ii) locking, (iii) tracking and (iv) unlocking.
Mode (i) defines the controller with which the algorithm starts and is the
mode used in absence of obstacles in the local horizon of the agent (i.e. when
$d=d_{m}$). Note that since no obstacles are present, $u_{s}=0$. This mode
ensures that the agent follows the attraction line, by ensuring that (i) the
agent’s location, $x$, is in a tubular neighbourhood of radius
$\Delta_{m}r_{0}=0.03r_{0}$ of the attraction line and (ii) the angular
separation between $v$ and $v(0)$ (denoted by $\delta$) is not greater than
$\delta_{m}=0.103$. The controller for this mode is derived in §A.2 and is
given by,

$u_{att}\left(x,v,x(0),v(0)\right)=-\delta-163\Delta,$ (4)

where $\Delta=\pi_{att}\left(x\right)$ and
$\pi_{att}:\mathbb{R}^{2}\rightarrow\mathbb{R}_{\geq 0}$ represents distance
between the agent’s position and its projection onto the attraction line. Mode
switching occurs if either (a) $x\in B\left(0,\epsilon\right)$ where
$\epsilon\leq d_{m}$ at which point the algorithm stops or (b) $d<d_{m}$ at
which point Mode (ii) begins and a timer, with values $\hat{t}$, begins.
For locking, the depth sensor detects the initial impact point on the obstacle
(the first point at which $d<d_{m}$) and keeps tracking it at all times (see
§A.2 for a mathematical expression for $u_{s}$). Using the latter point, it is
possible to obtain nominal trajectories, $(\overline{x},\overline{v})$, which
end when $\overline{v}$ is aligned with $\dot{f}$ at the impact point and the
distance between $\overline{x}$ and the impact point is $d_{0}=0.06r_{0}$ (the
time of completion for the nominal trajectory is given by $\hat{t}_{1}$). The
proposed nominal trajectory involves three segments (and thus two switching
submodes): (a) an initial circular segment (with radius $1.151r_{a}$), (b) an
intermediate linear segment and (c) a final circular segment (with radius
$1.151r_{a}$). A controller is designed for each submode which ensures that
the agent tracks the nominal trajectory (analogous to mode (i)). For the
initial and final submodes, the controller is given by,

$u_{cir}\left(x,v,\overline{x},\overline{v},\hat{t}\right)=u=-M\text{sgn}\left(\delta-3.4\Delta\right),$

where $\delta$ and $\Delta$ have analogous meanings to the ones for mode (i)
(e.g. $\Delta$ is the distance between the agent’s location and its projection
on the nominal curve, etc). Similarly, since the intermediate stage is linear
we define $u_{int}$ as in (4) with obvious modifications (see §A.2 for
details). Note that for each submode, trajectories are guaranteed to exits
either by the continuity of the controller (intermediate stage) or by
convexification[1] (initial and final stages) and hence since there are a
finite number of switches (two) between the submodes, a trajectory exists for
the entire locking stage. We will refer to $u_{loc}$ as the collection of the
three submodes that produces the aforementioned trajectory. Switching from
mode (ii) to mode (iii) occurs when $\hat{t}\geq\hat{t}_{1}$, the distance
between $x$ and the impact point is contained in
$\left[\frac{d_{0}}{2},\frac{3d_{0}}{2}\right]$ and the angular separation
between $v$ and $\dot{f}$ at the impact point is bounded by $\psi_{m}=0.58$.
At the time of the switch the timer is reset.
We define $\hat{t}_{2}$ to be the time taken to reach the attraction line by a
particle travelling in uniform circular motion with acceleration $a_{0}$ and
starting position and velocity equal to agent’s when the mode switching
occurred. In mode (iii), the controller is given by,

$u_{tr}\left(x,v,d,\psi,\hat{t}\right)=-M\text{sgn}\left[0.02\left(d-d_{0}\right)-0.12\left(\psi-1.71\right)\right]$

and guarantees that $d\in\left[\frac{d_{0}}{2},\frac{3d_{0}}{2}\right]$ and
$\lvert\psi\rvert\leq\psi_{m}$ at all times. Throughout tracking, $u_{s}=0$.
Switching from mode (iii) to mode (iv) occurs when $\hat{t}\geq\hat{t}_{2}$
and $x$ is the neighbourhood of radius $\Delta_{m}r_{0}$ of the attraction
line. Mode switching resets the timer for $\hat{t}$.
Mode (iv) is analogous to mode (ii) in the sense that the sensor is oriented
towards a fixed impact point (the one detected when mode switching from (iii)
to (iv) occurs). Similarly, nominal trajectories involving only two circular
segments can be used to drive the state of the agent to have velocity parallel
to $v(0)$ and position on the attraction line and $\hat{t}_{3}$ is defined
analogously. Note that at this point, the sensor will not be parallel to the
velocity so it has to be rotated using maximal sensor actuation until $\phi=0$
(details in §A.3). The circular submodes are defined just as in mode (ii) and
$u_{unloc}$ is used to denote the collection of the two circlar submodes and
submode of sensor reorientation. Mode (iv) switches to mode (i) when
$\hat{t}\geq\hat{t}_{3}$, the angular separation between $v$ and $v(0)$ is
bounded by $\delta_{m}$ and $x$ is the tubular neighbourhood of radius
$\Delta_{m}r_{0}$ of the attraction line. A summary of how mode switching
occurs is presented in Algorithm 1.
It is important to emphasize that the controller modes designed guarantee
sensitivity to some level of sensor noise (see §A.1 for example). However, no
theoretical guarantees are given on the magnitude of the noise, i.e. for
tracking there exists $\delta_{tr}$ such that if sensor noise is bounded by
$\delta_{tr}$, tracking is guaranteed to be possible. $\delta_{loc}$ and
$\delta_{unloc}$ are similarly defined. Moreover, we stress that given the
assumptions on the family of obstacles and the agent dynamics, it is possible
to infer that each mode is guaranteed to occur for a finite non-infinitesimal
amount of time after every mode switch. This implies that convergence to the
target will only require a finite amount of mode switches and since each mode
guarantees the existence of a trajectory associated with it, wellposedness of
(2) follows.

##  3 Main Result

We now state the main theorem of this article that rigorously proves that the
aforementioned control algorithm will guarantee, that if the agent starts
sufficiently far from an obstacle, it will reach a neighbourhood of the target
while avoiding collisions with obstacles at all times.

######  Theorem 1.

Assume there are no obstacles in $B(0,d_{m})$ and $B(x(0),d_{m})$. Then for
every $\epsilon>0$, there exists $\delta>0$ and finite time $T>0$ such that
for sensor noise bounded by $\delta$ and for any $x(0)$, we have $x(T)\in
B(0,\epsilon)$.

Proving Theorem 1 is straightforward since tracking, locking and unlocking
have already been certified. Consider the case of zero noise, then, there
exists a continuous trajectory that always ends on the attraction line after
unlocking and hence there exists a finite time $T$ such that $x(T)=0$.
Similarly, we set
$\delta=\min\left(\delta_{tr},\delta_{loc},\delta_{unloc}\right)$ and we
introduce noise bounded by $\delta$ in sensor measurements. By the continuity
of the trajectory, noise in sensor measurements implies that after unlocking
the agent’s location and velocity are in a neighbourhood of the attraction
line and $v(0)$ respectively, whence proving the desired result.
Note that it is important to emphasize that Theorem 1 proves robustness to
some non-zero level of noise, however we do not actually prove a global upper
bound for the noise.

##  4 Numerical Examples

We conclude our case study by providing some simulations of the agent moving
in an unknown environment. We keep the sensor noise at $\frac{d_{0}}{8}$ for
depth measurements and $1.5\degree$ for angular measurements and we stress
that the latter are not theoretically guaranteed but rather the practical
(obtained from numerical experiments) maximal noise levels that the proposed
algorithm can handle. Figure 1 (a) depicts the agent moving past an unknown of
family of obstacles and converging to the target. On the other hand, in Figure
1 (b) we portray the importance of condition (ii) in Assumption 1 for the
locking phase by showing fatal collision in absence of the latter condition.
Finally, in Figure 1 (c)-(d) we compare tracking for bounded obstacle
curvature (Figure 1 (c)) versus the inability to track obstacles with large
curvature (Figure 1 (d)).

(a)

(b)

(c)

(d)

Figure 1: (a) Convergence to target, (b) dropping condition (ii) from
Assumption 1. Importance of curvature assumption for tracking: (c) tracking
with $w(s)=\frac{2}{\pi}\arctan\left(s\right)$ vs (d) tracking with $w(s)={\rm
e}^{s}$. Obstacles portrayed in red, starting position of agent is denoted by
$\blacksquare$ and the target is denoted by $\bullet$.

## References

  * Filippov [1988] A. F. Filippov.  _Differential equations with discontinuous righthand sides_ , volume 18 of _Mathematics and its Applications (Soviet Series)_.  Kluwer Academic Publishers Group, Dordrecht, 1988.  ISBN 90-277-2699-X.

##  Appendix A Derivations

###  A.1 Tracking

We derive the control law for tracking a single obstacle and hence we drop the
obstacle subscript $i$. Let $T$ denote the rotation matrix by $\phi$ where
$\phi$ is the angle between the velocity and depth sensor and define the angle
between the depth sensor and the tangent to the obstacle curve as $\psi$, then

$v_{0}^{2}\cos(\phi-\psi)=v^{\prime}\dot{f}.$ (5)

The dynamics of the agent, sensor depth, $d$, and obstacle boundary are
related by,

$x+d\frac{Tv}{v_{0}}=f,$ (6)

so that by differentiating (6) and combining with (5), we can obtain dynamic
equations for $d$ and $\psi$. Henceforth, in this section, we work with non-
dimensional depth $d\rightarrow\frac{d}{r_{0}}$ and time,
$t\rightarrow\frac{a_{0}}{v_{0}}t$ and obtain,

$\displaystyle\dot{d}$ $\displaystyle=$
$\displaystyle-\cos{\phi}+\frac{\sin{\phi-du}}{\tan{\psi}},$
$\displaystyle\dot{\phi}$ $\displaystyle=$ $\displaystyle 0,$
$\displaystyle\dot{\psi}$ $\displaystyle=$ $\displaystyle u-\frac{\sin{\phi-
du}}{\sin{\psi}}w.$ (7)

For the tracking phase, the idea is to keep the agent within a neighbourhood
of the obstacle curve and have the velocity track the obstacle tangent as
close as possible. Thus, the aim is to keep
$d\in[\frac{d_{0}}{2},\frac{3d_{0}}{2}]$ and
$\psi\in[\frac{\pi}{2}-\psi_{m},\frac{\pi}{2}+\psi_{m}]$ where $0<d_{0}\ll 1$
and $\psi_{m}>0$. Writing $\Delta=d-d_{0}$,
$\phi^{\prime}:=\phi-\frac{\pi}{2}$ and $\delta:=\psi-\frac{\pi}{2}$, then,
$\dot{\phi^{\prime}}=0\implies\phi^{\prime}:=\phi_{m}\geq 0$ (we drop this
non-negativity assumption at the end of this section) and

$\displaystyle\dot{\Delta}$ $\displaystyle=$
$\displaystyle\sin{\phi_{m}}-(\cos{\phi_{m}}-(\Delta+d_{0})u)\tan{\delta},$
$\displaystyle\dot{\delta}$ $\displaystyle=$ $\displaystyle
u-\left(\frac{\cos{\phi_{m}}-(\Delta+d_{0})u}{\cos{\delta}}\right)w.$ (8)

In order, to obtain a control law for the above, we consider the inner
approximation

$\displaystyle\dot{\Delta}$ $\displaystyle=$
$\displaystyle\sin\phi_{m}-\alpha\delta,$ $\displaystyle\dot{\delta}$
$\displaystyle=$ $\displaystyle u-\beta,$ (9)

where

$\displaystyle\alpha$ $\displaystyle\in$
$\displaystyle[\alpha_{0},\alpha_{1}]=\left[\frac{2\cos{\phi_{m}}-3d_{0}M}{2},\frac{2\cos{\phi_{m}}+3d_{0}M}{2}\right],$
$\displaystyle\beta$ $\displaystyle\in$
$\displaystyle[-\beta_{0},\beta_{0}]=\left[-\frac{2\cos{\phi_{m}}+3d_{0}M}{2\cos{\psi_{m}}},\frac{2\cos{\phi_{m}}+3d_{0}M}{2\cos{\psi_{m}}}\right].$

This immediately yields some conditions for stabilizability,

$\displaystyle d_{0}M<\frac{2}{3}\cos{\phi_{m}},\hskip
14.22636pt\text{and}\hskip
14.22636ptM>\frac{2\cos{\phi_{m}}+3d_{0}M}{2\cos{\psi_{m}}}.$

Let
$\psi_{0}:=\frac{\sin\phi_{m}}{2}\left(\frac{1}{a_{0}}+\frac{1}{a_{1}}\right)$
and impose $\psi_{m}>\frac{sin(\phi_{m})}{a_{0}}$ and
$\frac{\sin{\phi_{m}}}{a_{1}}<\phi_{m}<\frac{\sin{\phi_{m}}}{a_{0}}$. We
define a quadratic control Lyapunov function,

$V=\Delta^{2}+p^{2}(\delta-\psi_{0})^{2}+2q\Delta(\delta-\psi_{0}),$ (10)

and seek the region of attraction for the tracking phase by imposing
$\dot{V}<0$,

$(\Delta+q\left(\delta-\psi_{0}\right))\left(\sin\phi_{m}-\alpha\delta\right)-\beta(p^{2}\Delta+q\left(\delta-\psi_{0}\right))<M\left\lvert
p^{2}\Delta+q\left(\delta-\psi_{0}\right)\right\rvert,$

where we set
$u=-M\text{sgn}\left(p^{2}\Delta+q\left(\delta-\psi_{0}\right)\right)$. For
convenience, we find a subset for the region described above,

$\displaystyle\hat{m}\left(\delta+\hat{c}\right)\leq\Delta\leq\hat{m}\left(\delta-\hat{c}\right),$
(11)

where
$\hat{m}=\frac{q}{p^{2}-q^{2}}\frac{q\sin{\phi_{m}}-(M-\beta_{1})p^{2}-\alpha_{1}q\psi_{0}}{M-\beta_{1}}$
and
$\hat{c}=-\frac{\sin{\phi_{m}}}{\alpha_{1}}+\frac{(M-\beta_{1})p^{2}}{\alpha_{1}q}$.
However, considering this simplified region yields yet another stability
condition,

$\frac{\sin{\phi_{m}}}{\alpha_{1}}-\frac{p^{2}}{\alpha_{1}q}(M-\beta_{1})>\psi_{0}.$

Before proceeding, we summarise all constraints:

$\displaystyle\psi_{m}$ $\displaystyle>$
$\displaystyle\frac{\sin{\phi_{m}}}{\alpha_{0}},$ (12a)
$\displaystyle\phi_{m}$ $\displaystyle>$
$\displaystyle\frac{\sin{\phi_{m}}}{\alpha_{1}}$ (12b) $\displaystyle
2\cos{\phi_{m}}-3d_{0}M$ $\displaystyle>$ $\displaystyle 0,$ (12c)
$\displaystyle 2M\cos\psi_{m}$ $\displaystyle>$ $\displaystyle
2\cos{\phi_{m}}-3d_{0}M,$ (12d)
$\displaystyle\frac{\sin{\phi_{m}}}{\alpha_{1}}-\frac{p^{2}}{\alpha_{1}q}(M-\beta_{1})$
$\displaystyle>$ $\displaystyle\psi_{0}.$ (12e)

We wish to maximize the region of attraction for tracking (remember that we
need to bound the control Lyapunov function ellipse so that it is physically
relevant, i.e. $\lvert\Delta\rvert\leq\frac{d_{0}}{2}$ and
$\lvert\delta\rvert\leq\psi_{m}-\psi_{0}$). Whence to satisfy (12c) and (12d),
we select,

$3d_{0}M=\cos{\phi_{m}}\hskip 14.22636pt\text{and}\hskip
14.22636pt\cos{\psi_{m}}=\frac{2\cos{\phi_{m}}}{M}.$

This ensures that $d_{0}$ and $\psi_{m}$ are maximised and also simplifies the
parameters, $\alpha_{0}=\frac{\cos\phi_{m}}{2}$,
$\alpha_{1}=\frac{3\cos\phi_{m}}{2}$, $\beta_{1}=\frac{3M}{4}$
$\psi_{0}=\frac{4\tan\phi_{m}}{3}$. Moreover, we impose $M\geq 3$ and
$\phi_{m}<0.431$ in order to satisfy (12a) and (12b).
In order to find the largest region of attraction we impose that the elliptic
control Lyapunov at
$(-\psi_{0}+\frac{\sin{\phi_{m}}}{\alpha_{1}}-\frac{p^{2}}{\alpha_{1}q}(M-\beta_{1}),0)$
has the same tangent gradient as the two boundary lines in (11). This is
achieved by selecting,

$p^{2}=q^{2}-q\sqrt{q^{2}+\frac{4q}{M}\sin{\phi_{m}}}.$ (13)

Note that the condition in (12e) is equivalent to imposing
$q\leq-\frac{4}{M}\sin{\phi_{m}}$.
We proceed by fitting the ellipse inside the correct box in order to be
physically relevant and thus require,

$\frac{p^{2}\left(\frac{2\tan{\phi_{m}}}{3}+\frac{Mp^{2}}{6q\cos{\phi_{m}}}\right)^{2}}{p^{2}-q^{2}}\leq\frac{\cos^{2}{\phi_{m}}}{36M^{2}}\leq\left(\psi_{m}-\psi_{0}\right)^{2},$

which is equivalent to requiring that $(\phi_{m},q)$ is in the intersection:

$\left\\{0>q\geq-\frac{1}{8^{\frac{1}{4}}M}\right\\}\bigcap\left\\{q\leq\left(\frac{0.109}{\sqrt{\arccos{\frac{2}{M}}}}-0.775\right)\phi_{m}-\frac{0.236}{M\sqrt{\arccos{\frac{2}{M}}}}\right\\}.$

Thus, to maximize $\phi_{m}$, we select, $q=-\frac{1}{8^{\frac{1}{4}}M}$ and
obtain

$\phi_{m}\leq\frac{\left(\frac{1}{3M\sqrt{2\arccos\left(\frac{2}{M}\right)}}-\frac{1}{8^{\frac{1}{4}}M}\right)\left(1.293M\sqrt{2\arccos\left(\frac{2}{M}\right)}\right)}{\left(1-5.013\sqrt{2\arccos\left(\frac{2}{M}\right)}\right)}.$

We conclude the tracking section by bounding the spurious region around the
origin where $\dot{V}\geq 0$. The latter is contained inside the following
ellipse,

$\Delta^{2}+p^{2}\left(\delta-\psi_{0}\right)^{2}+2q\Delta\left(\delta-\psi_{0}\right)\leq\frac{4p^{2}}{9q^{2}}\left(p^{2}-q^{2}\right)\tan^{2}\phi_{m},$
(14)

whereas the maximal region of attraction is given by the intersection of the
complement of the region in (14) with the region below,

$\Delta^{2}+p^{2}\left(\delta-\psi_{0}\right)^{2}+2q\Delta\left(\delta-\psi_{0}\right)\leq
p^{2}\left(\frac{2}{3}\tan\phi_{m}+\frac{Mp^{2}}{6q\cos\phi_{m}}\right)^{2}.$
(15)

We also stress that by symmetry, the condition $\phi_{m}\geq 0$ can be dropped
but (13) is replaced with

$p^{2}=q^{2}-q\sqrt{q^{2}+\frac{4q}{M}\sin{\phi_{m}}\text{sgn}(\phi_{m})},$
(16)

which ensures that the rest of the analysis remains valid.
Hence, thus far we have proved the existence of $\delta_{tr}$ such that if the
sensor noise is bounded by $\delta_{tr}$ then the agent is guaranteed to be
able to track an obstacle (this follows from the fact that the Lyapunov
function is strictly decreasing). Finally, note that while $M\geq 3$, we
arbitrarily select $M=5$ in order to ensure that tracking occurs close enough
to the obstacle (i.e $d_{0}\approx\frac{6}{100}r_{0}$) and a decent
sensitivity to sensor noise (empirically determined via simulations, see §4).

###  A.2 Locking

Consider the moment when the agent first detects the presence of the obstacle.
At this time instance, the coordinates of the impact point, $f_{p}$, and the
tangent at the later point, $\dot{f}_{p}$, will be known (subject to noise).
In order to simplify the analysis in the following section, we define
coordinates in the complex plane, $\mathbb{C}$, and tangents/velocities on the
unit circle, $\mathbb{T}$, with the understanding that if $x\in\mathbb{C}$
then $\text{Re}(x)$ represents the horizontal coordinate, $\text{Im}(x)$
represent the vertical coordinate, etc. We, thus define local coordinates with
the local origin at $f_{p}$ and define the real axis to be parallel to
$\dot{f}_{p}$ while the imaginary axis is parallel to the outward normal to
the obstacle curve at $f_{p}$. Note that by defining such a coordinate axis we
obtain a control law in local coordinates which will then need to be converted
in the global coordinate frame.
The objective is to drive the agent to the location $jd_{0}$ with velocity
$v_{0}$ where $j=\sqrt{-1}$ and $v_{0}>0$ is the magnitude of the constant
velocity of the agent. Note that we do this by keeping the impact point of the
sensor at $f_{p}$. In the absence of noise, it is straightforward to define a
nominal trajectory bringing the agent to the desired state. Namely,

$\displaystyle\begin{split}\begin{cases}\overline{x}(t)=\left(-d_{m}+j\frac{r_{0}}{\overline{u}}\right){\rm
e}^{-j\theta}+\frac{r_{0}}{\overline{u}}{\rm
e}^{j\left(\frac{a_{0}\overline{u}}{v_{0}}t-\theta-\frac{\pi}{2}\right)}\\\
\overline{v}(t)=v_{0}{\rm
e}^{j\left(\frac{a_{0}\overline{u}}{v_{0}}t-\theta\right)}\\\
\overline{u}(t)=\frac{M}{c_{1}(\theta)\left(1+\epsilon\right)}\end{cases}t\in[0,t_{1}]\end{split}$
(17a)
$\displaystyle\begin{split}\begin{cases}\overline{x}(t)=\overline{x}(t_{1})+\overline{v}(t_{1})(t-t_{1})\\\
\overline{v}(t)=\overline{v}(t_{1})\\\ \overline{u}(t)=0\end{cases}\hskip
56.9055ptt\in(t_{1},t_{2}]\end{split}$ (17b)
$\displaystyle\begin{split}\begin{cases}\overline{x}(t)=j\left(d_{0}+\frac{r_{0}}{\overline{u}}\right)+\frac{r_{0}}{\overline{u}}{\rm
e}^{j\left(\frac{a_{0}\overline{u}}{v_{0}}(t-T)-\frac{\pi}{2}\right)}\\\
\overline{v}(t)=v_{0}{\rm
e}^{j\left(\frac{a_{0}\overline{u}}{v_{0}}(t-T)\right)}\\\
\overline{u}(t)=\frac{M}{c_{2}(\theta)\left(1+\epsilon\right)}\end{cases}\hskip
14.22636ptt\in(t_{2},T]\end{split}$ (17c)

where we recall that $d_{m}$ is the maximal depth of the sensor,
$\cos{\theta}:=\frac{\text{Re}(\overline{v}(0))}{v_{0}}$, $d_{0}$ is the
desired distance from the obstacle required for tracking, $r_{0}$ is the
minimum radius of curvature of the obstacle boundary curve, $a_{0}M$ is the
maximum allowable actuation (obtained from tracking), $t_{1},t_{2},T$ ensure
that the nominal trajectory is continuous and that the intermediate linear
trajectory (i.e. $t\in[t_{1},t_{2}])$ is the common tangent connecting the
initial (i.e. $t\in[0,t_{1}]$) and final (i.e. $t\in[t_{2},T]$) circular
segments. $\epsilon>0$ parametrizes the increase in radius, with respect to
the minimum radius of the agent, necessary in order to handle noise and will
be calculated when noise is introduced. Moreover, for future convenience we
define,
$\hat{x}_{1}(\overline{u}):=\left(-d_{m}+j\frac{r_{0}}{\overline{u}}\right){\rm
e}^{j\theta}$, $\hat{x}_{2}:=\overline{x}(t_{1})$ and
$\hat{x}_{3}(\overline{u}):=j\left(d_{0}-\frac{r_{0}}{\overline{u}}\right)$,
$\hat{x}_{1,3}^{+}:=\hat{x}_{1,3}\left(\lvert\overline{u}\rvert\right)$,
$c_{2}(\theta):=\text{sgn}\left(a(\theta)\right)$ where

$a(\theta):=\frac{2r_{0}(1+\epsilon)}{M}\text{Re}(\hat{x}_{1}^{+})+\text{Im}(\hat{x}_{1}^{+}-\hat{x}_{3}^{+})\sqrt{\text{Re}(\hat{x_{1}}^{+})^{2}+\text{Im}(\hat{x}_{1}^{+}-\hat{x}_{3}^{+})^{2}-\frac{4r_{0}^{2}(1+\epsilon)^{2}}{M^{2}}}.$

Similarly,
$c_{1}(\theta):=\text{sgn}\left(\cos{\theta}\left(1+\frac{Md_{0}}{r_{0}(1+\epsilon)}\right)-1\right)$.
We then proceed with the introduction of disturbances of the appropriate form
in the nominal trajectories. For the initial ($t\in[0,t_{1}]$) and final
($t\in(t_{2},T]$) stages, we write,

$\begin{cases}x(t)=\hat{x}_{1,3}+r_{0}\left[\frac{1}{\overline{u}}+\Delta(t)\right]{\rm
e}^{j\overline{u}q(t)},\\\ v(t)=jv_{0}{\rm
e}^{j\left(\overline{u}q(t)+\delta(t)\right)},\end{cases}$ (18a) where
$\delta,\Delta,q\in\mathbb{R}$, are non-dimensional and satisfy
$\begin{cases}\tan\delta:=-\frac{\text{Re}\left(\left(x-\hat{x}_{1,3}\right)^{\prime}v\right)}{\text{Im}\left(\left(x-\hat{x}_{1,3}\right)^{\prime}v\right)},\\\
\Delta:=\frac{\left\lvert
x-\hat{x}_{1,3}\right\rvert}{r_{0}}-\frac{1}{\overline{u}}.\end{cases}$ (18b)

Similarly for the intermediate stage ($t\in(t_{1},t_{2}]$),

$\begin{cases}x(t)=\hat{x}_{2}+\frac{v_{0}\overline{v}(t)}{a_{0}}\left[q(t)+j\Delta\right],\\\
v(t)=\overline{v}(t){\rm e}^{j\delta(t)},\end{cases}$ (19a) with,
$\begin{cases}\tan\delta:=-\frac{\text{Im}\left(v^{\prime}\overline{v}\right)}{\text{Re}\left(v^{\prime}\overline{v}\right)},\\\
\Delta:=-\frac{1}{v_{0}r_{0}}\text{Im}\left(\left(x-\hat{x}_{2}\right)^{\prime}\overline{v}\right).\end{cases}$
(19b)

Moreover, we can derive the dynamic equations for the disturbances, in the
similar way as we did for the tracking case. We recall that we defined the
non-dimensional the time, $\tilde{t}=\frac{a_{0}}{v_{0}}t$ whence the dynamic
non-dimensional in time equations for the initial and final stage are given by

$\displaystyle\dot{\delta}$ $\displaystyle=u-\overline{u}\dot{q},$
$\displaystyle\dot{\Delta}$ $\displaystyle=-\sin{\delta},$
$\displaystyle\dot{q}$
$\displaystyle=\frac{\cos{\delta}}{1+\overline{u}\Delta},$ (20a) whereas for
the intermediate stage, $\displaystyle\dot{\delta}$
$\displaystyle=u-\overline{u}\dot{q},$ $\displaystyle\dot{\Delta}$
$\displaystyle=-\sin{\delta},$ $\displaystyle\dot{q}$
$\displaystyle=\frac{\cos{\delta}}{1+\overline{u}\Delta}.$ (20b)

We stress here that the necessary space required for locking is given by the
tubular neighbourhood of the obstacle that has radius
$r_{0}\left(\frac{3\left(1+\epsilon\right)}{M}+\frac{3d_{0}}{2}\right)<r_{0}$.
This thus imposes the minimal allowable sensor depth. Note that the
aforementioned distance was obtained by considering the agent approaching a
convex obstacle with velocity orthogonal to obstacle tangent. The above
argument also remains valid for non-convex obstacles since by assumption at
each point on the obstacle boundary curve there are no other boundary curves
within a ball of radius $r_{0}$ (condition (ii) in Theorem 1).
Furthermore, we can compute the minimal actuation rate of the sensor,
$\gamma$, by analysing the dynamic equations for $d,\phi$ and $\psi$ in the
locking phase (derivation analogous to tracking),

$\displaystyle\dot{d}$ $\displaystyle=$ $\displaystyle-v_{0}\cos{\phi},$
$\displaystyle\dot{\phi}$ $\displaystyle=$
$\displaystyle\frac{v_{0}\sin{\phi}}{d}-\frac{a_{0}}{v_{0}}u$
$\displaystyle\dot{\psi}$ $\displaystyle=$
$\displaystyle\frac{v_{0}\sin{\phi}}{d},$ (21)

which thus implies
$\gamma\geq\frac{a_{0}}{v_{0}}\left(\frac{M}{1+\epsilon}+\frac{2r_{0}}{d_{0}}\right)$.
We conclude this by designing the control law which proves that locking is
possible under our assumptions. We begin with the initial and final circular
motion segments. We wish to keep the disturbances in
$\lvert\delta\rvert\leq\delta_{m}\leq\psi_{m}-\phi_{m}$,
$\lvert\Delta\rvert\leq\Delta_{m}\leq\frac{d_{0}}{2}$ (so that noise does not
interfere with the agent’s ability to track) and $\dot{q}\approx 1$. Note that
from equation (20a) it suffices to keep $\delta,\Delta$ small in order to
maintain $\dot{q}\approx 1$. We proceed by obtaining an inner approximation
for the equation (20a),

$\displaystyle\dot{\delta}$ $\displaystyle=u-\beta,$
$\displaystyle\dot{\Delta}$ $\displaystyle=-\alpha\delta,$ (22)

where

$\alpha\in\left[\frac{\sin{\delta_{m}}}{\delta_{m}},1\right]\,\,\,\text{and}\,\,\,\beta\in\left[-\frac{\lvert\overline{u}\rvert}{1-\Delta_{m}\lvert\overline{u}\rvert},\frac{\lvert\overline{u}\rvert}{1-\Delta_{m}\lvert\overline{u}\rvert}\right].$

and we note that we have reduced this problem to the one solved in the
tracking case. So omitting most details, our control is defined as

$u=-M\text{sgn}\left(\delta-\frac{p}{\sqrt{2}}\Delta\right)$ (23)

where $p=\frac{2M}{\sqrt{2+\epsilon}}$ and the control Lyapunov function is
defined as the quadratic,

$V:=\delta^{2}+p^{2}\Delta-\sqrt{2}p\delta\Delta.$ (24)

Maximimizing the region of attraction for the above control Lyapunov function
we obtain the bounds, $\Delta_{m}\leq\frac{\epsilon}{2M}$ and
$\delta_{m}\leq\frac{\epsilon}{\sqrt{2+\epsilon}}$. Whence in order to comply
with the tracking requirement we require $\epsilon\leq 0.151$. We maximise
$\epsilon$ in order to maximize the noise that can be handled and hence we
obtain $\delta_{m}=0.103$ and $\Delta_{m}=0.030$, $p=6.818$.
Controlling the linear intermediate portion is simpler and does not require
discontinuous feedback. The requirement that $\dot{q}\approx 1$ in equation
(20b) is analogous to initial/final cases we just studied and thus only
requires that $\lvert\delta\rvert\leq\delta_{m}$,
$\lvert\Delta\rvert\leq\Delta_{m}$. We define the control Lyapunov function as

$V=\delta^{2}+q^{2}\Delta^{2},$ (25)

and the control law as $u=-\delta-q^{2}\Delta$ where
$q^{2}=\frac{M-\delta_{m}}{\Delta_{m}}$. It is straightforward to check that
for $\lvert\delta\rvert\leq\delta_{m}$ and $\lvert\Delta\rvert\leq\Delta_{m}$,
$\dot{V}<0$ and $\lvert u\rvert\leq M$, whence concluding the locking section.
To summarize, in this section we proved the existence of $\delta_{loc}$, such
that if the sensor noise is bounded by $\delta_{loc}$ then the agent is able
to lock onto an obstacle.
Note that tracking the nominal curve in the linear intermediate stage of
locking is analogous to tracking the attraction line in absence of obstacles.
Thus, we will use the same control law in order for the agent follow to the
attraction line.

###  A.3 Unlocking

As described in the algorithm, we will stop the tracking phase and begin the
unlocking phase when the agent’s position is in a neighbourhood the attraction
line. We aim to drive the system to have velocity parallel to $v(0)$. As in
locking, we define a local coordinate axis where the vertical axis is parallel
to the velocity of the agent at the time instance when tracking stops and the
horizontal axis is orthogonal to the later and points away from the obstacle.
In the absence of noise, we define nominal trajectories,

$\displaystyle\begin{split}\begin{cases}\overline{x}(t)=\frac{r_{0}}{\overline{u}}\left(1-{\rm
e}^{-j\frac{a_{0}\overline{u}}{v_{0}}t}\right)\\\ \overline{v}(t)=jv_{0}{\rm
e}^{-j\left(\frac{a_{0}\overline{u}}{v_{0}}t\right)}\\\
\overline{u}(t)=\frac{M}{\left(1+\epsilon\right)}\end{cases}\hskip
79.6678ptt\in[0,t_{1}]\end{split}$ (26a)
$\displaystyle\begin{split}\begin{cases}\overline{x}(t)=\left(c_{1}+jc_{2}\right)+\frac{r_{0}}{\overline{u}}{\rm
e}^{j\frac{a_{0}\overline{u}}{v_{0}}(t-T)+\theta}\\\
\overline{v}(t)=jv_{0}{\rm
e}^{j\frac{a_{0}\overline{u}}{v_{0}}(t-T)+\theta}\\\
\overline{u}(t)=\frac{M}{\left(1+\epsilon\right)}\end{cases}\hskip
28.45274ptt\in(t_{1},T]\end{split}$ (26b)

where $t_{1},t_{2},T$ ensure that the above two circles are tangent to each
other, $\cos{\theta}=\frac{\text{Re}\left(\hat{v}(0)\right)}{v_{0}}$ where
$\hat{v}(0)$ is the initial agent velocity in the local unlocking coordinate
frame, $\epsilon=0.151$ obtained from locking,
$r=\frac{r_{0}(1+\epsilon)}{M}$, $c_{1}=\lambda\cos{\theta}-r\sin{\theta}$,
$c_{2}=\lambda\sin{\theta}+r\cos{\theta}$ and
$\lambda=r\left(\cos{\theta}+\sqrt{\left(1-\sin{\theta}\right)\left(3+\sin{\theta}\right)}\right)$.
When considering noise, we note that the unlocking control problem is
analogous to the locking one (in unlocking there is no linear segment in the
nominal trajectory) so the latter discussion applies. Just as in locking we
have thus proved the existence of a sensor noise bound $\delta_{unloc}$ which
guarantees unlocking.
Furthermore, note that the unlocking manoeuvre requires
$r_{0}\left(\sqrt{3}+1\right)\frac{1+\epsilon}{M}$ of free-space (consider
$\theta=0$ in the nominal trajectories to obtain the latter). However, we
stress that such a manoeuvre is done while directing the sensor towards the
obstacle (i.e. not looking ahead) so we do not expect the sensor to be aligned
with the velocity once $v$ is the neighbourhood of $v(0)$. The worst case
scenario occurs when we need to rotate the sensor by $\pi$ which requires a
guaranteed free-space of $\frac{\pi v_{0}}{\gamma}$. Combining, the free-space
and sensor considerations for the unlocking phase, we find that the free-
neighbourhood required for unlocking is contained in the one required for
locking.


#  The minimal size of graphs with given pendant-tree connectivity
***Supported by the National Science Foundation of China (Nos. 11551001,
11161037, 11461054) and the Science Found of Qinghai Province (No.
2014-ZJ-907).

Yaping Mao1,2†††E-mail<EMAIL_ADDRESS>
1Department of Mathematics, Qinghai Normal University,
2Key Laboratory of IOT of Qinghai Province,
Xining, Qinghai 810008, China

###### Abstract

The concept of pendant-tree $k$-connectivity $\tau_{k}(G)$ of a graph $G$,
introduced by Hager in 1985, is a generalization of classical vertex-
connectivity. Let $f(n,k,\ell)$ be the minimal number of edges of a graph $G$
of order $n$ with $\tau_{k}(G)=\ell\ (1\leq\ell\leq n-k)$. In this paper, we
give some exact value or sharp bounds of the parameter $f(n,k,\ell)$.
Keywords: connectivity, Steiner tree, packing, pendant-tree connectivity
AMS subject classification 2010: 05C05, 05C40, 05C70.

##  1 Introduction

A processor network is expressed as a graph, where a node is a processor and
an edge is a communication link. Broadcasting is the process of sending a
message from the source node to all other nodes in a network. It can be
accomplished by message dissemination in such a way that each node repeatedly
receives and forwards messages. Some of the nodes and/or links may be faulty.
However, multiple copies of messages can be disseminated through disjoint
paths. We say that the broadcasting succeeds if all the healthy nodes in the
network finally obtain the correct message from the source node within a
certain limit of time. A lot of attention has been devoted to fault-tolerant
broadcasting in networks [9, 13, 15, 36]. In order to measure the ability of
fault-tolerance, the above path structure connecting two nodes are generalized
into some tree structures connecting more than two nodes, see [17, 19, 23]. To
show these generalizations clearly, we must state from the connectivity in
graph theory. We divide our introduction into the following four subsections
to state the motivations and our results of this paper.

###  1.1 Connectivity and $k$-connectivity

All graphs considered in this paper are undirected, finite and simple. We
refer to the book [1] for graph theoretical notation and terminology not
described here. For a graph $G$, let $V(G)$, $E(G)$, $e(G)$, $\bar{G}$,
$\Delta(G)$ and $\delta(G)$ denote the set of vertices, the set of edges, the
size, the complement, the maximum degree and the minimum degree of $G$,
respectively. In the sequel, let $K_{s,t}$, $K_{n}$, $W_{n}$, $C_{n}$, and
$P_{n}$ denote the complete bipartite graph of order $s+t$ with part sizes $s$
and $t$, complete graph of order $n$, wheel of order $n$, cycle of order $n$,
and path of order $n$, respectively. For any subset $X$ of $V(G)$, let $G[X]$
denote the subgraph induced by $X$, and $E[X]$ the edge set of $G[X]$. For two
subsets $X$ and $Y$ of $V(G)$ we denote by $E_{G}[X,Y]$ the set of edges of
$G$ with one end in $X$ and the other end in $Y$. If $X=\\{x\\}$, we simply
write $E_{G}[x,Y]$ for $E_{G}[\\{x\\},Y]$.

Connectivity is one of the most basic concepts of graph-theoretic subjects,
both in combinatorial sense and the algorithmic sense. It is well-known that
the classical connectivity has two equivalent definitions. The _connectivity_
of $G$, written $\kappa(G)$, is the minimum order of a vertex set $S\subseteq
V(G)$ such that $G-S$ is disconnected or has only one vertex. We call this
definition the ‘cut’ version definition of connectivity. A well-known theorem
of Whitney [38] provides an equivalent definition of connectivity, which can
be called the ‘path’ version definition of connectivity. For any two distinct
vertices $x$ and $y$ in $G$, the _local connectivity_ $\kappa_{G}(x,y)$ is the
maximum number of internally disjoint paths connecting $x$ and $y$. Then
$\kappa(G)=\min\\{\kappa_{G}(x,y)\,|\,x,y\in V(G),x\neq y\\}$ is defined to be
the _connectivity_ of $G$. For connectivity, Oellermann gave a survey paper on
this subject; see [31].

Although there are many elegant and powerful results on connectivity in graph
theory, the basic notation of classical connectivity may not be general enough
to capture some computational settings. So people want to generalize this
concept. For the ‘cut’ version definition of connectivity, we find the above
minimum vertex set without regard the number of components of $G-S$. Two
graphs with the same connectivity may have differing degrees of vulnerability
in the sense that the deletion of a vertex cut-set of minimum cardinality from
one graph may produce a graph with considerably more components than in the
case of the other graph. For example, the star $K_{1,n}$ and the path
$P_{n+1}\ (n\geq 3)$ are both trees of order $n+1$ and therefore connectivity
$1$, but the deletion of a cut-vertex from $K_{1,n}$ produces a graph with $n$
components while the deletion of a cut-vertex from $P_{n+1}$ produces only two
components. Chartrand et al. [4] generalized the ‘cut’ version definition of
connectivity. For an integer $k\ (k\geq 2)$ and a graph $G$ of order $n\
(n\geq k)$, the _$k$ -connectivity_ $\kappa^{\prime}_{k}(G)$ is the smallest
number of vertices whose removal from $G$ of order $n\ (n\geq k)$ produces a
graph with at least $k$ components or a graph with fewer than $k$ vertices.
Thus, for $k=2$, $\kappa^{\prime}_{2}(G)=\kappa(G)$. For more details about
$k$-connectivity, we refer to [4, 16, 31, 32].

###  1.2 Generalized (edge-)connectivity

The generalized connectivity of a graph $G$, introduced by Hager [12], is a
natural generalization of the ‘path’ version definition of connectivity. For a
graph $G=(V,E)$ and a set $S\subseteq V(G)$ of at least two vertices, _an
$S$-Steiner tree_ or _a Steiner tree connecting $S$_ (or simply, _an
$S$-tree_) is a such subgraph $T=(V^{\prime},E^{\prime})$ of $G$ that is a
tree with $S\subseteq V^{\prime}$. Note that when $|S|=2$ an $S$-Steiner tree
is just a path connecting the two vertices of $S$. Two $S$-Steiner trees $T$
and $T^{\prime}$ are said to be _internally disjoint_ if $E(T)\cap
E(T^{\prime})=\varnothing$ and $V(T)\cap V(T^{\prime})=S$. For $S\subseteq
V(G)$ and $|S|\geq 2$, the _generalized local connectivity_ $\kappa_{G}(S)$ is
the maximum number of internally disjoint $S$-Steiner trees in $G$, that is,
we search for the maximum cardinality of edge-disjoint trees which include $S$
and are vertex disjoint with the exception of $S$. For an integer $k$ with
$2\leq k\leq n$, _generalized $k$-connectivity_ (or _$k$ -tree-connectivity_)
is defined as $\kappa_{k}(G)=\min\\{\kappa_{G}(S)\,|\,S\subseteq
V(G),|S|=k\\}$, that is, $\kappa_{k}(G)$ is the minimum value of
$\kappa_{G}(S)$ when $S$ runs over all $k$-subsets of $V(G)$. Clearly, when
$|S|=2$, $\kappa_{2}(G)$ is nothing new but the connectivity $\kappa(G)$ of
$G$, that is, $\kappa_{2}(G)=\kappa(G)$, which is the reason why one addresses
$\kappa_{k}(G)$ as the generalized connectivity of $G$. By convention, for a
connected graph $G$ with less than $k$ vertices, we set $\kappa_{k}(G)=1$. Set
$\kappa_{k}(G)=0$ when $G$ is disconnected. Note that the generalized
$k$-connectivity and $k$-connectivity of a graph are indeed different. Take
for example, the graph $H_{1}$ obtained from a triangle with vertex set
$\\{v_{1},v_{2},v_{3}\\}$ by adding three new vertices $u_{1},u_{2},u_{3}$ and
joining $v_{i}$ to $u_{i}$ by an edge for $1\leq i\leq 3$. Then
$\kappa_{3}(H_{1})=1$ but $\kappa^{\prime}_{3}(H_{1})=2$. There are many
results on the generalized connectivity, see [5, 19, 20, 21, 23, 24, 25, 26,
27, 33].

###  1.3 Pendant-tree (edge-)connectivity

The concept of pendant-tree connectivity [12] was introduced by Hager in 1985,
which is specialization of generalized connectivity (or _$k$ -tree-
connectivity_) but a generalization of classical connectivity. For an
$S$-Steiner tree, if the degree of each vertex in $S$ is equal to one, then
this tree is called a _pendant $S$-Steiner tree_. Two pendant $S$-Steiner
trees $T$ and $T^{\prime}$ are said to be _internally disjoint_ if $E(T)\cap
E(T^{\prime})=\varnothing$ and $V(T)\cap V(T^{\prime})=S$. For $S\subseteq
V(G)$ and $|S|\geq 2$, the _pendant-tree local connectivity_ $\tau_{G}(S)$ is
the maximum number of internally disjoint pendant $S$-Steiner trees in $G$.
For an integer $k$ with $2\leq k\leq n$, _pendant-tree $k$-connectivity_ is
defined as $\tau_{k}(G)=\min\\{\tau_{G}(S)\,|\,S\subseteq V(G),|S|=k\\}$. When
$k=2$, $\tau_{2}(G)=\tau(G)$ is just the connectivity of a graph $G$. For more
details on pendant-tree connectivity, we refer to [12, 28]. Clearly, we have

$\left\\{\begin{array}[]{ll}\tau_{k}(G)=\kappa_{k}(G),&\mbox{\rm
for}~{}k=1,2;\\\ \tau_{k}(G)\leq\kappa_{k}(G),&\mbox{\rm for}~{}k\geq
3.\end{array}\right.$

The relation between pendant-tree connectivity and generalized connectivity
are shown in the following Table 2.

| Pendant tree-connectivity | Generalized connectivity
---|---|---
Vertex subset | $S\subseteq V(G)\ (|S|\geq 2)$ | $S\subseteq V(G)\ (|S|\geq 2)$
Set of Steiner trees | $\left\\{\begin{array}[]{ll}\mathscr{T}_{S}=\\{T_{1},T_{2},\cdots,T_{\ell}\\}\\\ S\subseteq V(T_{i}),\\\ d_{T_{i}}(v)=1~{}for~{}every~{}v\in S\\\ E(T_{i})\cap E(T_{j})=\varnothing,\\\ \end{array}\right.$ | $\left\\{\begin{array}[]{ll}\mathscr{T}_{S}=\\{T_{1},T_{2},\cdots,T_{\ell}\\}\\\ S\subseteq V(T_{i}),\\\ E(T_{i})\cap E(T_{j})=\varnothing,\\\ \end{array}\right.$
Local parameter | $\tau(S)=\max|\mathscr{T}_{S}|$ | $\kappa(S)=\max|\mathscr{T}_{S}|$
Global parameter | $\tau_{k}(G)=\underset{S\subseteq V(G),|S|=k}{\min}\tau(S)$ | $\kappa_{k}(G)=\underset{S\subseteq V(G),|S|=k}{\min}\kappa(S)$

Table 2. Two kinds of tree-connectivities

The following two observations are easily seen.

###### Observation 1.1

If $G$ is a connected graph, then $\tau_{k}(G)\leq\mu_{k}(G)\leq\delta(G)$.

###### Observation 1.2

If $H$ is a spanning subgraph of $G$, then $\tau_{k}(H)\leq\tau_{k}(G)$.

In [12], Hager derived the following results.

###### Lemma 1.1

[12] Let $G$ be a graph. If $\tau_{k}(G)\geq\ell$, then $\delta(G)\geq
k+\ell-1$.

###### Lemma 1.2

[12] Let $G$ be a graph. If $\tau_{k}(G)\geq\ell$, then $\kappa(G)\geq
k+\ell-2$.

###### Lemma 1.3

[12] Let $k,n$ be two integers with $3\leq k\leq n$, and let $K_{n}$ be a
complete graph of order $n$. Then

$\tau_{k}(K_{n})=n-k.$

###### Lemma 1.4

[12] Let $K_{r,s}$ be a complete bipartite graph with $r+s$ vertices. Then

$\tau_{k}(K_{r,s})=\max\\{\min\\{r-k+1,s-k+1\\},0\\}.$

As a natural counterpart of the pendant-tree $k$-connectivity, we introduced
the concept of pendant-tree $k$-edge-connectivity. For $S\subseteq V(G)$ and
$|S|\geq 2$, the pendant-tree local edge-connectivity $\mu(S)$ is the maximum
number of edge-disjoint pendant $S$-Steiner trees in $G$. For an integer $k$
with $2\leq k\leq n$, the pendant-tree $k$-edge-connectivity $\mu_{k}(G)$ of
$G$ is then defined as $\mu_{k}(G)=\min\\{\mu(S)\,|\,S\subseteq V(G)\ and\
|S|=k\\}$. It is also clear that when $|S|=2$, $\mu_{2}(G)$ is just the
standard edge-connectivity $\lambda(G)$ of $G$, that is,
$\mu_{2}(G)=\lambda(G)$.

###  1.4 Application background and our results

In addition to being a natural combinatorial measure, both the pendant-tree
connectivity and the generalized connectivity can be motivated by its
interesting interpretation in practice. For example, suppose that $G$
represents a network. If one considers to connect a pair of vertices of $G$,
then a path is used to connect them. However, if one wants to connect a set
$S$ of vertices of $G$ with $|S|\geq 3$, then a tree has to be used to connect
them. This kind of tree with minimum order for connecting a set of vertices is
usually called a Steiner tree, and popularly used in the physical design of
VLSI (see [10, 11, 34]) and computer communication networks (see [8]).
Usually, one wants to consider how tough a network can be, for the connection
of a set of vertices. Then, the number of totally independent ways to connect
them is a measure for this purpose. The generalized $k$-connectivity can serve
for measuring the capability of a network $G$ to connect any $k$ vertices in
$G$.

Let $f(n,k,\ell)$ be the minimal number of edges of a graph $G$ of order $n$
with $\tau_{k}(G)=\ell\ (1\leq\ell\leq n-k)$. It is not easy to determine the
exact value of the parameter $f(n,k,\ell)$ for a general $k\ (3\leq k\leq n)$
and a general $\ell\ (1\leq\ell\leq n-k)$.

In Section 2, we obtain the following result for general $k$.

###### Theorem 1.1

Let $n,k$ be two integers with $3\leq k\leq n$ and $n\geq 15$. Then

$(1)$ $f(n,k,n-k)={n\choose{2}}$;

$(2)$ $f(n,k,n-k-1)={n\choose{2}}-2$;

$(3)$ $f(n,k,0)=n-1$;

$(4)$ $f(n,k,1)=\left\lceil\frac{kn}{2}\right\rceil$;

$(5)$ For $1\leq\ell\leq\frac{n}{2}-k+1$, we have

$\left\lceil\frac{1}{2}(k+\ell-1)n\right\rceil\leq
f(n,k,\ell)\leq(k+\ell-1)(n-k-\ell+1);$

$(6)$ For $\frac{n}{2}-k+2\leq\ell\leq n-k-2$, we have

$\left\lceil\frac{1}{2}(k+\ell-1)n\right\rceil\leq
f(n,k,\ell)\leq(k+\ell-1)(n-k-\ell+1)+{k+\ell-1\choose 2}.$

Moreover, the bounds are sharp.

For $k=n,n-1,n-2,n-3,3$, we get the following results in Section $3$.

###### Theorem 1.2

Let $n,k$ be two integers with $3\leq k\leq n$ and $n\geq 15$. Then

$(1)$ $f(n,n,0)=n-1$;

$(2)$ $f(n,n-1,1)={n\choose{2}}$, $f(n,n-1,0)=n-1$;

$(3)$ $f(n,n-2,2)={n\choose{2}}$, $f(n,n-2,1)={n\choose{2}}-2$,
$f(n,n-2,0)=n-1$;

$(4)$ $f(n,n-3,3)={n\choose{2}}$, $f(n,n-3,2)={n\choose{2}}-2$,
$f(n,n-3,1)={n\choose{2}}-n$; $f(n,n-3,0)=n-1$.

###### Theorem 1.3

Let $n$ be an integer with $n\geq 10$. Then

$(1)$ $f(n,3,0)=n-1$;

$(2)$ $f(n,3,1)=\lceil\frac{3n}{2}\rceil$;

$(3)$ $f(n,3,2)=2n$ for $n=pq$ and $p,q\geq 3$; $2n\leq
f(n,3,2)\leq\frac{5n}{2}$ for $n=2p$; $2n\leq f(n,3,2)\leq 4n-16$ if $n$ is a
prime number.

$(4)$ $\left\lceil\frac{(\ell+2)n}{2}\right\rceil\leq
f(n,3,\ell)\leq(\ell+1)(n-\ell)+1$ for $3\leq\ell\leq\frac{n-4}{3}$;

$(5)$ $\left\lceil\frac{(\ell+2)n}{2}\right\rceil\leq
f(n,3,\ell)\leq\left\lfloor\frac{n}{\ell+1}\right\rfloor(\ell+1)^{2}+(r+1)(\ell+1)+r-1$
for $\frac{n-1}{3}\leq\ell\leq\frac{n-r-2}{2}$ where $n\equiv r\ (mod\ \ell)$
and $r\geq 2$; $\left\lceil\frac{(\ell+2)n}{2}\right\rceil\leq
f(n,3,\ell)\leq(\ell+2)(n-\ell-2)$ for
$\frac{n-r-2}{2}\leq\ell\leq\frac{n-4}{2}$, or
$\frac{n-1}{3}\leq\ell\leq\frac{n-r-2}{2}$ where $n\equiv r\ (mod\ \ell)$ and
$r=0,1$;

$(6)$ $\left\lceil\frac{(\ell+2)n}{2}\right\rceil\leq
f(n,3,\ell)\leq(\ell+2)(n-\ell-2)+{\ell+2\choose 2}$ for
$\frac{n-2}{2}\leq\ell\leq n-6$;

$(7)$ $f(n,3,n-5)={n\choose 2}-\lfloor\frac{n-4}{2}\rfloor$;

$(8)$ $f(n,3,n-4)={n\choose 2}-2$;

$(9)$ $f(n,3,n-3)={n\choose 2}$.

##  2 For general $k$ and $\ell$

Given a vertex $x$ and a set $U$ of vertices, an _$(x,U)$ -fan_ is a set of
paths from $x$ to $U$ such that any two of them share only the vertex $x$. The
size of an $(x,U)$-fan is the number of internally disjoint paths from $x$ to
$U$.

###### Lemma 2.1

(Fan Lemma, [37], p-170) A graph is $k$-connected if and only if it has at
least $k+1$ vertices and, for every choice of $x$, $U$ with $|U|\geq k$, it
has an $(x,U)$-fan of size $k$.

###### Corollary 2.1

Let $G$ be a graph with $\kappa(G)=k$. Then $\tau_{k}(G)\geq 1$.

Proof. Since $\kappa(G)=k$, it follows from Lemma 2.1 that for any $S\subseteq
V(G)$ and $|S|=k$, there exist an $(x,S)$-fan, where $x\in V(G)-S$. So there
is a pendant $S$-Steiner tree in $G$, and hence $\tau(S)\geq 1$. From the
arbitrariness of $S$, we have $\tau_{k}(G)\geq 1$, as desired.

In [29], Mao and Lai obtained the following upper bound of $\tau_{k}(G)$.

###### Lemma 2.2

[29] Let $G$ be a connected graph of order $n\geq 6$. Let $k$ be an integer
with $3\leq k\leq n$. Then

$\tau_{k}(G)\leq\delta(G)-k+1.$

Moreover, the upper bound is sharp.

The Harary graph $H_{n,d}$ is constructed by arranging the $n$ vertices in a
circular order and spreading the $d$ edges around the boundary in a nice way,
keeping the chords as short as possible. Harary graph $H_{n,d}$ is a
$d$-connected graph on $n$ vertices, and the structure of $H_{n,d}$ depends on
the parities of $d$ and $n$; see [37].

  * Case 1: $d$ even. Let $d=2r$. Then $H_{n,2r}$ is constructed as follows. It has vertices $0,1,\cdots,n-1$ and two vertices $i$ and $j$ are jointed if $i-r\leq j\leq i+r$ (where addition is taken modulo $n$).

  * Case 2: $d$ odd, $n$ even. Let $d=2r+1$. Then $H_{n,2r+1}$ is constructed by first drawing $H_{n,2r}$ and then adding edges joining vertex $i$ to vertex $i+\frac{n}{2}$ for $1\leq i\leq\frac{n}{2}$.

  * Case 3: $d$ odd, $n$ even. Let $d=2r+1$. Then $H_{n,2r+1}$ is constructed by first drawing $H_{n,2r}$ and then adding edges joining vertex $0$ to vertices $\frac{n-1}{2}$ and $\frac{n+1}{2}$ and $i$ to vertex $i+\frac{n+1}{2}$ for $1\leq i\leq\frac{n-1}{2}$.

###### Lemma 2.3

[37] Let $H_{n,k}$ be the Harary graph of order $n\geq 6$. Then

$\kappa(H_{n,k})=k,\ e(H_{n,k})=\left\lceil\frac{kn}{2}\right\rceil.$

For general $k$ and $\ell$, we give a sharp lower bound of $f(n,k,\ell)$.

###### Proposition 2.1

Let $n,k$ be two integers with $3\leq k\leq n$ and $n\geq 15$. Then

$f(n,k,\ell)\geq\left\lceil\frac{1}{2}(k+\ell-1)n\right\rceil$

for $1\leq\ell\leq n-k-2$. Moreover, the bound is sharp.

Proof. Since $\tau_{k}(G)=\ell\ (1\leq\ell\leq n-k-2)$, it follows from Lemma
2.2 that $\delta(G)\geq k+\ell-1$. Denote by $X$ the set of vertices of degree
$k+\ell-1$ in $G$. Set $Y=V(G)\setminus X$. Let $m^{\prime},m^{\prime\prime}$
be the number of edges of $G[X],G[Y]$, respectively. Then

$|E_{G}[X,Y]|=(k+\ell-1)|X|-2m^{\prime}$ $None$

and

$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}e(G)$
$\displaystyle=$ $\displaystyle e(G[X])+e(G[Y])+|E_{G}[X,Y]|$ $\displaystyle=$
$\displaystyle m^{\prime}+m^{\prime\prime}+(k+\ell-1)|X|-2m^{\prime}$
$\displaystyle=$
$\displaystyle(k+\ell-1)|X|+(m^{\prime\prime}-m^{\prime}).~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}(2)$

Since every vertex in $Y$ has degree at least $k+\ell$ in $G$, it follow that

$\displaystyle\sum_{v\in Y}d(v)$ $\displaystyle=$ $\displaystyle
2m^{\prime\prime}+|E_{G}[X,Y]|$ $\displaystyle=$ $\displaystyle
2m^{\prime\prime}+(k+\ell-1)|X|-2m^{\prime}$ $\displaystyle\geq$
$\displaystyle(k+\ell)|Y|,$

and hence

$m^{\prime\prime}-m^{\prime}\geq\frac{1}{2}(k+\ell-1)(|Y|-|X|)+\frac{1}{2}|Y|.$
$None$

From $(1),(2),(3)$, we have

$e(G)=\frac{1}{2}(k+\ell-1)(|Y|+|X|)+\frac{1}{2}|Y|\geq\frac{1}{2}(k+\ell-1)n.$

Since the number of edges is an integer, it follows that

$e(G)\geq\left\lceil\frac{1}{2}(k+\ell-1)n\right\rceil,$

as desired.

To show the sharpness of the lower bound, we consider the following example.

Example 1. Let $H_{n,k}$ be the Harary graph of order $n\geq 6$. Then
$\kappa(H_{n,k})=\delta(H_{n,k})=k$. From Lemma 2.2, we have
$\tau_{k}(H_{n,k})\leq\delta(H_{n,k})-k+1=1$. From Corollary 2.1, we have
$\tau_{k}(H_{n,k})\geq 1$, and hence $\tau_{k}(H_{n,k})=1$. From Lemma 2.3,
$e(H_{n,k})=\left\lceil\frac{kn}{2}\right\rceil=f(n,k,1)$. So the lower bound
is sharp for $\ell=1$.

The following corollary is immediate from Proposition 2.1 and Example 1.

###### Corollary 2.2

Let $n,k$ be two integers with $3\leq k\leq n$ and $n\geq 5$. Then

$f(n,k,1)=\left\lceil\frac{kn}{2}\right\rceil.$

For general $k$ and $\ell\ (1\leq\ell\leq\frac{n}{2}-k+1)$, we give a sharp
upper bound of $f(n,k,\ell)$.

###### Proposition 2.2

Let $n,k,\ell$ be three integers with $3\leq k\leq n$ and
$1\leq\ell\leq\frac{n}{2}-k+1$. Then

$f(n,k,\ell)\leq(k+\ell-1)(n-k-\ell+1).$

Moreover, the bound is sharp.

Proof. Let $G=K_{k+\ell-1,n-k-\ell+1}$. Since $1\leq\ell\leq\frac{n}{2}-k+1$,
it follows that $n-k-\ell+1\geq k+\ell-1$. From Lemma 1.4, we have
$\tau_{k}(G)=\ell$. So $f(n,k,\ell)\leq(k+\ell-1)(n-k-\ell+1)$, as desired.

The join or complete product $G\vee H$ of two disjoint graphs $G$ and $H$ is
the graph with vertex set $V(G)\cup V(H)$ and edge set $E(G)\cup
E(H)\cup\\{uv\,|\,u\in V(G),v\in V(H)\\}$. For classical connectivity, the
following result is well-known.

###### Lemma 2.4

[1] Let $G$ and $H$ be two graphs. Then

$\kappa(G\vee H)=\min\\{|V(G)|+\kappa(H),|V(H)|+\kappa(G)\\}.$

For general $k$ and $\ell\ (\frac{n}{2}-k+2\leq\ell\leq n-k)$, we can also
give a sharp upper bound of $f(n,k,\ell)$.

###### Proposition 2.3

Let $n,k,\ell$ be three integers with $3\leq k\leq n$ and
$\frac{n}{2}-k+2\leq\ell\leq n-k$. Then

$f(n,k,\ell)\leq(k+\ell-1)(n-k-\ell+1)+{k+\ell-1\choose 2}.$

Moreover, the bound is sharp.

Proof. Let $G=K_{k+\ell-1}\vee(n-k-\ell+1)K_{1}$. Since $\delta(G)=k+\ell-1$,
it follows from Lemma 2.2 that $\tau_{k}(G)\leq\delta(G)-k+1=\ell$. It
suffices to show that $\tau_{k}(G)\geq\ell$. Let
$V(K_{k+\ell-1})=\\{y_{1},y_{2},\ldots,y_{k+\ell-1}\\}$ and
$X=V(G)-V(K_{k+\ell-1})=\\{x_{1},x_{2},\ldots,x_{n-k-\ell+1}\\}$. For any
$S\subseteq V(G)$ and $|S|=k$, if $S\subseteq X$, then the trees induced by
the edges in $E_{G}[y_{i},S]\ (1\leq i\leq k+\ell-1)$ are $k+\ell-1$
internally disjoint pendant $S$-Steiner trees, and hence $\tau(S)\geq
k+\ell-1$. If $S\subseteq Y$, then there are $\ell-1$ internally disjoint
pendant $S$-Steiner trees in $G[Y]$. These trees and the trees induced by the
edges in $E_{G}[x_{i},S]\ (1\leq i\leq n-k-\ell+1)$ are $n-k$ internally
disjoint pendant $S$-Steiner trees, and hence $\tau(S)\geq n-k\geq\ell$.
Suppose $S\cap X\neq\varnothing$ and $S\cap V(K_{k+\ell-1})\neq\varnothing$.
Without loss of generality, let $S\cap X=\\{x_{1},x_{2},\ldots,x_{r}\\}$ and
$S\cap V(K_{k+\ell-1})=\\{y_{1},y_{2},\ldots,y_{k-r}\\}$. Then the trees
induced by the edges in $\\{x_{i}y_{j}\,|\,1\leq i\leq r,\ k-r+1\leq j\leq
k+\ell-1\\}\cup\\{y_{i}y_{j}\,|\,1\leq i\leq k-r,\ k-r+1\leq j\leq
k+\ell-1\\}$ are $\ell-1+r\geq\ell$ internally disjoint pendant $S$-Steiner
trees, and hence $\tau(S)\geq n-1$. We conclude that $\tau(S)\geq n-1$ for any
$S\subseteq V(G)$ and $|S|=k$. From the arbitrariness of $S$, we have
$\tau_{k}(G)\geq\ell$, and hence $\tau_{k}(G)=\ell$. So
$f(n,k,\ell)\leq(k+\ell-1)(n-k-\ell+1)+{k+\ell-1\choose 2}$.

In [28], Mao and Lai characterized graphs with $\tau_{k}(G)=n-k,n-k-1,n-k-2$,
respectively.

###### Lemma 2.5

[28] Let $k,n$ be two integers with $3\leq k\leq n$ and $n\geq 4$, and let $G$
be a connected graph. Then $\tau_{k}(G)=n-k$ if and only if $G$ is a complete
graph of order $n$.

###### Lemma 2.6

[28] Let $k,n$ be two integers with $3\leq k\leq n$ and $n\geq 7$, and let $G$
be a connected graph. Then $\tau_{k}(G)=n-k-1$ if and only if
$\bar{G}=rK_{2}\cup(n-2r)K_{1}\ (r=1,2)$.

From $\ell=n-k,n-k-1,0$, we can derive the exact value of $f(n,k,\ell)$.

###### Proposition 2.4

Let $n,k$ be two integers with $3\leq k\leq n$ and $n\geq 15$. Then

$(i)$ $f(n,k,n-k)={n\choose{2}}$;

$(ii)$ $f(n,k,n-k-1)={n\choose{2}}-2$;

$(iii)$ $f(n,k,0)=n-1$.

Proof. $(i)$ From Lemma 2.5, $\tau_{k}(G)=n-k$ if and only if $G$ is a
complete graph of order $n$. So $f(n,k,n-k)={n\choose{2}}$.

$(ii)$ From Lemma 2.6, $\tau_{k}(G)=n-k-1$ if and only if
$\bar{G}=rK_{2}\cup(n-2r)K_{1}\ (r=1,2)$. Then $f(n,k,n-k-1)={n\choose{2}}-2$.

$(iii)$ The tree $T_{n}$ with $n$ vertices is the graph such that
$\tau_{k}(T_{n})=0$ with the minimal number of edges. So $f(n,k,1)=n-1$.

The results in Theorem 1.1 follow from Propositions 2.1, 2.2, 2.3 and 2.4.

##  3 For fixed $k$ and general $\ell$

The Cartesian product $G\Box H$ of two graphs $G$ and $H$, is the graph with
vertex set $V(G)\times V(H)$, in which two vertices $(u,v)$ and
$(u^{\prime},v^{\prime})$ are adjacent if and only if $u=u^{\prime}$ and
$(v,v^{\prime})\in E(H)$, or $v=v^{\prime}$ and $(u,u^{\prime})\in E(G)$.
Clearly, $|E(G\Box H)|=|E(H)||V(G)|+|E(G)||V(H)|$.

The lexicographic product $G\circ H$ of graphs $G$ and $H$ has the vertex set
$V(G\circ H)=V(G)\times V(H)$, and two vertices
$(u,v),(u^{\prime},v^{\prime})$ are adjacent if $uu^{\prime}\in E(G)$, or if
$u=u^{\prime}$ and $vv^{\prime}\in E(H)$. It is easy to see that $|E(G\circ
H)|=|E(H)||V(G)|+|E(G)||V(H)|^{2}$.

In this section, we study $f(n,k,\ell)$ for $k=n,n-1,n-2,n-3,3$ and general
$\ell$.

###  3.1 For $n-3\leq k\leq n$ and general $\ell$

Mao and Lai obtained the following results.

###### Lemma 3.1

[28] Let $G$ be a graph of order $n$. Then $\tau_{n}(G)=0$ if and only if $G$
is a graph of order $n$.

###### Lemma 3.2

[28] Let $G$ be a connected graph of order $n$. Then

$(1)$ $\tau_{n-1}(G)=1$ if and only if $G$ is a complete graph of order $n$.

$(2)$ $\tau_{n-1}(G)=0$ if and only if $G$ is not a complete graph of order
$n$.

###### Lemma 3.3

[28] Let $G$ be a connected graph of order $n$. Then

$(1)$ $\tau_{n-2}(G)=2$ if and only if $G$ is a complete graph of order $n$.

$(2)$ $\tau_{n-2}(G)=1$ if and only if $G=K_{n}\setminus M$ and $1\leq|M|\leq
2$, where $M$ is a matching of $K_{n}$ for $n\geq 7$.

$(3)$ $\tau_{n-2}(G)=0$ if and only if $G$ is one of the other graphs.

Graphs with $\tau_{n-3}(G)=\ell\ (0\leq\ell\leq 3)$ can be also characterized.

###### Proposition 3.1

Let $G$ be a connected graph of order $n\geq 9$. Then

$(1)$ $\tau_{n-3}(G)=3$ if and only if $G$ is a complete graph of order $n$.

$(2)$ $\tau_{n-3}(G)=2$ if and only if $G=K_{n}\setminus M$ and $1\leq|M|\leq
2$, where $M$ is a matching of $K_{n}$.

$(3)$ $\tau_{n-3}(G)=1$ if and only if $1\leq\Delta(\bar{G})\leq 2$, and
$|M|\geq 3$ if $M$ is a matching of $\bar{G}$.

$(4)$ $\tau_{n-3}(G)=0$ if and only if $G$ is one of the other graphs.

Proof. From Lemmas 2.5 and 2.6, $(1)$ and $(2)$ is true. We only need to show
that $(3)$ is true. Suppose that $\tau_{n-3}(G)=1$. We claim that
$1\leq\Delta(\bar{G})\leq 2$. Assume, to the contrary, that
$\Delta(\bar{G})\geq 3$. Then there exist four vertices $u,v,w,u_{1}$ such
that $u_{1}u,u_{1}v,u_{1}w\notin E(G)$. We choose $S\subseteq V(G)$ and
$|S|=n-3$ such that $V(G)-S=\\{u,v,w\\}$. Then $u_{1}\in S$. Observe that
there is no pendant $S$-Steiner tree in $G$. Therefore, $\tau_{n-3}(G)=0$, a
contradiction. So $1\leq\Delta(\bar{G})\leq 2$. From $(2)$, if $M$ is a
matching of $\bar{G}$, then $|M|\geq 3$.

Conversely, we suppose $1\leq\Delta(\bar{G})\leq 2$, and $|M|\geq 3$ if $M$ is
a matching of $\bar{G}$. For any $S\subseteq V(G)$ and $|S|=n-3$, there exist
three vertices, say $u,v,w$, such that $\bar{S}=V(G)-S=\\{u,v,w\\}$. Since
$1\leq\Delta(\bar{G})\leq 2$, it follows that $1\leq
d_{\bar{G}}(u),d_{\bar{G}}(v),d_{\bar{G}}(w)\leq 2$. Set
$S=\\{u_{1},u_{2},\ldots,u_{n-3}\\}$. If $d_{\bar{G}[\bar{S}]}(u)=2$, then
$uu_{i}\in E(G)\ (1\leq i\leq n-3)$, and hence the tree induced by the edges
in $E_{G}[u,S]$ is a pendant $S$-Steiner tree, and hence $\tau(S)\geq 1$. The
same is true when $d_{\bar{G}[\bar{S}]}(v)=2$ or $d_{\bar{G}[\bar{S}]}(w)=2$.
From now on, we suppose that $d_{\bar{G}[\bar{S}]}(u)\leq 1$,
$d_{\bar{G}[\bar{S}]}(v)\leq 1$ and $d_{\bar{G}[\bar{S}]}(w)\leq 1$. Clearly,
we have $G[\bar{S}]=P_{3}$ or $G[\bar{S}]=K_{3}$. Suppose $G[\bar{S}]=P_{3}$.
Without loss of generality, let $uv,uw\in E(G)$. Since
$1\leq\Delta(\bar{G})\leq 2$, there are at most two vertices in $S$, say
$u_{1},u_{2}$, such that $uu_{1},uu_{2}\notin E(G)$. Since
$1\leq\Delta(\bar{G})\leq 2$, it follows that $u_{i}v\in E(G)$ or $u_{i}w\in
E(G)$ for $i=1,2$. If $u_{1}w,u_{2}w\in E(G)$, then the tree induced by the
edges in $\\{uu_{i}\,|\,3\leq i\leq n-3\\}\cup\\{u_{1}w,u_{2}w\\}$ is a
pendant $S$-Steiner tree, and hence $\tau(S)\geq 1$. If $u_{1}v,u_{2}w\in
E(G)$, then the tree induced by the edges in $\\{uu_{i}\,|\,3\leq i\leq
n-3\\}\cup\\{u_{1}v,u_{2}w,uv,vw\\}$ is a pendant $S$-Steiner tree, and hence
$\tau(S)\geq 1$. From the arbitrariness of $S$, we have $\tau_{n-3}(G)\geq 1$.
Since $|M|\geq 3$ if $M$ is a matching of $\bar{G}$, it follows that
$\tau_{n-3}(G)\leq 1$. So $\tau_{n-3}(G)=1$.

Theorem 1.2 is immediate from Lemmas 3.1, 3.2, 3.3 and Proposition 3.1.

###  3.2 For $k=3$ and general $\ell$

In [35], S̆pacapan obtained the following result.

###### Lemma 3.4

[35] Let $G$ and $H$ be two nontrivial graphs. Then

$\kappa(G\Box
H)=\min\\{\kappa(G)|V(H)|,\kappa(H)|V(G)|,\delta(G)+\delta(H)\\}.$

For $k=3$ and $\ell=2$, we have the following.

###### Proposition 3.2

Let $n$ be an integer with $n\geq 10$.

$(1)$ If $n=pq$ and $p,q\geq 3$, then $f(n,3,2)=2n$;

$(2)$ If $n=2p$, then $2n\leq f(n,3,2)\leq\frac{5n-8}{2}$;

$(3)$ If $n$ is a prime number, then $2n\leq f(n,3,2)\leq 4n-16$.

Proof. $(1)$ If $n=pq$ and $p,q\geq 3$, then we consider the graph
$G=C_{p}\Box C_{q}$. From Lemma 3.4, $\kappa(G)=\delta(G)=4$. From Lemma 2.2,
we have $\tau_{3}(G)\leq\delta(G)-2=2$. We only need to show that
$\tau_{3}(G)\geq 2$. Let $C_{p,1},C_{p,2},\ldots,C_{p,q}$ be cycles in $G$
corresponding to $C_{p}$, and let
$C_{1,q}^{\prime},C_{2,q}^{\prime},\ldots,C_{p,q}^{\prime}$ be cycles in $G$
corresponding to $C_{q}$. For any $S\subseteq V(G)$ and $|S|=3$, it suffices
to show $\tau(S)\geq 2$. Let $S=\\{x,y,z\\}$.

If there exists some cycle $C_{p,i}$ such that $|S\cap V(C_{p,i})|=3$, then
$x,y,z\in V(C_{p,i})$. Let $x^{\prime},y^{\prime},z^{\prime}$ be the vertices
in $C_{p,i-1}$ corresponding to $x,y,z$ in $C_{p,i}$, and let
$x^{\prime\prime},y^{\prime\prime},z^{\prime\prime}$ be the vertices in
$C_{p,i+1}$ corresponding to $x,y,z$ in $C_{p,i}$, respectively. Then the
subgraph induced by the edges in
$E(C_{p,i-1})\cup\\{xx^{\prime},yy^{\prime},zz^{\prime}\\}$ contains a pendant
$S$-Steiner tree, and the subgraph induced by the edges in
$E(C_{p,i+1})\cup\\{xx^{\prime\prime},yy^{\prime\prime},zz^{\prime\prime}\\}$
contains a pendant $S$-Steiner tree. Note that these trees are internally
disjoint. Then $\tau(S)\geq 2$.

Suppose that there exists some cycle $C_{p,i}$ such that $|S\cap
V(C_{p,i})|=2$. Then there exists another cycle $C_{p,j}$ such that $|S\cap
V(C_{p,j})|=1$. Without loss of generality, let $|S\cap V(C_{p,1})|=2$ and
$|S\cap V(C_{p,2})|=1$. Then $x,y\in V(C_{p,1})$ and $z\in V(C_{p,2})$. Let
$x^{\prime},y^{\prime}$ be the vertices corresponding to $x,y$ in $C_{p,1}$,
and let $z^{\prime}$ be the vertices corresponding to $z$ in $C_{p,2}$.
Suppose $z^{\prime}\notin\\{x,y\\}$. Then the vertices $x,y,z^{\prime}$ divide
the cycle $C_{p,1}$ into three paths, say $P_{1},P_{2},P_{3}$. Similarly, the
vertices $x^{\prime},y^{\prime},z$ divide the cycle $C_{p,2}$ into three
paths, say $Q_{1},Q_{2},Q_{3}$. Then the tree induced by the edges in
$E(P_{2})\cup E(P_{3})\cup\\{zz^{\prime}\\}$ and the tree induced by the edges
in $E(Q_{1})\cup E(Q_{3})\cup\\{xx^{\prime},yy^{\prime}\\}$ are two internally
disjoint pendant $S$-Steiner trees in $G$, and hence $\tau(S)\geq 2$. Suppose
$z^{\prime}\in\\{x,y\\}$. Without loss of generality, let $y^{\prime}=z$.
Since $C_{p,1}$ is a cycle, it follows that there exists a vertex
$w\notin\\{x,y\\}$. Let $x^{\prime},w^{\prime}$ be the vertices in $C_{p,2}$
corresponding to $x,w$ in $C_{p,1}$, and let
$x^{\prime\prime},y^{\prime\prime},w^{\prime\prime}$ be the vertices in
$C_{p,3}$ corresponding to $x,y,w$ in $C_{p,1}$, respectively. Then the
vertices $x,y,w$ divide the cycle $C_{p,1}$ into three paths, say
$P_{1},P_{2},P_{3}$. Similarly, the vertices $x^{\prime},z,w^{\prime}$ divide
the cycle $C_{p,2}$ into three paths, say $Q_{1},Q_{2},Q_{3}$, and the
vertices $x^{\prime\prime},y^{\prime\prime},w^{\prime\prime}$ divide the cycle
$C_{p,3}$ into three paths, say $R_{1},R_{2},R_{3}$. Then the tree induced by
the edges in $E(P_{2})\cup E(P_{3})\cup E(Q_{2})\cup\\{ww^{\prime}\\}$ and the
tree induced by the edges in $E(Q_{1})\cup E(R_{1})\cup
E(R)\cup\\{xx^{\prime},x^{\prime}x^{\prime\prime}\\}$ are two internally
disjoint pendant $S$-Steiner trees in $G$, where $R$ is a path in some
$C_{j,q}$ connecting $y$ and $y^{\prime\prime}$, and hence $\tau(S)\geq 2$.

Suppose that there exist three cycles $C_{p,i},C_{p,j},C_{p,k}$ such that
$|S\cap V(C_{p,i})|=|S\cap V(C_{p,j})|=|S\cap V(C_{p,k})|=1$. Without loss of
generality, let $|S\cap V(C_{p,1})|=|S\cap V(C_{p,2})|=|S\cap V(C_{p,3})|=1$.
Let $y^{\prime},z^{\prime}$ be the vertices corresponding to $y,z$ in
$C_{p,1}$, $x^{\prime},z^{\prime\prime}$ be the vertices corresponding to
$x,z$ in $C_{p,2}$ and $x^{\prime\prime},y^{\prime\prime}$ be the vertices
corresponding to $x,y$ in $C_{p,3}$. If $x,y^{\prime},z^{\prime}$ are distinct
vertices in $C_{p,1}$, then the vertices $x,y^{\prime},z^{\prime}$ divide the
cycle $C_{p,1}$ into three paths $P_{1},P_{2},P_{3}$, and the vertices
$x^{\prime},y,z^{\prime\prime}$ divide the cycle $C_{p,2}$ into three paths
$Q_{1},Q_{2},Q_{3}$, and the vertices $x^{\prime\prime},y^{\prime\prime},z$
divide the cycle $C_{p,3}$ into three paths $R_{1},R_{2},R_{3}$. Then the tree
induced by the edges in $E(P_{1})\cup
E(P_{2})\cup\\{yy^{\prime},z^{\prime}z^{\prime\prime},zz^{\prime\prime}\\}$
and the tree induced by the edges in $E(Q_{1})\cup
E(R_{3})\cup\\{xx^{\prime},x^{\prime}x^{\prime\prime}\\}$ are two internally
disjoint pendant $S$-Steiner trees in $G$, and hence $\tau(S)\geq 2$. Suppose
that two of $x,y^{\prime},z^{\prime}$ are the same vertex in $C_{p,1}$.
Without loss of generality, let $x=y^{\prime}$. Since $C_{p,1}$ is a cycle, it
follows that there exists a vertex $v$ such that $v\notin\\{x,z^{\prime}\\}$.
Let $v^{\prime},v^{\prime\prime}$ be the vertices in $C_{p,2},C_{p,3}$
corresponding to $v$, respectively. Then the vertices $x,z^{\prime},v$ divide
the cycle $C_{p,1}$ into three paths $P_{1},P_{2},P_{3}$, and the vertices
$y,z^{\prime\prime},v^{\prime}$ divide the cycle $C_{p,2}$ into three paths
$Q_{1},Q_{2},Q_{3}$, and the vertices $x^{\prime\prime},z,v^{\prime\prime}$
divide the cycle $C_{p,3}$ into three paths $R_{1},R_{2},R_{3}$. Then the tree
induced by the edges in $E(P_{3})\cup E(Q_{3})\cup
E(R_{2})\cup\\{vv^{\prime},v^{\prime}v^{\prime\prime}\\}$ and the tree induced
by the edges in $E(P_{1})\cup
E(Q_{1})\cup\\{z^{\prime}z^{\prime\prime},zz^{\prime\prime}\\}$ are two
internally disjoint pendant $S$-Steiner trees in $G$, and hence $\tau(S)\geq
2$. Suppose that $x,y^{\prime},z^{\prime}$ are the same vertex in $C_{p,1}$.
Since $C_{p,1}$ is a cycle, it follows that there exists two verties $u,v$
such that $u\neq x$ and $v\neq x$. Let $u^{\prime},v^{\prime}$ be the vertices
in $C_{p,2}$ corresponding to $u,v$, respectively. Let
$u^{\prime\prime},v^{\prime\prime}$ be the vertices in $C_{p,3}$ corresponding
to $u,v$, respectively. Then the vertices $x,u,v$ divide the cycle $C_{p,1}$
into three paths $P_{1},P_{2},P_{3}$, and the vertices
$y,u^{\prime},v^{\prime}$ divide the cycle $C_{p,2}$ into three paths
$Q_{1},Q_{2},Q_{3}$, and the vertices $z,u^{\prime\prime},v^{\prime\prime}$
divide the cycle $C_{p,3}$ into three paths $R_{1},R_{2},R_{3}$. Then the tree
induced by the edges in $E(P_{1})\cup E(Q_{1})\cup
E(R_{1})\cup\\{uu^{\prime},u^{\prime}u^{\prime\prime}\\}$ and the tree induced
by the edges in $E(P_{3})\cup E(Q_{3})\cup
E(R_{3})\cup\\{vv^{\prime},v^{\prime}v^{\prime\prime}\\}$ are two internally
disjoint pendant $S$-Steiner trees in $G$, and hence $\tau(S)\geq 2$.

From the argument, we conclude that $\tau_{3}(G)=2$, and hence $f(n,3,2)\leq
2pq=2n$. From Proposition 2.1, $f(n,3,2)\geq 2n$. So $f(n,3,2)=2n$.

$(2)$ Let $G=W_{p}\Box P_{2}$. From Lemma 3.4, we have
$\delta(G)=\kappa(G)=4$. From Lemma 2.2, $\tau_{3}(G)\leq\delta(G)-k+1=2$. We
only need to show that $\tau_{3}(G)\geq 2$. It suffices to prove that
$\tau(S)\geq 2$ for any $S\subseteq V(G)$ and $|S|=3$. Let $S=\\{x,y,z\\}$.
Let $W_{p,1},W_{p,2}$ be the two wheels in $G$ corresponding to $W_{p}$.
Suppose $S\subseteq V(W_{p,i})$ where $i=1,2$. Without loss of generality, let
$S\subseteq V(W_{p,1})$. Let $x^{\prime},y^{\prime},z^{\prime}$ be the
vertices in $W_{p,2}$ corresponding to $x,y,z$ in $W_{p,1}$, respectively.
Since $\kappa(W_{p,1})=3$, it follows from Corollary 2.1 that
$\tau_{3}(W_{p,1})\geq 1$, and hence there exists a pendant $S$-Steiner tree
in $W_{p,1}$, say $T$. Let $T^{\prime}$ be the tree in $W_{p,2}$ corresponding
to $T$ in $W_{p,1}$. Then the tree induced by the edges in
$E(T^{\prime})\cup\\{xx^{\prime},yy^{\prime},zz^{\prime}\\}$ and the tree $T$
are two pendant $S$-Steiner trees in $G$. Then $\tau(S)\geq 2$. Suppose
$|S\cap V(W_{p,1})|=2$ or $|S\cap V(W_{p,2})|=2$. Without loss of generality,
let $|S\cap V(W_{p,1})|=2$. Then $|S\cap V(W_{p,2})|=1$. Let
$x^{\prime},y^{\prime}$ be the vertices in $W_{p,2}$ corresponding to $x,y$ in
$W_{p,1}$, and let $z^{\prime}$ be the vertex in $W_{p,1}$ corresponding to
$z$ in $W_{p,2}$. Let $w,w^{\prime}$ be the centers of the wheels
$W_{p,1},W_{p,2}$, respectively. Then the tree $T_{1}$ induced by the edges in
$\\{xw,yw,ww^{\prime},w^{\prime}z\\}$ is a pendant $S$-Steiner tree, and the
tree $T_{2}$ induced by the edges in $\\{xx^{\prime},yy^{\prime}\\}$ is a
pendant $S$-Steiner tree. Since $T_{1}$ and $T_{2}$ are disjoint, it follows
that $\tau(S)\geq 2$. From the arbitrariness of $S$, we have $\tau_{3}(G)\geq
2$, and hence $\tau_{3}(G)=2$. So $f(n,3,2)\leq 5p-4=\frac{5n-8}{2}$. From
Proposition 2.1, $f(n,3,2)\geq 2n$.

$(3)$ From $(2)$ of Theorem 1.1, if $n$ is a prime number, then $2n\leq
f(n,3,2)\leq 4n-16$.

For $k=3$ and general $\ell\ (3\leq\ell\leq\frac{n-4}{3})$, we give the upper
and lower bound of $f(n,3,\ell)$.

###### Proposition 3.3

Let $n,\ell$ be two integers with $3\leq\ell\leq\frac{n-4}{3}$ and $n\geq 15$.
Then

$\left\lceil\frac{(\ell+2)n}{2}\right\rceil\leq
f(n,3,\ell)\leq(\ell+1)(n-\ell)+1.$

Proof. Let $H=\ell K_{1}\vee C_{n-\ell}$. Set
$V(C_{n-\ell})=\\{y_{1},y_{2},\ldots,y_{n-\ell}\\}$. Let $G$ be a graph
obtained from $H$ by adding an edge $y_{1}y_{\lfloor\frac{n-\ell}{2}\rfloor}$.
Then $\delta(G)=\ell+2$. From Lemma 2.2, $\tau_{3}(G)\leq\delta(G)-2=\ell$. We
only need to show $\tau_{3}(G)\geq\ell$. Set
$X=V(G)-V(C_{n-\ell})=\\{x_{1},x_{2},\ldots,x_{\ell}\\}$. For any $S\subseteq
V(G)$ and $|S|=3$, it suffices to show $\tau(S)\geq\ell$. Suppose $S\subseteq
V(C_{n-\ell})$. Without loss of generality, let $S=\\{y_{1},y_{2},y_{3}\\}$.
Then the trees induced by the edges in
$\\{x_{i}y_{1},x_{i}y_{2},x_{i}y_{3}\\}\ (1\leq i\leq\ell)$ are $\ell$
internally disjoint pendant $S$-Steiner trees in $G$, and hence
$\tau(S)\geq\ell$. Suppose $S\subseteq X$. Without loss of generality, let
$S=\\{x_{1},x_{2},x_{3}\\}$. Then the trees induced by the edges in
$\\{y_{i}x_{1},y_{i}x_{2},y_{i}x_{3}\\}\ (1\leq i\leq n-\ell)$ are internally
disjoint $n-\ell\geq 2\ell+4$ pendant $S$-Steiner trees in $G$, and hence
$\tau(S)\geq\ell$. Suppose $|S\cap X|=2$. Then $|S\cap V(C_{n-\ell})|=1$.
Without loss of generality, let $S=\\{x_{1},x_{2},y_{1}\\}$. Then the trees
induced by the edges in $\\{y_{i}x_{1},y_{i}x_{2},x_{i}y_{i},x_{i}y_{1}\\}\
(3\leq i\leq\ell)$, the tree induced by the edges in
$\\{y_{2}x_{1},y_{2}x_{2},y_{2}y_{1}\\}$ and the tree induced by the edges in
$\\{y_{n-\ell}x_{1},y_{n-\ell}x_{2},y_{n-\ell}y_{1}\\}$ are $\ell$ internally
disjoint pendant $S$-Steiner trees in $G$, and hence $\tau(S)\geq\ell$.
Suppose $|S\cap X|=1$. Then $|S\cap V(C_{n-\ell})|=2$. Without loss of
generality, let $S=\\{x_{1},y_{i},y_{j}\\}$. If $1\leq
i<j\leq\lfloor\frac{n-\ell}{2}\rfloor$, then the trees induced by the edges in
$\\{x_{t}y_{\lfloor\frac{n-\ell}{2}\rfloor+t-1},y_{i}x_{t},y_{j}x_{t},x_{1}y_{\lfloor\frac{n-\ell}{2}\rfloor+t-1}\\}\
(2\leq t\leq\ell)$ and the tree induced by the edges in
$\\{y_{1}x_{\lfloor\frac{n-\ell}{2}\rfloor},x_{1}y_{1}\\}\cup\\{y_{r}y_{r+1}\,|\,1\leq
r\leq i-1\\}\cup\\{y_{s}y_{s+1}\,|\,j\leq
s\leq\lfloor\frac{n-\ell}{2}\rfloor-1\\}$ are $\ell$ internally disjoint
pendant $S$-Steiner trees in $G$, and hence $\tau(S)\geq\ell$. The same is
true for $\lfloor\frac{n-\ell}{2}\rfloor+1\leq i<j\leq n-\ell$. Suppose $1\leq
i\leq\lfloor\frac{n-\ell}{2}\rfloor$ and $\lfloor\frac{n-\ell}{2}\rfloor+1\leq
j\leq n-\ell$. Without loss of generality, let
$|j-i|\geq\lceil\frac{n-\ell}{2}\rceil$. Then the trees induced by the edges
in $\\{x_{t}y_{i+t},y_{i}x_{t},y_{j}x_{t},x_{1}y_{i+t}\\}\ (2\leq t\leq\ell)$
and the tree induced by the edges in
$\\{x_{1}y_{1}\\}\cup\\{y_{r}y_{r+1}\,|\,1\leq r\leq
i-1\\}\cup\\{y_{s}y_{s+1}\,|\,j\leq s\leq\lfloor\frac{n-\ell}{2}\rfloor-1\\}$
are $\ell$ internally disjoint pendant $S$-Steiner trees in $G$, and hence
$\tau(S)\geq\ell$. From the argument, we conclude that $\tau(S)\geq\ell$ for
any $S\subseteq V(G)$ and $|S|=3$. So $\tau_{3}(G)=\ell$ and hence
$f(n,3,\ell)\leq(\ell+1)(n-\ell)+1$.

###### Lemma 3.5

[29] Let $G$ be a connected graph of order $n\geq 6$. Let $k$ be an integer
with $3\leq k\leq n$. Then

$\tau_{k}(G)\leq\kappa(G)-k+2.$

For $k=3$ and general $\ell\ (\frac{n-4}{3}\leq\ell\leq\frac{n-r-2}{2})$, we
give the upper and lower bound of $f(n,3,\ell)$.

###### Proposition 3.4

Let $n,\ell$ be two integers with $\frac{n-4}{3}\leq\ell\leq\frac{n-r-2}{2}$
and $n\geq 15$, where $n\equiv r\ (mod\ \ell+1)$ and $r\geq 2$. Then

$\left\lceil\frac{(\ell+2)n}{2}\right\rceil\leq
f(n,3,\ell)\leq\left\lfloor\frac{n}{\ell+1}\right\rfloor(\ell+1)^{2}+(r+1)(\ell+1)+r-1.$

Proof. Let $F=P_{s}\circ(\ell+1)K_{1}$ where
$s=\lfloor\frac{n}{\ell+1}\rfloor$. Set $P_{s}=u_{1}u_{2}\ldots u_{s}$. Let
$V((\ell+1)K_{1})=\\{v_{1},v_{2}\ldots v_{\ell+1}\\}$. Let $G$ be the graph
obtained from $F$ by adding the vertices
$(u_{s+1},v_{1}),(u_{s+1},v_{2}),\ldots,(u_{s+1},v_{r})$ and the edges

$\displaystyle\\{(u_{s},v_{i})(u_{s+1},v_{j})\,|\,1\leq i\leq\ell+1,\ 1\leq
j\leq r\\}\cup\\{(u_{s+1},v_{j})(u_{s+1},v_{j+1})\,|\,1\leq j\leq r-1\\}$
$\displaystyle\cup\\{(u_{1},v_{j})(u_{1},v_{j+1})\,|\,1\leq j\leq\ell\\}.$

Clearly, $\kappa(G)=\ell+1$. From Lemma 3.5,
$\tau_{3}(G)\leq\kappa(G)-1=\ell$. We only need to show $\tau_{3}(G)\geq\ell$.
Let $H_{1},H_{2},\ldots,H_{s}$ be the copies corresponding to $(\ell+1)K_{1}$,
and let $H_{s+1}=\\{(u_{s+1},v_{j})\,|\,1\leq j\leq r\\}$. For any $S\subseteq
V(G)$ and $|S|=3$, it suffices to show $\tau(S)\geq\ell$. Let $S=\\{x,y,z\\}$.

Suppose that there exists some $H_{i}\ (1\leq i\leq s+1)$ such that $|S\cap
V(H_{i})|=3$. Without loss of generality, let $|S\cap V(H_{1})|=3$. Then the
trees induced by the edges in
$\\{x(u_{2},v_{i}),y(u_{2},v_{i}),z(u_{2},v_{i})\\}$ $(1\leq i\leq\ell+1)$ are
$\ell+1$ internally disjoint pendant $S$-Steiner trees in $G$, and hence
$\tau(S)\geq\ell+1$.

Suppose that there exist $H_{i},H_{j}$ such that $|S\cap V(H_{i})|=2$ and
$|S\cap V(H_{j})|=1$. Suppose $|j-i|\geq 2$. Note that the subgraph induced by
the vertices in $\\{(u_{r},v_{s})\,|\,i+1\leq r\leq j,\ 1\leq s\leq\ell+1\\}$
is $(\ell+1)$-connected. From Lemma 2.1, there exits a $(z,U)$-fan, where
$U=\\{(u_{i+1},v_{s})\,|\,1\leq s\leq\ell+1\\}$, and hence there is a path
connecting $z$ and $(u_{i+1},v_{s})$, say $P_{s}$, where $1\leq s\leq\ell+1$.
Then the trees induced by the edges in
$E(P_{s})\cup\\{(u_{i+1},v_{s})x,(u_{i+1},v_{s})y\\}$ are $\ell+1$ internally
disjoint pendant $S$-Steiner trees, and hence $\tau(S)\geq\ell+1$. Suppose
$|j-i|=1$. Without loss of generality, let $S\cap V(H_{1})=\\{x,y\\}$ and
$|S\cap V(H_{2})|=\\{z\\}$. Let $x^{\prime},y^{\prime}$ be the vertices
corresponding to $x,y$ in $H_{2}$, $z^{\prime}$ be the vertex corresponding to
$z$ in $H_{1}$. Suppose $z^{\prime}\not\in\\{x,y\\}$. Without loss of
generality, let $\\{x,y,z^{\prime}\\}=\\{(u_{1},v_{i})\,\,1\leq i\leq 3\\}$.
Then the tree induced by the edges in
$\\{xx^{\prime},yx^{\prime},x^{\prime}(u_{3},v_{1}),z(u_{3},v_{1})\\}$, the
tree induced by the edges in
$\\{xy^{\prime},yy^{\prime},y^{\prime}z^{\prime},z^{\prime}z\\}$ and the trees
induced by the edges in
$\\{x(u_{2},v_{j}),y(u_{2},v_{j}),(u_{1},v_{j})(u_{2},v_{j}),(u_{1},v_{j})z\\}\
(4\leq j\leq\ell+1)$ are $\ell$ internally disjoint pendant $S$-Steiner trees
in $G$, and hence $\tau(S)\geq\ell$. Suppose $z^{\prime}\in\\{x,y\\}$. Without
loss of generality, let $z^{\prime}=y$, $\\{x,y\\}=\\{(u_{1},v_{i})\,\,1\leq
i\leq 2\\}$. Then the tree induced by the edges in
$\\{xx^{\prime},yx^{\prime},x^{\prime}(u_{3},v_{1}),z(u_{3},v_{1})\\}$ and the
trees induced by the edges in
$\\{x(u_{2},v_{j}),y(u_{2},v_{j}),(u_{1},v_{j})(u_{2},v_{j}),(u_{1},v_{j})z\\}\
(3\leq j\leq\ell+1)$ are $\ell$ internally disjoint pendant $S$-Steiner trees
in $G$, and hence $\tau(S)\geq\ell$.

Suppose that there exist $H_{i},H_{j},H_{k}$ such that $|S\cap
V(H_{i})|=|S\cap V(H_{j})|=|S\cap V(H_{k})|=1$. Without loss of generality,
let $|S\cap V(H_{1})|=|S\cap V(H_{2})|=|S\cap V(H_{3})|=1$, and
$x=(u_{1},v_{1})$, $y=(u_{2},v_{1})$, $z=(u_{3},v_{1})$. Then the trees
induced by the edges in
$\\{x(u_{2},v_{j}),y(u_{2},v_{j}),(u_{1},v_{j})(u_{2},v_{j}),(u_{1},v_{j})z\\}\
(2\leq j\leq\ell+1)$ are $\ell$ internally disjoint pendant $S$-Steiner trees
in $G$, and hence $\tau(S)\geq\ell$.

From the above argument, we conclude that $\tau(S)\geq\ell$ for any
$S\subseteq V(G)$ and $|S|=3$. From the arbitrariness of $S$, we have
$\tau_{3}(G)\geq\ell$, and hence $\tau_{3}(G)=\ell$. So
$f(n,3,\ell)\leq\lfloor\frac{n}{\ell+1}\rfloor(\ell+1)^{2}+(r+1)(\ell+1)+r-1$.
From Proposition 2.1, $f(n,3,\ell)\geq\lceil\frac{(\ell+2)n}{2}\rceil$, as
desired.

The following result is from [28].

###### Lemma 3.6

[28] Let $G$ be a connected graph of order $n$. Then $\tau_{3}(G)=n-5$ if and
only if $\bar{G}$ is a subgraph of one of the following graphs.

  * •

$C_{i}\cup C_{j}\cup(n-i-j)K_{1}\ \ (i=3,4,\ j=3,4)$;

  * •

$C_{i}\cup\lfloor\frac{n-i}{2}\rfloor K_{2}\ \ (i=3,4)$;

  * •

$P_{5}\cup\lfloor\frac{n-5}{2}\rfloor K_{2}$;

  * •

$C_{i}\cup(n-i)K_{1}\ \ (i=5,6,7)$.

Proof of Theorem 1.3: From $(3)$ of Theorem 1.1, we have $f(n,3,0)=n-1$. From
$(4)$ of Theorem 1.1, we have $f(n,3,1)=\lceil\frac{3n}{2}\rceil$. From
Proposition 3.2, $f(n,3,2)=2n$ for $n=pq$ and $p,q\geq 3$; $2n\leq
f(n,3,2)\leq\frac{5n}{2}$ for $n=2p$; $2n\leq f(n,3,2)\leq 4n-16$ if $n$ is a
prime number. From Proposition 3.3, $\lceil\frac{(\ell+2)n}{2}\rceil\leq
f(n,3,\ell)\leq(\ell+1)(n-\ell)+1$ for $3\leq\ell\leq\frac{n-4}{3}$; From
Proposition 3.4, $\lceil\frac{(\ell+2)n}{2}\rceil\leq
f(n,3,\ell)\leq\lfloor\frac{n}{\ell+1}\rfloor(\ell+1)^{2}+(r+1)(\ell+1)+r-1$
for $\frac{n-1}{3}\leq\ell\leq\frac{n-r-2}{2}$ where $n\equiv r\ (mod\ \ell)$
and $r\geq 2$. From $(5)$ of Theorem 1.1, we have
$\lceil\frac{(\ell+2)n}{2}\rceil\leq f(n,3,\ell)\leq(\ell+2)(n-\ell-2)$ for
$\frac{n-1}{3}\leq\ell\leq\frac{n-r-2}{2}$ where $n\equiv r\ (mod\ \ell)$ and
$r=0,1$, or $\frac{n-r-2}{2}\leq\ell\leq\frac{n-4}{2}$. From $(6)$ of Theorem
1.1, we have $\left\lceil\frac{(\ell+2)n}{2}\right\rceil\leq
f(n,3,\ell)\leq(\ell+2)(n-\ell-2)+{\ell+2\choose 2}$ for
$\frac{n-2}{2}\leq\ell\leq n-6$. From Lemma , we have $f(n,3,n-5)={n\choose
2}-\lfloor\frac{n-4}{2}\rfloor$. From $(1)$ and $(2)$ of Theorem 1.1,
$f(n,3,n-4)={n\choose 2}-2$ and $f(n,3,n-3)={n\choose 2}$.

## References

  * [1] J.A. Bondy, U.S.R. Murty, _Graph Theory_ , GTM 244, Springer, 2008\.
  * [2] K. Day and A.-E. Al-Ayyoub, _The cross product of interconnection networks_ , IEEE Trans. Parallel and Distributed Systems 8(2)(1997), 109-118.
  * [3] S. Chang, _The uniqueness and nonuniqueness of the triangular association scheme_ , Sci. Record 3(1959), 604–613.
  * [4] G. Chartrand, S.F. Kappor, L. Lesniak, D.R. Lick, _Generalized connectivity in graphs_ , Bull. Bombay Math. Colloq. 2(1984), 1–6.
  * [5] G. Chartrand, F. Okamoto, P. Zhang, _Rainbow trees in graphs and generalized connectivity_ , Networks 55 (4) (2010), 360–367.
  * [6] G. Chartrand, M. Steeart, _The connectivity of line graphs_ , Math. Ann. 182(1969), 170–174.
  * [7] G.A. Dirac, _In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen_ , Math. Nach 22(1960), 61–85.
  * [8] D. Du, X. Hu, _Steiner tree problems in computer communication networks_ , World Scientific, 2008.
  * [9] P. Fragopoulou, S.G. Akl, _Edge-disjoint spanning trees on the star network with applications to fault tolerance_ , IEEE Trans. Computers 45(2)(1996), 174–185.
  * [10] M. Grötschel, _The Steiner tree packing problem in $VLSI$ design_, Math. Program. 78 (1997), 265–281.
  * [11] M. Grötschel, A. Martin, R. Weismantel, _Packing Steiner trees: A cutting plane algorithm and commputational results_ , Math. Program. 72 (1996), 125–145.
  * [12] M. Hager, _Pendant tree-connectivity_ , J. Combin. Theory 38 (1985), 179–189.
  * [13] S.M. Hedetniemi, S.T. Hedetniemi, A.L. Liestman, _A survey of gossiping and broadcasting in communication networks_ , Networks 18(1988), 1240–1268.
  * [14] A. Hoffman, _On the exeptional case in the characterization of the arcs of a complete graph_ , IBM J. Res. Dev. 4(1960), 487–496.
  * [15] P. Jalote, _Fault Tolerance in Distributed Systems_ , Prentice-Hall, Englewood Cliffs, NJ, 1994.
  * [16] K. Day, A.-E. Al-Ayyoub, _The Cross Product of Interconnec- tion Networks_ , IEEE Trans. Parallel and Distributed Systems 8(2)(1997), 109–118.
  * [17] S. Ku, B. Wang, T. Hung, _Constructing edge- disjoint spanning trees in product networks_ , Parallel and Distributed Systems, IEEE Transactions on parallel and disjoited systems 14(3)(2003), 213–221.
  * [18] H. Li, X. Li, Y. Mao, _On extremal graphs with at most two internally disjoint Steiner trees connecting any three vertices_ , Bull. Malays. Math. Sci. Soc. (2)37(3)(2014), 747–756.
  * [19] H. Li, X. Li, Y. Sun, _The generalied $3$-connectivity of Cartesian product graphs_, Discrete Math. Theor. Comput. Sci. 14 (1) (2012), 43–54.
  * [20] S. Li, X. Li, _Note on the hardness of generalized connectivity_ , J. Combin. Optimization 24 (2012), 389–396.
  * [21] S. Li, X. Li, W. Zhou, _Sharp bounds for the generalized connectivity $\kappa_{3}(G)$_, Discrete Math. 310 (2010), 2147–2163.
  * [22] X. Li, Y. Mao, Generalized Connectivity of Graphs, Springer Briefs in Mathematics, Springer, Switzerland, 2016.
  * [23] X. Li, Y. Mao, _On extremal graphs with at most $\ell$ internally disjoint Steiner trees connecting any $n-1$ vertices_, Graphs & Combin. 31(6)(2015), 2231–2259.
  * [24] X. Li, Y. Mao, _The generalied $3$-connectivity of lexigraphical product graphs_, Discrete Math. Theor. Comput. Sci. 16(1)(2014), 339–354.
  * [25] X. Li, Y. Mao, _Nordhaus-Gaddum-type results for the generalized edge-connectivity of graphs_ , Discrete Appl. Math. 185(2015), 102–112.
  * [26] X. Li, Y. Mao, _Graphs with large generalized (edge-)connectivity_ , accepted by Discuss. Math. Graph Theory, arXiv: 1305.1089 [math.CO] 2013.
  * [27] X. Li, Y. Mao, Y. Sun, _On the generalized (edge-)connectivity of graphs_ , Australasian J. Combin. 58(2)(2014), 304–319.
  * [28] Y. Mao, H. Lai, _On the pendant-tree connectivity of graphs_ , arXiv:1508.07149 [math.CO] 2015.
  * [29] Y. Mao, H. Lai, Graphs with given pendant-tree connectivity, submitted.
  * [30] O.R. Oellermann, _Connectivity and edge-connectivity in graphs: A survey_ , Congessus Numerantium 116 (1996), 231–252.
  * [31] O.R. Oellermann, _On the $\ell$-connectivity of a graph_, Graphs & Combin. 3(1987), 285–299.
  * [32] O.R. Oellermann, _A note on the $\ell$-connectivity function of a graph_, Congessus Numerantium 60 (1987), 181–188.
  * [33] F. Okamoto, P. Zhang, _The tree connectivity of regular complete bipartite graphs_ , J. Combin. Math. Combin. Comput. 74 (2010), 279–293.
  * [34] N.A. Sherwani, _Algorithms for $VLSI$ Physical Design Automation_, 3rd Edition, Kluwer Acad. Pub., London, 1999.
  * [35] S. S̆pacapan, _Connectivity of Cartesian products of graphs_ , Appl. Math. Lett. 21(2008), 682-685.
  * [36] P. Ramanathan, D.D. Kandlur, K.G. Shin, _Hardware-assisted software clock synchronization for homogeneous distributed systems_ , IEEE Trans. Comput. 39(1990), 514–524.
  * [37] D. West, _Introduction to Graph Theory (Second edition)_ , Prentice Hall, 2001.
  * [38] H. Whitney, _Congruent graphs and the connectivity of graph_ , Amer. J. Math. 54(1)(1932), 150–168.