11institutetext: Institut für Informatik, Universität Rostock, Rostock,
Germany
11email: {van-bang.le<EMAIL_ADDRESS>
# Computing Optimal Leaf Roots of Chordal Cographs in Linear Time

Van Bang Le  Christian Rosenke

###### Abstract

A graph $G$ is a _$k$ -leaf power_, for an integer $k\geq 2$, if there is a
tree $T$ with leaf set $V(G)$ such that, for all vertices $x,y\in V(G)$, the
edge $xy$ exists in $G$ if and only if the distance between $x$ and $y$ in $T$
is at most $k$. Such a tree $T$ is called a _$k$ -leaf root_ of $G$. The
computational problem of constructing a $k$-leaf root for a given graph $G$
and an integer $k$, if any, is motivated by the challenge from computational
biology to reconstruct phylogenetic trees. For fixed $k$, Lafond [SODA 2022]
recently solved this problem in polynomial time.

In this paper, we propose to study _optimal leaf roots_ of graphs $G$, that
is, the $k$-leaf roots of $G$ with _minimum_ $k$ value. Thus, all
$k^{\prime}$-leaf roots of $G$ satisfy $k\leq k^{\prime}$. In terms of
computational biology, seeking optimal leaf roots is more justified as they
yield more probable phylogenetic trees. Lafond’s result does not imply
polynomial-time computability of optimal leaf roots, because, even for optimal
$k$-leaf roots, $k$ may (exponentially) depend on the size of $G$. This paper
presents a linear-time construction of optimal leaf roots for chordal cographs
(also known as trivially perfect graphs). Additionally, it highlights the
importance of the parity of the parameter $k$ and provides a deeper insight
into the differences between optimal $k$-leaf roots of even versus odd $k$.

###### Keywords:

$k$-leaf power $k$-leaf root optimal $k$-leaf root trivially perfect leaf
power chordal cograph

##  1 Introduction

Leaf powers have been introduced by Nishimura, Ragde and Thilikos [12] to
model the phylogeny reconstruction problem from computational biology: given a
graph $G$ that represents a set of species with vertices $V(G)$ and the
interspecies similarity with edges $E(G)$, how can we reconstruct an
evolutionary tree $T$ with a given similarity threshold $k$? A _$k$ -leaf
root_ of $G$, a tree $T$ with species $V(G)$ as the leaf set and where species
$x,y\in V(G)$ have distance at most $k$ in $T$ if and only if they are similar
on account of $xy\in E(G)$, is considered a solution to this problem. In case
$T$ exists, the graph $G$ is called a _$k$ -leaf power_. The challenge of
finding a $k$-leaf root for given $G$ and $k$ has, yet, been modelled as the
_$k$ -leaf power recognition problem_: given $G$ and $k$, decide if $G$ has a
$k$-leaf root.

$v_{1}$$u_{1}$$u_{0}$$v_{2}$$v_{0}$$G$

$v_{1}$$u_{1}$$u_{0}$$v_{2}$$v_{0}$$T$

$v_{1}$$u_{1}$$u_{0}$$v_{2}$$v_{0}$$T^{\prime}$

Figure 1:  A graph $G$ (left), a $5$-leaf root $T$ of $G$ (middle), a $4$-leaf
root $T^{\prime}$ of $G$ (right).

For an example, see Figure 1 with the graph $G$ called _dart_. The
similarities between the five species can be explained with similarity
threshold $k=5$ using the $5$-leaf root $T$ and with $k=4$ by the $4$-leaf
root $T^{\prime}$, both depicted in Figure 1.

For a deeper discourse into the heavily studied field of $k$-leaf powers, the
reader is kindly referred to the survey [13]. Here, we just give a short
overview.

Lately, Eppstein and Havvaei [8] showed that $k$-leaf power recognition for
graphs $G$ with $n$ vertices can be solved in ${\cal O}(f(k,\omega)\cdot n)$
time with $f(k,\omega)$ exponential in $k$ and $\omega$, the clique number of
$G$. Quite simply put, they reduce $k$-leaf power recognition to the decision
of a certain monadic second order property in a graph derived from $G$ having
tree-width bounded by $k$ and $\omega$. Lafond’s even more recent algorithm
[10] solves $k$-leaf power recognition in ${\cal O}(n^{g(k)})$ time, where
$g(k)$ grows superexponentially with $k$. It applies sophisticated dynamic
programming on a tree decomposition of $G$ and exploits structural
redundancies in $G$. Observe that, for fixed $k$, the latter method runs in
polynomial time.

Before these advances, $k$-leaf power recognition had only been solved for all
fixed $k$ between $2$ and $6$. The $2$-leaf powers are exactly the graphs that
have just cliques as their connected components, which makes the problem
trivial. For $k=3$ (see [12] and [3]), $k=4$ (see [12] and [4]), $k=5$ (see
[5]) and $k=6$ (see [7]) individual algorithms have been developed, all
creating a certain (tree-) decomposition of the input graph $G$ and then
attempting to fit together candidate $k$-leaf roots for the components into
one $k$-leaf root for $G$.

A general controversial aspect of modelling the reconstruction of a
phylogenetic tree $T$ with the $k$-leaf power recognition problem is that $k$
is part of the input. In the biological context, the value of $k$ describes an
upper bound on the number of evolutionary events in $T$ that lie between two
similar species $x,y$, thus, species adjacent in the given graph $G$ by an
edge $xy$. Unlike the model suggests, biologists do not always have control
over the parameter $k$. Instead, phylogenetic trees $T$ with as few as
possible evolutionary events between all pairs of similar species are
preferred. That is because, in reality, a higher number of events between $x$
and $y$ makes a similarity between $x$ and $y$ less likely. Conversely, this
means that a $k$-leaf root of $G$ with a small parameter $k$ models a more
probable phylogenetic tree. This paper therefore proposes a subtle change in
perspective towards considering the following optimization problem.

Optimal Leaf Root (OLR) Instance: A graph $G$. Output: An _optimal leaf root_
$T$ of $G$, that is, a $\kappa$-leaf root of $G$ such that $\kappa\leq k$ for
all $k$-leaf roots of $G$, or No, if $T$ does not exist.

Subsequently, we use $\kappa$ to indicate that the respective $\kappa$-leaf
root is optimal. OLR is in a certain sense an optimization version of $k$-leaf
power recognition. The answer No states that the given graph $G$ is not a
$k$-leaf power for any $k$ and, in particular, not for the given one. Getting
an optimal $\kappa$-leaf root of $G$ helps to decide if $G$ is a $k$-leaf
power in many cases. A difficulty is that, for all $\kappa$ and $k$ of
different parity and with $2\leq\kappa<k<2\kappa-2$, there are $\kappa$-leaf
powers that are not $k$-leaf powers [14]. Then, checking $\kappa\leq k$ does
not decide correctly.

As for $k$-leaf power recognition, there are no known general efficient
solutions for OLR. If input was restricted to $k$-leaf powers with $k\leq K$
for some fixed $K$, we could repurpose Lafond’s algorithm. Testing a given $G$
with all $2\leq k\leq K$ would finally reveal the minimum $\kappa$ for which
$G$ is $\kappa$-leaf power. At that point, a $\kappa$-leaf root of $G$ could
also be extracted from the algorithm. But that classes of $k$-leaf powers have
not been characterized well for any $k\geq 5$ makes restricting input in the
proposed way difficult. Then again, it is unknown how to decide if a given
graph $G$ is a $k$-leaf power for any arbitrary $k$. And on top of that, the
minimum value $\kappa$ for which a given $G$ is a $\kappa$-leaf power, if any,
may exponentially depend on the size of $G$. This means that this brute force
searching may take exponentially or even infinitely many runs of Lafond’s
algorithm.

It is known that, independent of $k$, all $k$-leaf powers are strongly
chordal, but not vice versa. Ptolemaic graphs are strongly chordal and a
_class of unbounded leaf powers_. That is, there is no bound $\beta$ such that
every Ptolemaic graph has a $k$-leaf root for some $k\leq\beta$. Nevertheless,
every Ptolemaic graph on $n$ vertices has a $2n$-leaf root [1, 2]. Later,
Theorem 3.1 shows that, often, this is not optimal. This paper considers a
subclass of Ptolemaic graphs, the chordal cographs (also known as _trivially
perfect graphs_), as input to OLR. By definition, they form the intersection
of the well-known _chordal graphs_ and the _cographs_. Accordingly, they are
also characterized as the graphs without induced cycles on four vertices and
without induced paths on four vertices [9, 15, 16]. As a side effect of Lemma
8, this paper proves that chordal cographs are still a class of unbounded leaf
powers. This means that $k$-leaf power recognition on this class cannot be
solved in polynomial time with the algorithm of Lafond or the one of Eppstein
and Havvaei. Nevertheless, the following main result of our work states that
OLR can be solved in linear time for chordal cographs.

###### Theorem 1.1

Given a chordal cograph $G$ on $n$ vertices and $m$ edges, a (compressed)
$\kappa$-leaf root of $G$ with minimum $\kappa$ can be computed in ${\cal
O}(n+m)$ time.

To the best of our knowledge, chordal cographs are, thus, the first class of
unbounded leaf powers with a polynomial-time solution for OLR. The word
_compressed_ in Theorem 1.1 means that the $\kappa$-leaf root $T$ is returned
in a denser representation, where long paths of degree two-vertices are
compressed into single weighted edges. Otherwise, the size of $T$ alone would
be quadratic.

While, in general, an OLR-solution does not entirely work for $k$-leaf power
recognition, as elaborated above, our OLR-approach can also be used for
linear-time $k$-leaf power recognition on chordal cographs. The key to this is
the ability of our method to solve OLR with a given parity, such that the
computed $\kappa$-leaf root comes with the minimum $\kappa$ of the given
parity. Hence, if we choose the parity of the given $k$, we can tell that a
given graph $G$ is a $k$-leaf power if and only if the computed $\kappa$-leaf
root with $\kappa$ of the same parity as $k$ satisfies $\kappa\leq k$.

As the desired parity of $\kappa$ plays a certain role in our construction, we
research this discrepancy here, and show, for certain chordal cographs, that
the minimum $\kappa$ can differ up to 25 percent depending on if it is wanted
odd or even.

The next section presents basic notation, definitions, and facts on trees and
$k$-leaf powers used in this paper. The optimal leaf root construction method
for chordal cographs is introduced and proved correct in Section 3. Section 4
provides a respective linear-time implementation, thus, proving Theorem 1.1. A
deepened evaluation of the difference between chordal cographs with
$\kappa$-leaf roots of minimum odd versus even $\kappa$ is carried out in the
concluding Section 5.

To simplify the readability of the article, all proofs have been moved to
Section 6 at the end of the paper.

##  2 Preliminaries

All considered graphs are finite and without multiple edges or loops. Let
$G=(V,E)$ be a graph with vertex set $V(G)=V$ and edge set $E(G)=E$. A
_universal vertex_ in $G$ is one that is adjacent to all other vertices. If
all vertices of $G$ are universal than $G$ is _complete_. A vertex $x$ that is
adjacent to exactly one other vertex of $G$ is called a _leaf_ and the edge
containing $x$ is a _pendant edge_. Two adjacent vertices $x,y\in V(G)$ are
_true twins_ if $xz\in E(G)$, if and only if $yz\in E(G)$ for all $z\in
V(G)\setminus\\{x,y\\}$.

A graph $H$ is an _induced subgraph_ of $G$ if $V(H)\subseteq V(G)$ and $xy\in
E(H)$ if and only if $xy\in E(G)$ for all $x,y\in V(H)$. All subgraphs
considered in this paper are induced. For $X\subset V(G)$, $G-X$ denotes the
induced subgraph $H$ of $G$ with $V(H)=V(G)\setminus X$. If $X$ consists of
one vertex $x$ then we write $G-x$ for $G-\\{x\\}$. Complete subgraphs of $G$
are called _cliques_.

As usual, an _$x,y$ -path_ in $G$ is a sequence $v_{1},\dots,v_{n}$ of
distinct vertices from $V(G)$ such that $x=v_{1}$, $y=v_{n}$ and
$v_{i}v_{i+1}\in E(G)$ for all $i\in\\{1,\dots,n-1\\}$. An $x,y$-path is
called a _cycle_ in $G$ if $xy\in E(G)$. The length of the $x,y$-path,
respective cycle, is the number of its edges, that is, $n-1$ in the $x,y$-path
and $n$ in the cycle. If there is an $x,y$-path in $G$ for all distinct
$x,y\in V(G)$ then $G$ is _connected_. Otherwise, $G$ is _disconnected_ and,
therefore, composed of _connected components_ $G_{1},\dots,G_{n}$, maximal
induced subgraphs of $G$ that are connected. A connected component is _non-
trivial_ if it has more than one vertex and, otherwise, it is called _isolated
vertex_. We call $C\subseteq V(G)$ a _cut set_ if $G-C$ has more connected
components than $G$. If $C$ is just a single vertex $c$ then $c$ is a
_cutvertex_.

Graphs $G$ and $H$ are isomorphic if a bijection $\sigma:V(G)\rightarrow V(H)$
exists with $xy\in E(G)$ if and only if $\sigma(x)\sigma(y)\in E(H)$. If no
induced subgraph of $G$ is isomorphic to a graph $H$ then $G$ is $H$-_free_.
_Trees_ are the connected cycle-free graphs. This means, a tree $T$ contains
exactly one $x,y$-path for all $x,y\in V(T)$.

In this paper, we learn that, dependent on the given parity, the construction
of an optimal leaf root differs in several details. To avoid permanent case
distinctions, we use ${\mathrm{\pi}}(i)$ for the parity of an integer $i$,
that is, ${\mathrm{\pi}}(i)=i\mathrel{\text{mod}}2$.

###  2.1 Chordal Cographs and Cotrees

_Chordal cographs_ , ccgs for short, are known as the graphs that are free of
the path and the cycle on $4$ vertices. See the top row of Figure 2 for an
example ccg. One particular ccg used in this paper is the _star (with $t$
leaves)_, which consists of the vertices $u,v_{1},\dots,v_{t}$ for some $t\geq
2$ and the edges $uv_{1},\dots,uv_{t}$.

Like all cographs, ccgs can be represented with _cotrees_ [6]. The second row
of Figure 2 shows the cotree of the example cograph in the first row. For
every cograph $G$, the cotree $\cal T$ is a rooted tree with leaves $V(G)$ and
where every internal node is labelled with 0 for _disjoint union_ or 1 for
_full join_. In this way, the leaves define single vertex graphs and every
internal node represents the cograph $G$ combining the cographs
$H_{1},H_{2},\dots,H_{n}$ of its children with the respective graph operation.
More precisely, $V(G)=V(H_{1})\cup V(H_{2})\cup\dots\cup V(H_{n})$ and
$G=\leavevmode\hbox to8.34pt{\vbox
to8.34pt{\pgfpicture\makeatletter\hbox{\hskip 4.17046pt\lower-4.17046pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{3.97046pt}{0.0pt}\pgfsys@curveto{3.97046pt}{2.19284pt}{2.19284pt}{3.97046pt}{0.0pt}{3.97046pt}\pgfsys@curveto{-2.19284pt}{3.97046pt}{-3.97046pt}{2.19284pt}{-3.97046pt}{0.0pt}\pgfsys@curveto{-3.97046pt}{-2.19284pt}{-2.19284pt}{-3.97046pt}{0.0pt}{-3.97046pt}\pgfsys@curveto{2.19284pt}{-3.97046pt}{3.97046pt}{-2.19284pt}{3.97046pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\scriptsize 0}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(H_{1},H_{2},\dots,H_{n})$
means the disconnected cograph on vertex set $V(G)$ and edge set
$E(G)=E(H_{1})\cup E(H_{2})\cup\dots\cup E(H_{n})$ and $G=\leavevmode\hbox
to8.34pt{\vbox to8.34pt{\pgfpicture\makeatletter\hbox{\hskip
4.17046pt\lower-4.17046pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{3.97046pt}{0.0pt}\pgfsys@curveto{3.97046pt}{2.19284pt}{2.19284pt}{3.97046pt}{0.0pt}{3.97046pt}\pgfsys@curveto{-2.19284pt}{3.97046pt}{-3.97046pt}{2.19284pt}{-3.97046pt}{0.0pt}\pgfsys@curveto{-3.97046pt}{-2.19284pt}{-2.19284pt}{-3.97046pt}{0.0pt}{-3.97046pt}\pgfsys@curveto{2.19284pt}{-3.97046pt}{3.97046pt}{-2.19284pt}{3.97046pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\scriptsize 1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(H_{1},H_{2},\dots,H_{n})$
means the connected cograph with vertex set $V(G)$ and edge set
$E(G)=E(H_{1})\cup E(H_{2})\cup\dots\cup E(H_{n})\cup\\{xy\mid x\in
V(H_{i}),y\in V(H_{j}),1\leq i<j\leq n\\}$. The cotree $\cal T$ is unique, can
be constructed in linear time, and has the following properties:

  * •

Every internal node has at least two children.

  * •

No two internal nodes with the same label, 0 or 1, are adjacent.

  * •

The subtree ${\cal T}_{X}$ rooted at node $X$ is the cotree of the subgraph
$G_{X}$ induced by the leaves of ${\cal T}_{X}$. If $X$ is labelled with 0
then $G_{X}$ is the disjoint union of the cographs represented by the children
of $X$ and if it is labelled with 1 than $G_{X}$ is the full join of the
children cographs.

  * •

The cotree of an $n$-vertex cograph has at most $2n-1$ nodes.

We mostly work with ccgs without true twins, like $G$ in Figure 2. These
graphs have the following properties, as observed in the upper rows of the
figure.

###### Proposition 1

If $G$ is a ccg without true twins and ${\cal T}$ is the cotree of $G$ then
every node of ${\cal T}$ labelled with 1 has exactly two children, one leaf
and one node labelled with 0.

######  Proposition 2 (Wolk [15, 16])

Every connected ccg $G$ without true twins has a unique universal vertex $u$
and $G-u$ is disconnected (that is, $u$ is a cutvertex).

###  2.2 Diameter, Radius and Center in Trees

Let $T$ be a tree. The following notions are throughout used in the paper:

  * •

The _distance_ between two vertices $x$ and $y$ in $T$, written
${\mathrm{dist}}_{T}(x,y)$, is the length of the unique $x,y$-path in $T$.

  * •

The _diameter_ of $T$, denoted ${\mathrm{diam}}(T)$, is the maximum distance
between two vertices in $T$, that is,
${\mathrm{diam}}(T)=\max\\{{\mathrm{dist}}_{T}(x,y)\mid x,y\in V(T)\\}$.

  * •

A _diametral path_ in $T$ is a path of length ${\mathrm{diam}}(T)$.

  * •

A vertex $z$ is a _center vertex_ of $T$ if the maximum distance between $z$
and any other vertex in $T$ is minimum, that is, all $y\in V(T)$ satisfy
$\max\\{{\mathrm{dist}}_{T}(x,z)\mid x\in
V(T)\\}\leq\max\\{{\mathrm{dist}}_{T}(x,y)\mid x\in V(T)\\}$.

  * •

The _radius_ of $T$, denoted ${\mathrm{rad}}(T)$, is the maximum distance
between a center $z$ and other vertices of $T$, that is,
${\mathrm{rad}}(T)=\max\\{{\mathrm{dist}}_{T}(v,z)\mid v\in V(T)\\}$.

For convenience, we define
${\mathrm{\pi}}(T)={\mathrm{\pi}}({\mathrm{diam}}(T))$, the parity of the
diameter of $T$. It is well known for all trees $T$ that
${\mathrm{diam}}(T)=2\cdot{\mathrm{rad}}(T)-{\mathrm{\pi}}(T)$ and that there
is a single center vertex if ${\mathrm{\pi}}(T)=0$ and two adjacent centers if
${\mathrm{\pi}}(T)=1$. Furthermore, it is obvious for any diametral path in
$T$ that the end-vertices $x$ and $y$ are leaves and the center coincides with
the center of $T$. Thus, we have
$\min\\{{\mathrm{dist}}_{T}(z,x),{\mathrm{dist}}_{T}(z,y)\\}={\mathrm{rad}}(T)-{\mathrm{\pi}}(T)$
and
$\max\\{{\mathrm{dist}}_{T}(z,x),{\mathrm{dist}}_{T}(z,y)\\}={\mathrm{rad}}(T)$
for any center vertex $z$ of $T$.

We call a center vertex $z$ a _min-max center_ of $T$ if, for all center
vertices $z^{\prime}$ of $T$, $\min\\{{\mathrm{dist}}_{T}(z,v)\mid v\text{ is
a leaf of }T\\}\geq\min\\{{\mathrm{dist}}_{T}(z^{\prime},v)\mid v\text{ is a
leaf of }T\\}$. Thus, a min-max center maximizes the distance to the closest
leaf of $T$. For a min-max center $z$, the _leaf distance_ is
$d^{\mathrm{min}}_{T}=\min\\{{\mathrm{dist}}_{T}(z,v)\mid v\text{ is a leaf of
}T\\}$. The paper also needs the following technical lemma:

###### Lemma 1

If $T_{1},\dots,T_{s}$ are $s\geq 2$ trees with
${\mathrm{diam}}(T_{1})\geq\dots\geq{\mathrm{diam}}(T_{s})$ then

  1. (i)

${\mathrm{rad}}(T_{1})\geq{\mathrm{rad}}(T_{2})\geq\cdots\geq{\mathrm{rad}}(T_{s})$,

  2. (ii)

for all $1\leq i<j\leq s$, if ${\mathrm{rad}}(T_{i})={\mathrm{rad}}(T_{j})$
then ${\mathrm{\pi}}(T_{i})\leq{\mathrm{\pi}}(T_{j})$, and

  3. (iii)

for all $1\leq i<j\leq s$,
${\mathrm{rad}}(T_{i})-{\mathrm{\pi}}(T_{i})\geq{\mathrm{rad}}(T_{j})-{\mathrm{\pi}}(T_{j})$.

###  2.3 Leaf Powers, Leaf Roots and their Basic Properties

Let $k\geq 2$ be an integer. A graph $G$ is a _$k$ -leaf power_ if a _$k$
-leaf root_ $T$ of $G$ exists, a tree with leaves $V(G)$ such that $xy$ is an
edge in $G$ if and only if ${\mathrm{dist}}_{T}(x,y)\leq k$. The example $G$
in Figure 2 therefore is an $11$-leaf power because of the $11$-leaf root $T$
of $G$ in the third row and also a $12$-leaf power by the $12$-leaf root
$T^{\prime}$ in the bottom row. Note that Figure 2 shows _compressed_
illustrations of $T$ and $T^{\prime}$ where some long paths of vertices with
degree two are depicted by single weighted edges. It is well-known that

  * •

a complete graph is a $k$-leaf power for all $k\geq 2$,

  * •

a graph is a $k$-leaf power if and only if all of its connected components are
$k$-leaf powers, and

  * •

if $x,y$ are true twins in $G$ then $G$ is a $k$-leaf power if and only if
$G-x$ is a $k$-leaf power.

Note for the last fact that Lemma 7.3 and Corollary 7.4 in [11] imply the
possibility to identify and remove all true twins from a graph in linear time.
So, in the remainder of the paper, we smoothly focus on graphs without true
twins.

Since the concept of $k$-leaf powers is slightly different for odd and even
$k$, we formalize this discrepancy as follows: We say that a $k$-leaf root is
of _even_ , respectively _odd parity_ , if $k$ is even, respectively odd. A
$k$-leaf root $T$ of $G$ is an _optimal even_ , respectively _optimal odd_
leaf root if $k$ is even, respectively odd, and all $k^{\prime}$-leaf roots of
$G$ with $k^{\prime}$ of the same parity as $k$ satisfy $k\leq k^{\prime}$.
Finally, a $k$-leaf root $T$ of $G$ is (just) _optimal_ if $k\leq k^{\prime}$
for all $k^{\prime}$-leaf roots of $G$ (independent of parity). See the third
row of Figure 2 for an optimal odd leaf root $T$ of the example graph $G$ in
the same figure and see the bottom row for an optimal even leaf root
$T^{\prime}$ of $G$. Since $T$ is an $11$-leaf root and $T^{\prime}$ a
$12$-leaf root, it follows that $T$ is an optimal leaf root of $G$.

We conclude this section by establishing a few properties for leaf roots as
considered in this paper. The first one concerns a bound on the distance
between center and leaves in $T$ in case $G$ is connected.

###### Lemma 2

Every $k$-leaf root $T$ of a connected graph satisfies
$d^{\mathrm{min}}_{T}\leq\tfrac{k}{2}$.

See Figure 2 with the $11$-leaf root $T$ of $G$ having
$d^{\mathrm{min}}_{T}={\mathrm{dist}}_{T}(u_{0},z_{0})=2\leq\tfrac{11}{2}$ and
the $12$-leaf root $T^{\prime}$ with
$d^{\mathrm{min}}_{T^{\prime}}={\mathrm{dist}}_{T}(u_{0},z_{0})=2\leq\tfrac{12}{2}$.
Secondly, if $G$ has a universal vertex $u$ then the distance between $u$ and
the center in $T$ cannot exceed the difference between $k$ and the radius of
$T$.

###### Lemma 3

If $G$ is a non-complete graph with a universal vertex $u$ and $T$ is a
$k$-leaf root of $G$ then ${\mathrm{dist}}_{T}(u,z)\leq
k-{\mathrm{rad}}(T)+{\mathrm{\pi}}(T)$ for all center vertices $z$ of $T$. If
$z_{1}\not=z_{2}$ are the center vertices of $T$, then
${\mathrm{dist}}_{T}(u,z_{1})\leq k-{\mathrm{rad}}(T)$ or
${\mathrm{dist}}_{T}(u,z_{2})\leq k-{\mathrm{rad}}(T)$.

For an illustration, see Figure 2, where the distance of $u_{0}$ and the
farthest center vertex $z_{0}$ of $T$ satisfies
${\mathrm{dist}}_{T}(u_{0},z_{0})=2\leq
11-10+1=k-{\mathrm{rad}}(T)+{\mathrm{\pi}}(T)$ and, in $T^{\prime}$,
${\mathrm{dist}}_{T^{\prime}}(u_{0},z_{0})=2\leq
12-11+1=k^{\prime}-{\mathrm{rad}}(T^{\prime})+{\mathrm{\pi}}(T^{\prime})$.
Lemma 3 implies upper bounds on radius and diameter of $T$.

###### Corollary 1

If $G$ is a graph with a universal vertex and $T$ is a $k$-leaf root of $G$
then ${\mathrm{rad}}(T)\leq k-1$ and, in particular, ${\mathrm{diam}}(T)\leq
2k-2$.

As a matter of fact, $k$-leaf roots tend to contain long paths of vertices
with degree two. It is reasonable to _compress_ such a path
$P=v_{0},\dots,v_{n}$ into a single _weighted_ edge $v_{0}(n)v_{n}$. Clearly,
weighted edges $v_{0}(n)v_{n}$ add their weight $n$ to distances in $T$ and,
so, ${\mathrm{dist}}_{T}(v_{0},v_{n})=n$.

##  3 Optimal Leaf Root Construction for CCGs

Aim of this section is the development of an optimal leaf-root construction
approach for ccgs $G$. In very simple terms, we describe a divide and conquer
method that splits $G$ into smaller ccgs $G_{1},G_{2},\dots$, recursively
obtains their optimal leaf roots $T_{1},T_{2},\dots$, and then extends them
into an optimal leaf root for $G$.

We start with introducing two basic leaf root operations and analyze their
properties. The first operation, the _extension_ of trees, is used to level
the recursively found leaf roots $T_{1},T_{2},\dots$ on the same $k$, which is
essential for the subsequent composition into one $k$-leaf root. If $T$ is a
tree and $\delta\geq 0$ an integer then $T^{\prime}=\eta(T,\delta)$ is the
obtained from $T$ by subdividing every pendant edge $\delta$ times, that is,
replacing the edge with a new path of length $\delta+1$ (hence, of $\delta+1$
edges). The following property of this operation is well-known:

###### Lemma 4

If $T$ is a $k$-leaf root of a graph $G$ and $\delta\geq 0$ an integer then
$T^{\prime}=\eta(T,\delta)$ is a $(k+2\delta)$-leaf root of $G$ with same
center, same min-max center vertices, and
${\mathrm{diam}}(T^{\prime})={\mathrm{diam}}(T)+2\delta$,
${\mathrm{rad}}(T^{\prime})={\mathrm{rad}}(T)+\delta$,
$d^{\mathrm{min}}_{T^{\prime}}=d^{\mathrm{min}}_{T}+\delta$.

The second operation merges the individual $k$-leaf roots for the connected
components of a graph $G$ into one $k$-leaf root $T$ for the entire $G$. The
goal here is to minimize the diameter of $T$, which, in turn, allows making
optimizations to the value of $k$. Assume that $G$ has $s\geq 0$ non-trivial
connected components $G_{1},\dots,G_{s}$ and $t\geq 0$ isolated vertices
$v_{1},\dots,v_{t}$ such that $s+t\geq 2$ and let $T_{1},\dots,T_{s}$ be
$k$-leaf roots for $G_{1},\dots,G_{s}$ with min-max center vertices
$z_{1},\dots,z_{s}$. If $s>0$, we define the _critical index_ $m$ as the
smallest element of $\\{1,\dots,s\\}$ with
$d^{\mathrm{min}}_{T_{m}}=\min\\{d^{\mathrm{min}}_{T_{i}}\mid 1\leq i\leq
s\\}$ and call $T_{m}$ the _critical root_. Then, the _merging_
$\mu(k,T_{1},\dots,T_{s},v_{1},\dots,v_{t})$ results in the tree $T$ produced
by the following steps:

  1. 1.

Create a new vertex $c$.

  2. 2.

If $s>0$ then connect $c$ and the center $z_{m}$ of the critical root by a
path of length $\tfrac{k+{\mathrm{\pi}}(k)}{2}-d^{\mathrm{min}}_{T_{m}}$. If
${\mathrm{\pi}}(k)=0$ and $d^{\mathrm{min}}_{T_{m}}=\tfrac{1}{2}k$ then this
means to identify the vertices $c$ and $z_{m}$.

  3. 3.

For all $i\in\\{1,\dots,m-1,m+1,\dots,s\\}$, connect $c$ and $z_{i}$ by a path
of length $\tfrac{k-{\mathrm{\pi}}(k)}{2}+1-d^{\mathrm{min}}_{T_{i}}$.

  4. 4.

For all $j\in\\{1,\dots,t\\}$, connect $c$ and $v_{j}$ by a path of length
$\tfrac{k-{\mathrm{\pi}}(k)}{2}+1$.

Notice that the $\mu$-operation is sensitive with respect to the parity
${\mathrm{\pi}}(k)$. For one thing, this is necessary to guarantee that all
added paths are of integer length, which is done by in- or decreasing odd $k$.
As a side note, we point out that the lengths of added paths are also non-
negative by Lemma 2, which makes the $\mu$-operation well-defined. On the
other hand, the result is that merging works slightly different for odd and
even $k$. For odd $k$, all trees $T_{1},\dots,T_{s}$, including the critical
one, are essentially added in the same way by our construction method. This is
because, for odd $k$,
$\tfrac{k+{\mathrm{\pi}}(k)}{2}-d^{\mathrm{min}}_{T_{m}}=\tfrac{k-{\mathrm{\pi}}(k)}{2}+1-d^{\mathrm{min}}_{T_{m}}$.
The special treatment of the critical root, thus, has an effect only if $k$ is
even. Specifically in that case, we can sometimes save one in the diameter of
$T$, if we put the critical root closer to the center of $T$ than the rest.
The reason that this optimization works is that, usually, the critical root
has the largest diameter.

###### Lemma 5

Let $G$ be a graph and $k\geq 2$ an integer. If $G$ is disconnected with
$s\geq 0$ non-trivial connected components $G_{1},\dots,G_{s}$ and $t\geq 0$
isolated vertices $v_{1},\dots,v_{t}$ such that $s+t\geq 2$ and if
$T_{1},\dots,T_{s}$ are $k$-leaf roots for $G_{1},\dots,G_{s}$ then
$T=\mu(k,T_{1},\dots,T_{s},v_{1},\dots,v_{t})$ is a $k$-leaf root of $G$.

The two operations above simplify the description of the following leaf root
construction algorithm for ccgs since they hide away many of the technical
details. Foundation of the proposed recursive approach is that (i) induced
subgraphs of ccgs are ccgs and (ii) every connected ccg without true twins has
a unique universal cut vertex (see Proposition 2). Also, recall from Section
2.3 that true twins in graphs can be removed in linear time and, thus, be
safely ignored. Therefore, we define for all ccgs $G$ without true twins and a
given parity $p\in\\{0,1\\}$ the result of the _root operation_ $\rho(G,p)$ as
the tree $T$ and the number $k$ produced by the following (recursive)
procedure:

  1. i.

If $G$ is a star then let $u$ be the central vertex and $v_{1},\dots,v_{t}$
the leaves of $G$ (with $t\geq 2$ because $G$ does not have true twins)

    1. 1.

If $p=1$ (for odd) then let $T^{\prime}=\eta(G,1)$, obtain $T$ by attaching a
new leaf to $u$ in $T^{\prime}$, and return $(T,3)$.

    2. 2.

If $p=0$ (for even) and $t=2$ then return $(T,4)$ with $T$ obtained from a
single vertex $v$ by attaching the leaves $u,v_{1}$ and $v_{2}$ to $v$ with
paths of lengths one, two and three, respectively.

    3. 3.

If $p=0$ and $t>2$ then let $T^{\prime}=\eta(G,2)$, obtain $T$ by attaching a
new leaf to $u$ in $T^{\prime}$, and return $(T,4)$.

  2. ii.

else if $G$ is a connected graph then let $u$ be the universal cut vertex of
$G$ (by Proposition 2) and let $G_{1},\dots,G_{s}$ be the $s\geq 1$ non-
trivial connected components and $v_{1},\dots,v_{t}$ the $t\geq 0$ isolated
vertices of $G-u$.

    1. 1.

Recursively find
$(T_{1},k_{1})=\rho(G_{1},p),\dots,(T_{s},k_{s})=\rho(G_{s},p)$.

    2. 2.

If $s=1$ then let $k=k_{1}+2(1-{\mathrm{\pi}}(T_{1}))$. Otherwise, let

$\begin{aligned} k_{a}&=\max\\{k_{1},\dots,k_{s}\\},\\\
k_{b}&=\max\\{k_{i}\mid 1\leq i\leq s,i\not=a\\}\text{ and, if }s>2\text{
let}\\\ k_{c}&=\max\\{k_{i}\mid 1\leq i\leq
s,i\not=a,i\not=b\\}.\end{aligned}$

If $p=1$ (for odd) then let
$k=k_{a}+k_{b}-1-2\cdot{\mathrm{\pi}}(T_{a})\cdot{\mathrm{\pi}}(T_{b})$ and,
otherwise,

$k=\begin{cases}k_{a}+k_{b}-2\cdot({\mathrm{\pi}}(T_{a})+{\mathrm{\pi}}(T_{b})-{\mathrm{\pi}}(T_{a})\cdot{\mathrm{\pi}}(T_{b})),&\text{if
}s=2\text{ or }k_{a}>k_{c}\\\
k_{a}+k_{b}-2\cdot{\mathrm{\pi}}(T_{a})\cdot{\mathrm{\pi}}(T_{b}),&\text{otherwise.}\end{cases}$

    3. 3.

Get the extended leaf root
$T^{\prime}_{i}=\eta\left(T_{i},\tfrac{k-k_{i}}{2}\right)$ for all
$i\in\\{1,\dots,s\\}$ and let
$T^{\prime}=\mu(k,T^{\prime}_{1},\dots,T^{\prime}_{s},v_{1},\dots,v_{t})$.

    4. 4.

Return $(T,k)$ with $T$ obtained from $T^{\prime}$ by attaching the leaf $u$
to a center vertex of $T^{\prime}$.

  3. iii.

else $G$ is a disconnected graph and then let $G_{1},\dots,G_{s}$ be the
$s\geq 0$ non-trivial connected components and $v_{1},\dots,v_{t}$ the $t\geq
0$ isolated vertices of $G$.

    1. 1.

Recursively find
$(T_{1},k_{1})=\rho(G_{1},p),\dots,(T_{s},k_{s})=\rho(G_{s},p)$.

    2. 2.

Let $k=\max\\{k_{1},\dots,k_{s},p+2\\}$ and let
$T^{\prime}_{i}=\eta\left(T_{i},\tfrac{k-k_{i}}{2}\right)$ for all
$i\in\\{1,\dots,s\\}$.

    3. 3.

Return $(T,k)$ with
$T=\mu(k,T^{\prime}_{1},\dots,T^{\prime}_{s},v_{1},\dots,v_{t})$.

$u_{0}$$u_{1}$$u_{2}$$u_{3}$$u_{4}$$u_{5}$$u_{6}$$u_{7}$$u_{8}$$u_{9}$$v_{0}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$$v_{8}$$v_{9}$$v_{10}$$v_{11}$$v_{12}$$v_{13}$$v_{14}$$G$$G_{1}$$G_{2}$$G_{3}$$G_{4}$$G_{5}$$G_{6}$$G_{7}$$G_{8}$$G_{9}$

01010101010101010101$u_{0}$$u_{1}$$u_{3}$$u_{4}$$u_{5}$$u_{6}$$u_{7}$$u_{8}$$u_{9}$$u_{2}$$v_{0}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$$v_{8}$$v_{9}$$v_{10}$$v_{11}$$v_{12}$$v_{13}$$v_{14}$$v_{1}$${\cal
T}$${\cal T}_{1}$${\cal T}_{2}$${\cal T}_{3}$${\cal T}_{4}$${\cal
T}_{5}$${\cal T}_{6}$${\cal T}_{7}$${\cal T}_{8}$${\cal T}_{9}$

$6$$z_{0}$$3$$z_{1}$$4$$z_{2}$$6$$4$$z_{3}$$5$$6$$6$$6$$z_{4}$$5$$6$$6$$z_{5}$$5$$6$$6$$z_{6}$$5$$6$$6$$z_{7}$$5$$6$$6$$z_{8}$$5$$6$$6$$z_{9}$$u_{0}$$u_{1}$$u_{2}$$u_{3}$$u_{4}$$u_{5}$$u_{6}$$u_{7}$$u_{8}$$u_{9}$$v_{0}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$$v_{8}$$v_{9}$$v_{10}$$v_{11}$$v_{12}$$v_{13}$$v_{14}$$T$$T_{1}$$T_{2}$$T_{3}$$T_{4}$$T_{5}$$T_{6}$$T_{7}$$T_{8}$$T_{9}$

$7$$z_{0}$$3$$z_{1}$$4$$7$$5$$5$$7$$7$$7$$z_{4}$$5$$6$$6$$z_{5}$$5$$6$$6$$z_{2},z_{6}$$5$$6$$6$$z_{7}$$5$$6$$6$$z_{8}$$5$$6$$6$$z_{3},z_{9}$$u_{0}$$u_{1}$$u_{2}$$u_{3}$$u_{4}$$u_{5}$$u_{6}$$u_{7}$$u_{8}$$u_{9}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$$v_{8}$$v_{9}$$v_{10}$$v_{11}$$v_{12}$$v_{13}$$v_{14}$$v_{0}$$v_{1}$$T^{\prime}$$T^{\prime}_{1}$$T^{\prime}_{2}$$T^{\prime}_{3}$$T^{\prime}_{4}$$T^{\prime}_{5}$$T^{\prime}_{6}$$T^{\prime}_{7}$$T^{\prime}_{8}$$T^{\prime}_{9}$

Figure 2: A ccg $G$ (top), the cotree ${\cal T}$ of $G$ (2nd row), an optimal
(odd) $11$-leaf root $T$ of $G$ (3rd row) as computed by Algorithm 1 (with
input $p=1$), and an optimal even $12$-leaf root $T^{\prime}$ of $G$ (bottom)
as computed by Algorithm 1 with input $p=0$.

Hence, if the input graph $G$ is not a star then the approach is to firstly
divide $G$ into smaller connected subgraphs $G_{1},\dots,G_{s}$ (and isolated
vertices $v_{1},\dots,v_{t}$), secondly find corresponding $k$-leaf roots
$T_{1},\dots,T_{s}$ by recursion and the $\eta$-operation, and, last, conquer
by merging them into a single leaf root of $G$ with the $\mu$-operation. The
divide-step is simple for disconnected $G$ and, otherwise, is carried out by
removing the unique universal (cutvertex) of $G$.

The $\rho$-operation is sensitive to the given parity $p$ for using $\mu$ as a
subroutine. Observe that $p$ also decides how the resulting $k$ is determined.
There are four cases when $G$ is connected and not a star. In the first one,
when $s=1$, the construction is the same for odd and even $p$ and consists of
adding $u,v_{1},\dots,v_{t}$ at the correct distance to the center of $T_{1}$
and computing $k$ from $k_{1}$. Secondly, if $s>1$ and $p=1$, the
$\mu$-operation has only one way of merging the recursively found leaf roots
$T_{1},\dots,T_{s}$ to minimize the diameter of the result $T$. Then, $k$
widely depends on the two largest values of $k_{1},\dots,k_{s}$. But if $p=0$,
there is one situation that, on the one hand, allows $\mu$ to use a smaller
diameter for $T$ by prioritizing the critical leaf root and, on the other
hand, lets $\rho$ return a slightly better value for $k$. This happens only
when $s=2$, or whenever the $k_{c}$-leaf root, with $k_{c}$ the third-largest
value among $k_{1},\dots,k_{s}$, properly fits into the diametral space of $T$
that is already required for the $k_{a}$-leaf root and the $k_{b}$-leaf root.

The third and bottom row of Figure 2 illustrate the results $(T,11)$ of
$\rho(G,1)$ and $(T^{\prime},12)$ of $\rho(G,0)$ on the example $G$. By
recursion, both are produced bottom-up, and it is difficult to follow their
assembly at the deeper recursion levels. The highest recursion level of
$\rho(G,1)$, however, has received a $7$-leaf root with odd diameter for
subgraph $G_{1}$ and a $5$-leaf root with even diameter for $G_{2}$ in Step
(ii.ii.1.). In Step (ii.ii.2.), the $\rho$-procedure determines
$k=k_{1}+k_{2}-1=11$. The extension of the trees in Step (ii.ii.3.) produces
the $11$-leaf roots $T_{1}$ and $T_{2}$ for $G_{1}$ and $G_{2}$, respectively,
as shown in Figure 2. Their following merging and the attachment of $u_{0}$ in
Step (ii.ii.4.) produces the shown $11$-leaf root $T$ of $G$. Similarly,
$\rho(G,0)$ receives an odd-diameter $8$-leaf root of $G_{1}$ and an even-
diameter $6$-leaf root of $G_{2}$. Since $s=2$, the critical root can be
treated in the special way and, thus, $\rho(G,0)$ determines
$k^{\prime}=k^{\prime}_{1}+k^{\prime}_{2}-2=12$. After the extension, we get
the $12$-leaf roots $T^{\prime}_{1}$ for $G_{1}$ and $T^{\prime}_{2}$ for
$G_{2}$ as in Figure 2. Their merging and the attachment of $u_{0}$ yields the
$12$-leaf root $T^{\prime}$ of $G$ as also illustrated there.

The following statement regards the correctness of our procedure.

###### Theorem 3.1

Let $G$ be a ccg on $n$ vertices and without true twins and let
$p\in\\{0,1\\}$. Then $(T,k)=\rho(G,p)$ provides a $k$-leaf root $T$ of $G$
that is optimal for parity $p$ (hence, ${\mathrm{\pi}}(k)=p$) and with $k\leq
n+1$. If $G$ is connected then

(T1)

${\mathrm{rad}}(T)=k-1$,

(T2)

$d^{\mathrm{min}}_{T}=1+{\mathrm{\pi}}(T)$, and

(T3)

${\mathrm{diam}}(T^{\prime})\geq{\mathrm{diam}}(T)+k^{\prime}-k$ for all
$k^{\prime}$-leaf roots $T^{\prime}$ of $G$ with
${\mathrm{\pi}}(k^{\prime})=p$.

Note that, with respect to the optimality of the result, the theorem above
makes a slightly stronger statement than our main result in Theorem 1.1. In
fact, the $\rho$-operation can find a $\kappa$-leaf root with minimum $\kappa$
for every ccg $G$ simply by choosing the best from $(T,k)=\rho(G,1)$ and
$(T^{\prime},k^{\prime})=\rho(G,0)$. To prove Theorem 1.1, the next section
shows how to implement the $\rho$-operation in linear time.

##  4 Linear Time Leaf Root Construction for CCGs

The algorithm in this section is an implementation of the $\rho$-operation
from Section 3. Here, the recursive subdivision of the input ccg $G$ is
replaced with a post-order iteration of the cotree of $G$. But before we go
into the details, we analyze the used submodules and show that the operations
$\eta$ and $\mu$ run efficiently.

###### Lemma 6

Let $T$ be a compressed tree with $n$ leaves and with explicitly given min-max
center $z$, center $Z$, diameter ${\mathrm{diam}}(T)$, and leaf-distance
$d^{\mathrm{min}}_{T}$. For all integers $\delta\geq 0$, the compressed tree
$T^{\prime}=\eta(T,\delta)$ with min-max center $z^{\prime}$, center
$Z^{\prime}$, diameter ${\mathrm{diam}}(T^{\prime})$, and leaf distance
$d^{\mathrm{min}}_{T^{\prime}}$ can be computed in ${\cal O}(n)$ time.

###### Lemma 7

Let $s\geq 0$ be an integer and, for all $i\in\\{1,\dots,s\\}$, let $T_{i}$ be
a given, compressed tree with explicitly given min-max center $z_{i}$, center
$Z_{i}$, diameter ${\mathrm{diam}}(T_{i})$, and leaf-distance
$d^{\mathrm{min}}_{T_{i}}$. For all integers $k\geq 2$ and vertices
$v_{1},\dots,v_{t}$, the merged compressed tree
$T^{\prime}=\mu(k,T_{1},\dots,T_{s},v_{1},\dots,v_{t})$ with center
$Z^{\prime}$ and diameter ${\mathrm{diam}}(T^{\prime})$ can be computed in
${\cal O}(s+t)$ time.

The recursive definition of $\rho(G,p)$ is implemented as an iterative
traversal of the cotree of $G$. We observe that connected and disconnected
graphs $G$ can easily be distinguished with the cotree of $G$; the former have
a root labelled by 1 and the latter by 0. Likewise, we detect small input
graphs, stars, with the cotree by checking if the root is labelled with 1 and
if the only child that is labelled with 0 has just leaf-children.

Recall that, for connected graphs $G$ of sufficient size, the $\rho$-operation
divides $G$ at the unique universal vertex $u$, to recurse into the non-
trivial connected components $G_{1},\dots,G_{s}$ of $G-u$, and to conquer by
merging the according leaf roots $T_{1},\dots,T_{s}$ into a parity-optimal
solution for $G$. This divide-and-conquer procedure is translated into a
traversal of the cotree ${\cal T}$ as follows. Since input consists of ccgs
without true twins, we rely on Proposition 1. That means that nodes with the
label 1, like the root $X$ of ${\cal T}$, always have exactly one leaf-child,
say $u$, and one child with label 0, say $Y$. The leaf $u$ marks the unique
universal vertex in $G$ and $Y$ has children $Z_{1},\dots,Z_{s}$ with label 1
and leaf-children $v_{1},\dots v_{t}$ that represent the non-trivial connected
components $G_{1},\dots,G_{s}$ and the isolated vertices $v_{1},\dots,v_{t}$
of $G-u$. The chosen post-order traversal of ${\cal T}$ makes sure that,
before processing $X$ (and $Y$), the nodes $Z_{1},\dots,Z_{s}$ have been
visited and finished. Because we use a stack to pass interim results upwards,
we always find leaf roots $T_{1},\dots,T_{s}$ for $G_{1},\dots,G_{s}$ on the
stack (in reverse order), when we need to compute a leaf root $T$ for the
subgraph that corresponds to ${\cal T}_{X}$.

We present the details of our construction in Algorithm 1: OptimalLeafRoot and
summarize our results in the following theorem.

###### Theorem 4.1

Given a chordal cograph $G$ on $n$ vertices and $m$ edges and $p\in\\{0,1\\}$,
a (compressed) $\kappa$-leaf root of $G$ with minimum integer $\kappa$ of
parity $p$ can be computed in ${\cal O}(n+m)$ time.

Input: A ccg $G=(V,E)$ without true twins and a parity $p\in\\{0,1\\}$

Output: A pair $(T,k)$ of a $k$-leaf root $T$ of $G$ with smallest $p$-parity
integer $k$.

1

2initialize empty stack ${\cal S}$ and compute the cotree ${\cal T}$ of $G$

3 foreach  _node $X$ visited traversing ${\cal T}$ in post-order_ do

4 if  _$X$ is labelled with 1_ then

5 let $Y$ be the 0-child and $u$ the leaf-child of $X$

6 let $s$ be the number of 1-children and $v_{1},\dots,v_{t}$ the leaf-
children of $Y$

7 if  _$s=0$_ then // Case i., base case, input is a star

8 build $T$ like Case i., Section 3 for star on edges $uv_{1},\dots,uv_{t}$

9 push $(T,4-p)$ onto ${\cal S}$

10

11 else // Case ii., input is a connected graph

12 foreach  _$i\in\\{s,s-1,\dots,1\\}$_ do pop $(T_{i},k_{i})$ from ${\cal S}$

13 if  _$s=1$_ then $k\leftarrow k_{1}+2(1-{\mathrm{\pi}}(T_{1}))$

14 else

15 $k_{a}\leftarrow\max\\{k_{1},\dots,k_{s}\\}$

16 $k_{b}\leftarrow\max\\{k_{i}\mid 1\leq i\leq s,i\not=a\\}$

17 if  _$p=1$_ then $k\leftarrow
k_{a}+k_{b}-1-2\cdot{\mathrm{\pi}}(T_{a})\cdot{\mathrm{\pi}}(T_{b})$

18 else

19 if  _$s >2$ and $k_{a}>\max\\{k_{i}\mid 1\leq i\leq s,i\not=a,i\not=b\\}$_
then

20 $k\leftarrow
k_{a}+k_{b}-2\cdot{\mathrm{\pi}}(T_{a})\cdot{\mathrm{\pi}}(T_{b})$

21

22 else $k\leftarrow
k_{a}+k_{b}-2\cdot({\mathrm{\pi}}(T_{a})+{\mathrm{\pi}}(T_{b})-{\mathrm{\pi}}(T_{a})\cdot{\mathrm{\pi}}(T_{b}))$

23

24 end if

25

26 end if

27 foreach  _$i\in\\{1,\dots,s\\}$_ do
$T^{\prime}_{i}\leftarrow\eta(T_{i},(k-k_{i})/2)$

28 $T\leftarrow\mu(k,T^{\prime}_{1},\dots,T^{\prime}_{s},v_{1},\dots,v_{t})$
with $\leftarrow$ a center of $T$

29 attach $u$ as a leaf to a center of $T$

30 push $(T,k)$ onto ${\cal S}$

31

32 end if

33

34 end if

35 if  _$X$ is 0-node without parent_ then // Case iii., disconnected input

36 let $s$ be the number of 1-children and $v_{1},\dots,v_{t}$ the leaf-
children of $X$

37 foreach  _$i\in\\{1,\dots,s\\}$_ do pop $(T_{i},k_{i})$ from ${\cal S}$

38 $k\leftarrow\max\\{k_{1},\dots,k_{s},p+2\\}$

39 foreach  _$i\in\\{s,s-1,\dots,1\\}$_ do
$T^{\prime}_{i}\leftarrow\eta(T_{i},(k-k_{i})/2)$

40 $T\leftarrow\mu(k,T^{\prime}_{1},\dots,T^{\prime}_{s},v_{1},\dots,v_{t})$

41 push $(T,k)$ onto ${\cal S}$

42

43 end if

44 pop $(T,k)$ from ${\cal S}$

45 return $(T,k)$

46

47 end foreach

Algorithm 1 OptimalLeafRoot

##  5 Conclusion

With Theorem 4.1, we have shown that the OLR problem is linear-time solvable
for chordal cographs. Our work also provides a linear-time solution for the
$k$-leaf power recognition problem on chordal cographs. Specifically, for a
given ccg $G$ and an integer $k$, it is sufficient to compute
$(T,\kappa)=\rho(G,{\mathrm{\pi}}(k))$ (in linear time with Algorithm 1) to
see by $\kappa\leq k$ if $G$ is a $k$-leaf power.

We conclude the paper by exploring the differences in the construction of odd
and even leaf-roots. As we have seen, merging three or more even leaf roots
sometimes requires a slightly stronger increase in $k$ than for odd leaf
roots. This can accumulate to an arbitrary big gap between $k$ and
$k^{\prime}$ of an optimal odd $k$-leaf root and an optimal even
$k^{\prime}$-leaf root of a given ccg. For example, consider the (infinite)
series $F_{1},F_{2},F_{3},\dots,F_{i},\dots$ of ccgs defined as follows. Let
$F_{0}$ be the path on three vertices and for all integers $i>0$ define

$F_{i}=t_{i}\ \leavevmode\hbox to8.34pt{\vbox
to8.34pt{\pgfpicture\makeatletter\hbox{\hskip 4.17046pt\lower-4.17046pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{3.97046pt}{0.0pt}\pgfsys@curveto{3.97046pt}{2.19284pt}{2.19284pt}{3.97046pt}{0.0pt}{3.97046pt}\pgfsys@curveto{-2.19284pt}{3.97046pt}{-3.97046pt}{2.19284pt}{-3.97046pt}{0.0pt}\pgfsys@curveto{-3.97046pt}{-2.19284pt}{-2.19284pt}{-3.97046pt}{0.0pt}{-3.97046pt}\pgfsys@curveto{2.19284pt}{-3.97046pt}{3.97046pt}{-2.19284pt}{3.97046pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\scriptsize 1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\ ((x_{i}\
\leavevmode\hbox to8.34pt{\vbox to8.34pt{\pgfpicture\makeatletter\hbox{\hskip
4.17046pt\lower-4.17046pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{3.97046pt}{0.0pt}\pgfsys@curveto{3.97046pt}{2.19284pt}{2.19284pt}{3.97046pt}{0.0pt}{3.97046pt}\pgfsys@curveto{-2.19284pt}{3.97046pt}{-3.97046pt}{2.19284pt}{-3.97046pt}{0.0pt}\pgfsys@curveto{-3.97046pt}{-2.19284pt}{-2.19284pt}{-3.97046pt}{0.0pt}{-3.97046pt}\pgfsys@curveto{2.19284pt}{-3.97046pt}{3.97046pt}{-2.19284pt}{3.97046pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\scriptsize 1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\ (F_{i-1}\
\leavevmode\hbox to8.34pt{\vbox to8.34pt{\pgfpicture\makeatletter\hbox{\hskip
4.17046pt\lower-4.17046pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{3.97046pt}{0.0pt}\pgfsys@curveto{3.97046pt}{2.19284pt}{2.19284pt}{3.97046pt}{0.0pt}{3.97046pt}\pgfsys@curveto{-2.19284pt}{3.97046pt}{-3.97046pt}{2.19284pt}{-3.97046pt}{0.0pt}\pgfsys@curveto{-3.97046pt}{-2.19284pt}{-2.19284pt}{-3.97046pt}{0.0pt}{-3.97046pt}\pgfsys@curveto{2.19284pt}{-3.97046pt}{3.97046pt}{-2.19284pt}{3.97046pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\scriptsize 0}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\ u_{i}))\
\leavevmode\hbox to8.34pt{\vbox to8.34pt{\pgfpicture\makeatletter\hbox{\hskip
4.17046pt\lower-4.17046pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{3.97046pt}{0.0pt}\pgfsys@curveto{3.97046pt}{2.19284pt}{2.19284pt}{3.97046pt}{0.0pt}{3.97046pt}\pgfsys@curveto{-2.19284pt}{3.97046pt}{-3.97046pt}{2.19284pt}{-3.97046pt}{0.0pt}\pgfsys@curveto{-3.97046pt}{-2.19284pt}{-2.19284pt}{-3.97046pt}{0.0pt}{-3.97046pt}\pgfsys@curveto{2.19284pt}{-3.97046pt}{3.97046pt}{-2.19284pt}{3.97046pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\scriptsize 0}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\ (y_{i}\
\leavevmode\hbox to8.34pt{\vbox to8.34pt{\pgfpicture\makeatletter\hbox{\hskip
4.17046pt\lower-4.17046pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{3.97046pt}{0.0pt}\pgfsys@curveto{3.97046pt}{2.19284pt}{2.19284pt}{3.97046pt}{0.0pt}{3.97046pt}\pgfsys@curveto{-2.19284pt}{3.97046pt}{-3.97046pt}{2.19284pt}{-3.97046pt}{0.0pt}\pgfsys@curveto{-3.97046pt}{-2.19284pt}{-2.19284pt}{-3.97046pt}{0.0pt}{-3.97046pt}\pgfsys@curveto{2.19284pt}{-3.97046pt}{3.97046pt}{-2.19284pt}{3.97046pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\scriptsize 1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\ (F_{i-1}\
\leavevmode\hbox to8.34pt{\vbox to8.34pt{\pgfpicture\makeatletter\hbox{\hskip
4.17046pt\lower-4.17046pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{3.97046pt}{0.0pt}\pgfsys@curveto{3.97046pt}{2.19284pt}{2.19284pt}{3.97046pt}{0.0pt}{3.97046pt}\pgfsys@curveto{-2.19284pt}{3.97046pt}{-3.97046pt}{2.19284pt}{-3.97046pt}{0.0pt}\pgfsys@curveto{-3.97046pt}{-2.19284pt}{-2.19284pt}{-3.97046pt}{0.0pt}{-3.97046pt}\pgfsys@curveto{2.19284pt}{-3.97046pt}{3.97046pt}{-2.19284pt}{3.97046pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\scriptsize 0}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\ v_{i}))\
\leavevmode\hbox to8.34pt{\vbox to8.34pt{\pgfpicture\makeatletter\hbox{\hskip
4.17046pt\lower-4.17046pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{3.97046pt}{0.0pt}\pgfsys@curveto{3.97046pt}{2.19284pt}{2.19284pt}{3.97046pt}{0.0pt}{3.97046pt}\pgfsys@curveto{-2.19284pt}{3.97046pt}{-3.97046pt}{2.19284pt}{-3.97046pt}{0.0pt}\pgfsys@curveto{-3.97046pt}{-2.19284pt}{-2.19284pt}{-3.97046pt}{0.0pt}{-3.97046pt}\pgfsys@curveto{2.19284pt}{-3.97046pt}{3.97046pt}{-2.19284pt}{3.97046pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\scriptsize 0}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\ (z_{i}\
\leavevmode\hbox to8.34pt{\vbox to8.34pt{\pgfpicture\makeatletter\hbox{\hskip
4.17046pt\lower-4.17046pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{3.97046pt}{0.0pt}\pgfsys@curveto{3.97046pt}{2.19284pt}{2.19284pt}{3.97046pt}{0.0pt}{3.97046pt}\pgfsys@curveto{-2.19284pt}{3.97046pt}{-3.97046pt}{2.19284pt}{-3.97046pt}{0.0pt}\pgfsys@curveto{-3.97046pt}{-2.19284pt}{-2.19284pt}{-3.97046pt}{0.0pt}{-3.97046pt}\pgfsys@curveto{2.19284pt}{-3.97046pt}{3.97046pt}{-2.19284pt}{3.97046pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\scriptsize 1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\ (F_{i-1}\
\leavevmode\hbox to8.34pt{\vbox to8.34pt{\pgfpicture\makeatletter\hbox{\hskip
4.17046pt\lower-4.17046pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{3.97046pt}{0.0pt}\pgfsys@curveto{3.97046pt}{2.19284pt}{2.19284pt}{3.97046pt}{0.0pt}{3.97046pt}\pgfsys@curveto{-2.19284pt}{3.97046pt}{-3.97046pt}{2.19284pt}{-3.97046pt}{0.0pt}\pgfsys@curveto{-3.97046pt}{-2.19284pt}{-2.19284pt}{-3.97046pt}{0.0pt}{-3.97046pt}\pgfsys@curveto{2.19284pt}{-3.97046pt}{3.97046pt}{-2.19284pt}{3.97046pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\scriptsize 0}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\ w_{i})))$

with $g\in\\{t_{i},u_{i},v_{i},w_{i},x_{i},y_{i},z_{i}\\}$ denoting a graph
with the single vertex $g$. By Section 2, $F_{1},F_{2},\dots$ are a family of
ccgs and, apparently, all these graphs are connected and without true twins.

###### Lemma 8

For all integers $i\geq 1$, the graph $F_{i}$ is a (odd) $k_{i}$-leaf power
for $k_{i}=2^{i+2}-1$ but not a $(k_{i}-2)$-leaf power and a (even)
$k^{\prime}_{i}$-leaf power for $k^{\prime}_{i}=k_{i}+2^{i}-1$ but not a
$(k^{\prime}_{i}-2)$-leaf power.

This means that, although odd and even leaf root construction follows the same
approach, there are $k$-leaf powers of odd $k$ among the chordal cographs that
have optimal even $k^{\prime}$-leaf roots with $k^{\prime}$ roughly $1.25k$.

##  6 Proofs

Proposition 1. _If $G$ is a ccg without true twins and ${\cal T}$ is the
cotree of $G$ then every 1-node of ${\cal T}$ has exactly two children, one
leaf and one 0-node. _

###### Proof

Consider any 1-node $X$ of ${\cal T}$. Then $X$ is not a leaf and, thus, has
at least two children none of which a 1-node. Since $G$ is free of true twins,
there is at most one leaf among the children of $X$. Distinct leaves $x,y$
would be true twins since, by definition, both are adjacent to all $z\in V(G)$
with the least common ancestor in $\cal T$ labelled by 1. Because $G$ is free
of cycles on four vertices, $X$ also has at most one 0-child. Two distinct
0-nodes $Y,Z$ would represent two induced subgraphs $G_{Y}$ and $G_{Z}$,
where, by definition, $G_{Y}$ contained two not adjacent vertices $a,b$ and
$G_{Z}$ two not adjacent vertices $c,d$. Also by definition, there would be
edges $ac,ad,bc,bd$ in $E(G)$ and, thus, an induced cycle on four vertices in
$G$. Hence, $X$ having exactly two children, one leaf and one 0-node, is the
only remaining possibility. ∎

Proposition 2. _Every connected ccg $G$ without true twins has a unique
universal vertex $u$ and $G-u$ is disconnected (that is, $u$ is a cutvertex).
_

###### Proof

Because $G$ is connected, the cotree has a 1-root $X$. By Proposition 1, $X$
has a leaf child $u$ that, by definition, is universal in $G$ and a 0-child
$Y$. Additional universal vertices would be true twins of $u$. By definition,
$G-u=G_{Y}$ is disconnected and, thus, $u$ is a cutvertex. ∎

Lemma 1. _If $T_{1},\dots,T_{s}$ are $s\geq 2$ trees with
${\mathrm{diam}}(T_{1})\geq\dots\geq{\mathrm{diam}}(T_{s})$ then_

  1. (i)

${\mathrm{rad}}(T_{1})\geq{\mathrm{rad}}(T_{2})\geq\cdots\geq{\mathrm{rad}}(T_{s})$_._

  2. (ii)

_For all_ $1\leq i<j\leq s$, if ${\mathrm{rad}}(T_{i})={\mathrm{rad}}(T_{j})$
then ${\mathrm{\pi}}(T_{i})\leq{\mathrm{\pi}}(T_{j})$.

  3. (iii)

_For all_ $1\leq i<j\leq s$,
${\mathrm{rad}}(T_{i})-{\mathrm{\pi}}(T_{i})\geq{\mathrm{rad}}(T_{j})-{\mathrm{\pi}}(T_{j})$.

###### Proof

Let $i<j$.

  1. (i)

By definition,
$2{\mathrm{rad}}(T_{i})-{\mathrm{\pi}}(T_{i})={\mathrm{diam}}(T_{i})\geq{\mathrm{diam}}(T_{j})=2{\mathrm{rad}}(T_{j})-{\mathrm{\pi}}(T_{j})$.
Clearly, if ${\mathrm{\pi}}(T_{i})={\mathrm{\pi}}(T_{j})$ then we directly get
${\mathrm{rad}}(T_{i})\geq{\mathrm{rad}}(T_{j})$. Otherwise, if only
${\mathrm{\pi}}(T_{i})=1$, we argue that

$2{\mathrm{rad}}(T_{i})>2{\mathrm{rad}}(T_{i})-1={\mathrm{diam}}(T_{i})\geq{\mathrm{diam}}(T_{j})=2{\mathrm{rad}}(T_{j}).$

Finally, if just ${\mathrm{\pi}}(T_{j})=1$ then the diameter of $T_{i}$ is
even and the diameter of $T_{j}$ is odd, thus, not equal. This immediately
tells us that

$2{\mathrm{rad}}(T_{i})={\mathrm{diam}}(T_{i})>{\mathrm{diam}}(T_{j})=2{\mathrm{rad}}(T_{j})-1$

and, hence, $2{\mathrm{rad}}(T_{i})\geq 2{\mathrm{rad}}(T_{j})$ and we are
done.

  2. (ii)

If ${\mathrm{rad}}(T_{i})={\mathrm{rad}}(T_{j})$, then
$2{\mathrm{rad}}(T_{i})-{\mathrm{\pi}}(T_{i})={\mathrm{diam}}(T_{i})\geq{\mathrm{diam}}(T_{j})=2{\mathrm{rad}}(T_{j})-{\mathrm{\pi}}(T_{j})=2{\mathrm{rad}}(T_{i})-{\mathrm{\pi}}(T_{j})$.
Hence, ${\mathrm{\pi}}(T_{i})\leq{\mathrm{\pi}}(T_{j})$.

  3. (iii)

By (i), ${\mathrm{rad}}(T_{i})\geq{\mathrm{rad}}(T_{j})$. If
${\mathrm{rad}}(T_{i})>{\mathrm{rad}}(T_{j})$, then
${\mathrm{rad}}(T_{i})-{\mathrm{\pi}}(T_{i})>{\mathrm{rad}}(T_{j})-{\mathrm{\pi}}(T_{i})\geq{\mathrm{rad}}(T_{j})-1$.
Hence,
${\mathrm{rad}}(T_{i})-{\mathrm{\pi}}(T_{i})\geq{\mathrm{rad}}(T_{j})\geq{\mathrm{rad}}(T_{j})-{\mathrm{\pi}}(T_{j})$.
If ${\mathrm{rad}}(T_{i})={\mathrm{rad}}(T_{j})$, then, by (ii),
${\mathrm{\pi}}(T_{i})\leq{\mathrm{\pi}}(T_{j})$. Hence,
${\mathrm{rad}}(T_{i})-{\mathrm{\pi}}(T_{i})={\mathrm{rad}}(T_{j})-{\mathrm{\pi}}(T_{i})\geq{\mathrm{rad}}(T_{j})-{\mathrm{\pi}}(T_{j})$.

∎

Lemma 2. _Every $k$-leaf root $T$ of a connected graph satisfies
$d^{\mathrm{min}}_{T}\leq\tfrac{k}{2}$. _

###### Proof

Let $T$ be a $k$-leaf root of a connected graph $G$, and let $z$ be a min-max
center vertex of $T$. Let $T^{\prime}$ be any subtree of $T-z$. Then, every
pair of leaf $v$ in $T^{\prime}$ and leaf $w$ outside $T^{\prime}$ fulfills

${\mathrm{dist}}_{T}(u,v)={\mathrm{dist}}_{T}(u,z)+{\mathrm{dist}}_{T}(z,v)\geq
2\\!\cdot\\!d^{\mathrm{min}}_{T}.$

Thus, if $d^{\mathrm{min}}_{T}$ was larger than $\tfrac{k}{2}$, then
${\mathrm{dist}}_{T}(u,v)>k$ and $G$ would be disconnected. ∎

Lemma 3. _If $G$ is a non-complete graph with a universal vertex $u$ and $T$
is a $k$-leaf root of $G$ then ${\mathrm{dist}}_{T}(u,z)\leq
k-{\mathrm{rad}}(T)+{\mathrm{\pi}}(T)$ for all center vertices $z$ of $T$. If
$z_{1}\not=z_{2}$ are the center vertices of $T$, then
${\mathrm{dist}}_{T}(u,z_{1})\leq k-{\mathrm{rad}}(T)$ or
${\mathrm{dist}}_{T}(u,z_{2})\leq k-{\mathrm{rad}}(T)$. _

###### Proof

Consider a diametral path $P$ in $T$, and let $x,y$ be the end vertices of
$P$. Since $G$ is not complete, $x$ and $y$ are not adjacent in $G$. Hence,
$u$, $x$ and $y$ are different leaves in $T$. Then the three paths in $T$, the
$x,u$-path, the $y,u$-path, and $P$ intersect at a unique (non-leaf) vertex on
$P$, say $c$. Let $\ell_{1}$ be the length of the $x,c$-path and $\ell_{2}$ be
the length of the $y,c$-path in $T$. Since $u$ is universal in $G$, we have

${\mathrm{dist}}_{T}(u,c)+\ell_{1}\leq
k\quad\text{and}\quad{\mathrm{dist}}_{T}(u,c)+\ell_{2}\leq k.$

Let $z_{1},z_{2}$ be the center vertices of $T$; possibly with $z_{1}=z_{2}$,
if ${\mathrm{diam}}(T)$ is even. Recall that, since $P$ is a diametral path,
the centers of $T$ and $P$ coincide, and that $z_{1}z_{2}$ is an edge on $P$
whenever $z_{1}\not=z_{2}$. Let, without loss of generality, $z_{1}$ be on the
$x,z_{2}$-path (and so $z_{2}$ is on the $y,z_{1}$-path). Then

$\displaystyle{\mathrm{dist}}_{T}(z_{1},y)$
$\displaystyle={\mathrm{rad}}(T)={\mathrm{dist}}_{T}(z_{2},x)\text{ and}$
$\displaystyle{\mathrm{dist}}_{T}(z_{1},x)$
$\displaystyle={\mathrm{rad}}(T)-{\mathrm{\pi}}(T)={\mathrm{dist}}_{T}(z_{2},y).$

Assume $c$ on the $x,z_{1}$-path; possibly with $c=z_{1}$. Then

$\displaystyle{\mathrm{dist}}_{T}(u,z_{1})$
$\displaystyle={\mathrm{dist}}_{T}(u,c)+\big{(}\ell_{2}-{\mathrm{dist}}_{T}(z_{1},y)\big{)}$
$\displaystyle=\big{(}{\mathrm{dist}}_{T}(u,c)+\ell_{2}\big{)}-{\mathrm{rad}}(T)$
$\displaystyle\leq k-{\mathrm{rad}}(T)\quad\text{and}$
$\displaystyle{\mathrm{dist}}_{T}(u,z_{2})$
$\displaystyle={\mathrm{dist}}_{T}(u,c)+\big{(}\ell_{2}-{\mathrm{dist}}_{T}(z_{2},y)\big{)}$
$\displaystyle=\big{(}{\mathrm{dist}}_{T}(u,c)+\ell_{2}\big{)}-\big{(}{\mathrm{rad}}(T)-{\mathrm{\pi}}(T)\big{)}$
$\displaystyle\leq k-{\mathrm{rad}}(T)+{\mathrm{\pi}}(T).$

In the case, where $c$ is on the $y,z_{2}$-path, the same arguments yield
${\mathrm{dist}}_{T}(u,z_{2})\leq k-{\mathrm{rad}}(T)$ and
${\mathrm{dist}}_{T}(u,z_{1})\leq k-{\mathrm{rad}}(T)+{\mathrm{\pi}}(T)$. ∎

Corollary 1. _If $G$ is a graph with a universal vertex and $T$ is a $k$-leaf
root of $G$ then ${\mathrm{rad}}(T)\leq k-1$ and, in particular,
${\mathrm{diam}}(T)\leq 2k-2$. _

###### Proof

For complete graphs, the statement is obvious. So, let $G$ be a non-complete
graph with universal vertex $u$. By Lemma 3,
$1\leq{\mathrm{dist}}_{T}(u,z)\leq k-{\mathrm{rad}}(T)$ for any center vertex
$z$ of $T$. Hence, ${\mathrm{rad}}(T)\leq k-1$. Since ${\mathrm{diam}}(T)\leq
2\\!\cdot\\!{\mathrm{rad}}(T)$, we have ${\mathrm{diam}}(T)\leq 2k-2$. ∎

Lemma 4. _If $T$ is a $k$-leaf root of a graph $G$ and $\delta\geq 0$ an
integer then $T^{\prime}=\eta(T,\delta)$ is a $(k+2\delta)$-leaf root of $G$
with same center, same min-max center vertices, and
${\mathrm{diam}}(T^{\prime})={\mathrm{diam}}(T)+2\delta$,
${\mathrm{rad}}(T^{\prime})={\mathrm{rad}}(T)+\delta$,
$d^{\mathrm{min}}_{T^{\prime}}=d^{\mathrm{min}}_{T}+\delta$. _

###### Proof

Note that $T$ and $T^{\prime}$ have the same set of leaves. For every two
leaves $u$ and $v$, we have
${\mathrm{dist}}_{T^{\prime}}(u,v)={\mathrm{dist}}_{T}(u,v)+2\delta$. Hence,
${\mathrm{dist}}_{T^{\prime}}(u,v)\leq k+2\delta$ if and only if
${\mathrm{dist}}_{T}(u,v)\leq k$. Thus, $T^{\prime}$ is a $k+2\delta$-leaf
root of $G$. The other statements are obvious from the respective definitions.
∎

Lemma 5. _Let $G$ be a graph and $k\geq 2$ an integer. If $G$ is disconnected
with $s\geq 0$ non-trivial connected components $G_{1},\dots,G_{s}$ and $t\geq
0$ isolated vertices $v_{1},\dots,v_{t}$ such that $s+t\geq 2$ and if
$T_{1},\dots,T_{s}$ are $k$-leaf roots for $G_{1},\dots,G_{s}$ then
$T=\mu(k,T_{1},\dots,T_{s},v_{1},\dots,v_{t})$ is a $k$-leaf root of $G$. _

###### Proof

From the construction, we immediately see for all distinct vertices $x$ and
$y$ from the same component $G_{i}$ that
${\mathrm{dist}}_{T}(x,y)={\mathrm{dist}}_{T_{i}}(x,y)$. Hence,
${\mathrm{dist}}_{T}(x,y)\leq k$, if and only if
${\mathrm{dist}}_{T_{i}}(x,y)\leq k$, if and only if $xy$ is an edge in
$G_{i}$.

To prove that $T$ is a $k$-leaf root for $G$, it is sufficient to show for all
vertices $x$ and $y$ stemming from different components of $G$ that
${\mathrm{dist}}_{T}(x,y)>k$. In case of $s>0$, we assume, without loss of
generality, that the critical index is $m=1$. For the remainder of the proof,
we keep in mind that, by the definition of a min-max center,
${\mathrm{dist}}_{T_{i}}(x,z_{i})-d^{\mathrm{min}}_{T_{i}}\geq 0$ for all
$T_{i},1\leq i\leq s$ with min-max center $z_{i}$ and all leaves $x$ of
$T_{i}$.

For a start, we consider a vertex $x$ in $G_{1}$ and $v_{j}$ for any
$j\in\\{1,\dots,t\\}$ and see

${\mathrm{dist}}_{T}(x,v_{j})={\mathrm{dist}}_{T_{1}}(x,z_{1})+\big{(}\tfrac{k+{\mathrm{\pi}}(k)}{2}-d^{\mathrm{min}}_{T_{1}}\big{)}+\big{(}\tfrac{k-{\mathrm{\pi}}(k)}{2}+1\big{)}\geq
k+1.$

Similarly, for any vertex $x$ in $G_{i}$, $1<i\leq s$, and $v_{j}$, we get

${\mathrm{dist}}_{T}(x,v_{j})={\mathrm{dist}}_{T_{i}}(x,z_{i})+\big{(}\tfrac{k-{\mathrm{\pi}}(k)}{2}+1-d^{\mathrm{min}}_{T_{i}}\big{)}+\big{(}\tfrac{k-{\mathrm{\pi}}(k)}{2}+1\big{)}\geq
k+1.$

For any vertex $x$ in $G_{1}$ and $y$ in $G_{j}$ with $1<j\leq s$, it is

$\displaystyle{\mathrm{dist}}_{T}(x,y)$
$\displaystyle={\mathrm{dist}}_{T_{1}}(x,z_{1})+\big{(}\tfrac{k+{\mathrm{\pi}}(k)}{2}-d^{\mathrm{min}}_{T_{1}}\big{)}+\big{(}\tfrac{k-{\mathrm{\pi}}(k)}{2}+1-d^{\mathrm{min}}_{T_{j}}\big{)}+{\mathrm{dist}}_{T_{j}}(z_{j},y)$
$\displaystyle=(k+1)+\big{(}{\mathrm{dist}}_{T_{1}}(x,z_{1})-d^{\mathrm{min}}_{T_{1}}\big{)}+\big{(}{\mathrm{dist}}_{T_{j}}(z_{j},y)-d^{\mathrm{min}}_{T_{j}}\big{)}\geq
k+1.$

Similarly, for any vertex $x$ in $G_{i}$ and $y$ in $G_{j}$ with $1<i<j\leq
s$, we get

$\displaystyle{\mathrm{dist}}_{T}(x,y)$
$\displaystyle={\mathrm{dist}}_{T_{i}}(x,z_{i})+\big{(}\tfrac{k-{\mathrm{\pi}}(k)}{2}+1-d^{\mathrm{min}}_{T_{i}}\big{)}+\big{(}\tfrac{k-{\mathrm{\pi}}(k)}{2}+1-d^{\mathrm{min}}_{T_{j}}\big{)}+{\mathrm{dist}}_{T_{j}}(z_{j},y)$
$\displaystyle=(k+2-{\mathrm{\pi}}(k))+\big{(}{\mathrm{dist}}_{T_{i}}(x,z_{i})-d^{\mathrm{min}}_{T_{i}}\big{)}+\big{(}{\mathrm{dist}}_{T_{j}}(z_{j},y)-d^{\mathrm{min}}_{T_{j}}\big{)}\geq
k+1.$

Finally, the distance between $v_{i}$ and $v_{j}$ with $1\leq i<j\leq t$ is

${\mathrm{dist}}_{T}(v_{i},v_{j})=2\cdot\big{(}\tfrac{k-{\mathrm{\pi}}(k)}{2}+1\big{)}\geq
k+1.$

It follows for all $x,y\in V(G)$ that $xy\in E(G)$ if and only if
${\mathrm{dist}}_{T}(x,y)\leq k$. That is, $T$ is a $k$-leaf root of $G$. ∎

Theorem 3.1. _Let $G$ be a ccg on $n$ vertices and without true twins and let
$p\in\\{0,1\\}$. Then $(T,k)=\rho(G,p)$ provides a $k$-leaf root $T$ of $G$
that is optimal for parity $p$ (hence, ${\mathrm{\pi}}(k)=p$) and with $k\leq
n+1$. If $G$ is connected then_

(T1)

${\mathrm{rad}}(T)=k-1$_,_

(T2)

$d^{\mathrm{min}}_{T}=1+{\mathrm{\pi}}(T)$_, and_

(T3)

${\mathrm{diam}}(T^{\prime})\geq{\mathrm{diam}}(T)+k^{\prime}-k$_for all_
$k^{\prime}$-leaf roots $T^{\prime}$ of $G$ with
${\mathrm{\pi}}(k^{\prime})=p$.

###### Proof

The proof of Theorem 3.1 stands for the majority of the work behind this paper
and, without subdivision, it is fairly long. So, to make reading easier, we
break it down into the proofs of several propositions. In principle, the proof
will be by complete induction on the vertex number and, below, we begin with
the first proposition that serves the base case.

###### Proposition 3

Let $G$ be a star on $n\geq 3$ vertices and let $p\in\\{0,1\\}$ be a given
parity. Then $(T,k)=\rho(G,p)$ provides a $k$-leaf root $T$ of $G$ that is
optimal for parity $p$ (hence, ${\mathrm{\pi}}(k)=p$) with $k=4-p\leq n+1$ and
satisfying (T1), (T2), and (T3).

For a proof of Proposition 3, we start by observing that $G$ does not have
true twins and, thus, $\rho(G,p)$ is well-defined. Moreover, since $G$ is not
complete, every $3$-leaf root of $G$ is an optimal (odd) leaf root and every
$4$-leaf root is an optimal even leaf root of $G$. By the same reason, any
$k^{\prime}$-leaf root $T^{\prime}$ of $G$ satisfies
${\mathrm{diam}}(T^{\prime})\geq k^{\prime}+1$.

We first consider the odd case, where $k=3=4-{\mathrm{\pi}}(k)$, and show that
the tree $T$ returned in Step (i.i.1.) is a $3$-leaf root of $G$ satisfying
the claimed conditions. In fact, $T$ is just $\eta(G,1)$ with an additional
leaf attached for $u$. This is obviously a $3$-leaf root of $G$ with
${\mathrm{rad}}(T)=2=k-1<n$, ${\mathrm{diam}}(T)=4$ and, thus,
${\mathrm{\pi}}(T)=0$ and $d^{\mathrm{min}}_{T}=1=1+{\mathrm{\pi}}(T)$.
Moreover, for any $k^{\prime}$-leaf root $T^{\prime}$ of $G$, we see that

${\mathrm{diam}}(T^{\prime})\geq
k^{\prime}+1=4+k^{\prime}-3={\mathrm{diam}}(T)+k^{\prime}-k,$

which settles the odd case.

In the even case, we have $k=4$. If $G$ has exactly two leaves $v_{1},v_{2}$
attached to the central vertex $u$ then Step (i.i.2.) returns the tree $T$
where the leaves $u,v_{1}$ and $v_{2}$ are attached to a vertex $v$ with paths
of lengths one, two and three, respectively. Obviously, $T$ is a $4$-leaf root
of $G$ with ${\mathrm{rad}}(T)=3=k-1=n$, ${\mathrm{diam}}(T)=5$ and, thus,
${\mathrm{\pi}}(T)=1$ and $d^{\mathrm{min}}_{T}=2=1+{\mathrm{\pi}}(T)$. Every
even $k^{\prime}$-leaf root $T^{\prime}$ of $G$ fulfills

${\mathrm{diam}}(T^{\prime})\geq
k^{\prime}+1=5+k^{\prime}-4={\mathrm{diam}}(T)+k^{\prime}-k,$

which settles this case, too.

Finally, let $p=0$ and $t\geq 3$, where Step (i.i.3.) constructs $T$ from
$\eta(G,2)$ by attaching a new leaf to $u$. Similar to the odd case, $T$ is
obviously a $4$-leaf root of $G$ with ${\mathrm{rad}}(T)=3=k-1<n$,
${\mathrm{diam}}(T)=6$ and, thus, ${\mathrm{\pi}}(T)=0$ and
$d^{\mathrm{min}}_{T}=1=1+{\mathrm{\pi}}(T)$. To see (T3), suppose to the
contrary that
${\mathrm{diam}}(T^{\prime})<{\mathrm{diam}}(T)+k^{\prime}-k=6+k^{\prime}-4=k^{\prime}+2$
for some even $k^{\prime}$-leaf root $T^{\prime}$ of $G$. Consider the vertex
$w$ on the $v_{1},v_{2}$-path in $T^{\prime}$ that is closest to $v_{3}$ and
let $d_{i}={\mathrm{dist}}_{T^{\prime}}(v_{i},w)$ for all $i\in\\{1,2,3\\}$.
Because of the diameter bound and since $v_{1},v_{2}$ and $v_{3}$ are pairwise
non-adjacent in $G$, we have $k^{\prime}+1\leq d_{i}+d_{j}<k^{\prime}+2$ for
all $1\leq i<j\leq 3$. This means
$d_{1}+d_{2}=d_{1}+d_{3}=d_{2}+d_{3}=k^{\prime}+1$. Hence,
$2(d_{1}+d_{2}+d_{3})=3(k^{\prime}+1)$, which implies that $3(k^{\prime}+1)$
is even. This is a contradiction to the fact that $k^{\prime}$ is even and,
thus, the last case is settled. Thus, Proposition 3 has been shown.

With the following proposition, we only care about non-trivial connected input
graphs and, for the moment, refrain from showing the optimality of $(T,k)$ or
even property (T3).

###### Proposition 4

Let $G$ be a connected ccg on $n$ vertices and without true twins and let
$p\in\\{0,1\\}$ be a given parity. Then $(T,k)=\rho(G,p)$ provides a $k$-leaf
root $T$ of $G$ with ${\mathrm{\pi}}(k)=p$ and $k\leq n+1$ and satisfying (T1)
and (T2).

The proof of Proposition 4 works by induction on the vertex number of $G$. The
smallest connected ccg without true twins is the star with two leaves (since
we ignore graphs with just one vertex). In Proposition 3, this base case has
already been settled. Moreover, Proposition 3 allows to assume that $G$ is not
a larger star in the following induction step.

Next, let $G$ have more than three vertices. Because $G$ is connected and not
a star, we are in Case ii. of the procedure for $\rho$. Again because $G$ is
connected and without true twins, it has a unique universal cutvertex by
Proposition 2. Hence, $H=G-u$ is disconnected. Since $G$ is not a star, $H$
has $s\geq 1$ non-trivial connected components $G_{1},\ldots,G_{s}$ and $t\geq
0$ isolated vertices $v_{1},\ldots,v_{t}$ such that $s+t\geq 2$.

Note that, as for $G$, every $G_{i}$ is a connected ccg without true twins but
with fewer vertices than $G$. This means that the induction hypothesis holds
and, thus, Step (ii.ii.1.) provides a $k_{i}$-leaf root $T_{i}$ of parity $p$
satisfying (T1) and (T2) for every $G_{i}$, $1\leq i\leq s$. We observe that
$k_{i}\geq 3$ for all $i\in\\{1,\dots,s\\}$ as none of $G_{1},\dots,G_{s}$ is
a complete graph (since they are neither isolated vertices nor contain true
twins).

At this point, we assume, without loss of generality, that
${\mathrm{diam}}(T_{1})\geq{\mathrm{diam}}(T_{2})\geq\dots\geq{\mathrm{diam}}(T_{s})$.
In addition to a simplified argumentation below, we get that

$k_{1}\geq k_{2}\geq\dots\geq k_{s}\text{ and also
}k_{1}-{\mathrm{\pi}}(T_{1})\geq k_{2}-{\mathrm{\pi}}(T_{2})\geq\dots\geq
k_{s}-{\mathrm{\pi}}(T_{s}).$

This is firstly because of Lemma 1, which implies

$\displaystyle{\mathrm{rad}}(T_{1})\geq{\mathrm{rad}}(T_{2})\geq\dots\geq{\mathrm{rad}}(T_{s})\text{
and }$
$\displaystyle{\mathrm{rad}}(T_{1})-{\mathrm{\pi}}(T_{1})\geq{\mathrm{rad}}(T_{2})-{\mathrm{\pi}}(T_{2})\geq\dots\geq{\mathrm{rad}}(T_{s})-{\mathrm{\pi}}(T_{a}),$

and secondly because of the induction hypothesis
$k_{i}={\mathrm{rad}}(T_{i})+1$, $1\leq i\leq s$. Hence, if $s>1$ then Step
(ii.ii.2.) selects $k_{a}=k_{1}$, $k_{b}=k_{2}$ and, if it exists,
$k_{c}=k_{3}$.

Next, let $k$ be the number computed in Step (ii.ii.2.) and note that
${\mathrm{\pi}}(k)=p$ and $k>k_{i},1\leq i\leq s$. By Lemma 4, Step (ii.ii.3.)
produces a $k$-leaf root
$T^{\prime}_{i}=\eta\left(T_{i},\tfrac{k-k_{i}}{2}\right)$ of $G_{i}$ for all
$i\in\\{1,\dots,s\\}$ such that

$\displaystyle{\mathrm{diam}}(T^{\prime}_{i})$
$\displaystyle={\mathrm{diam}}(T_{i})+k-k_{i},$
$\displaystyle{\mathrm{rad}}(T^{\prime}_{i})$
$\displaystyle={\mathrm{rad}}(T_{i})+\tfrac{k-k_{i}}{2}=\tfrac{k+k_{i}}{2}-1,$
$\displaystyle k-1$ $\displaystyle\leq|V(G_{i})|+(k-k_{i}),\text{ and}$
$\displaystyle d^{\mathrm{min}}_{T^{\prime}_{i}}$
$\displaystyle=d^{\mathrm{min}}_{T_{i}}+\tfrac{k-k_{i}}{2}=1+{\mathrm{\pi}}(T_{i})+\tfrac{k-k_{i}}{2}.$

Then, Lemma 5 tells us that Step (ii.ii.4.) assembles a $k$-leaf root
$T^{\prime}$ of $H$.

Observe that, under the given assumption that
${\mathrm{diam}}(T_{1})\geq{\mathrm{diam}}(T_{2})\geq\dots\geq{\mathrm{diam}}(T_{s})$,
the $\mu$-operation chooses the critical index $m=1$. This happens because
$\mu$ uses $m$ to select the first tree in
$T^{\prime}_{1},\dots,T^{\prime}_{s}$ that minimizes
$d^{\mathrm{min}}_{T^{\prime}_{m}}=1+{\mathrm{\pi}}(T_{m})+\tfrac{k-k_{m}}{2}$.
In fact, if there was $i\in\\{2,\dots,s\\}$ with
${\mathrm{\pi}}(T_{i})-\tfrac{k_{i}}{2}<{\mathrm{\pi}}(T_{1})-\tfrac{k_{1}}{2}$
then we had $k_{1}-k_{i}<2({\mathrm{\pi}}(T_{1})-{\mathrm{\pi}}(T_{i}))$.
Since $k_{1}\geq k_{i}$ and both are of the same parity and
${\mathrm{\pi}}(T_{1}),{\mathrm{\pi}}(T_{i})\in\\{0,1\\}$, we could conclude
that $k_{1}=k_{i}$ and ${\mathrm{\pi}}(T_{1})=1$ and
${\mathrm{\pi}}(T_{i})=0$. But that would imply the contradiction

$\displaystyle{\mathrm{diam}}(T_{1})$
$\displaystyle=2{\mathrm{rad}}(T_{1})-{\mathrm{\pi}}(T_{1})=2(k_{1}-1)-1<2(k_{1}-1)-0$
$\displaystyle=2(k_{i}-1)-{\mathrm{\pi}}(T_{i})=2{\mathrm{rad}}(T_{i})-{\mathrm{\pi}}(T_{i})={\mathrm{diam}}(T_{i}).$

In the following, we show that ${\mathrm{rad}}(T^{\prime})=k-1\leq n$ and, for
that purpose, we firstly determine the diameter of $T^{\prime}$. A diametral
path in $T^{\prime}$ connects two leaves $x$ and $y$, thus, vertices of $H$.
To find the length of a diametral path, thus, the diameter of $T^{\prime}$, we
subsequently analyze all possible origins of $x,y$ in $H$.

For leaves $x$ and $y$ of the same $G_{i},1\leq i\leq s$, the longest possible
connecting path has length

${\mathrm{diam}}(T^{\prime}_{i})=2{\mathrm{rad}}(T^{\prime}_{i})-{\mathrm{\pi}}(T^{\prime}_{i})=2\big{(}\tfrac{k+k_{i}}{2}-1\big{)}-{\mathrm{\pi}}(T_{i})=k+k_{i}-{\mathrm{\pi}}(T_{i})-2.$

The longest path in $T^{\prime}$ connecting a leaf $x$ in $G_{1}$ (recall the
critical index $m=1$) and $y=v_{j},1\leq j\leq t$ has length

$\displaystyle\ell_{1}$
$\displaystyle=\big{(}{\mathrm{rad}}(T^{\prime}_{1})+\tfrac{k+{\mathrm{\pi}}(k)}{2}-d^{\mathrm{min}}_{T^{\prime}_{1}}\big{)}+\tfrac{k-{\mathrm{\pi}}(k)}{2}+1$
$\displaystyle=k+{\mathrm{rad}}(T^{\prime}_{1})-d^{\mathrm{min}}_{T^{\prime}_{1}}+1$
$\displaystyle=k+\big{(}\tfrac{k+k_{1}}{2}-1\big{)}-\big{(}1+{\mathrm{\pi}}(T_{1})+\tfrac{k-k_{1}}{2}\big{)}+1$
$\displaystyle=k+k_{1}-{\mathrm{\pi}}(T_{1})-1.$

Similarly, a longest path of $T^{\prime}$ connecting a leaf $x$ in $G_{i}$
with $i\in\\{2,\dots,s\\}$ and $y=v_{j},1\leq j\leq t$ has length

$\displaystyle\ell_{i}$
$\displaystyle=\big{(}{\mathrm{rad}}(T^{\prime}_{i})+\tfrac{k-{\mathrm{\pi}}(k)}{2}+1-d^{\mathrm{min}}_{T^{\prime}_{i}}\big{)}+\tfrac{k-{\mathrm{\pi}}(k)}{2}+1$
$\displaystyle=k-{\mathrm{\pi}}(k)+{\mathrm{rad}}(T^{\prime}_{i})-d^{\mathrm{min}}_{T^{\prime}_{i}}+1$
$\displaystyle=k-{\mathrm{\pi}}(k)+\big{(}\tfrac{k+k_{i}}{2}-1)-\big{(}1+{\mathrm{\pi}}(T_{i})+\tfrac{k-k_{i}}{2}\big{)}+1$
$\displaystyle=k-{\mathrm{\pi}}(k)+k_{i}-{\mathrm{\pi}}(T_{i})-1.$

Next, let $x$ be a leaf in $G_{1}$ (again, recall that the critical index $m$
is $1$) and $y$ a leaf in $G_{i}$ with $i\in\\{2,\dots,s\\}$ that are most
distant from each other in $T^{\prime}$. The path connecting the leaves $x$
and $y$ has length

$\displaystyle\ell_{1,i}$
$\displaystyle=\big{(}{\mathrm{rad}}(T^{\prime}_{1})+\tfrac{k-{\mathrm{\pi}}(k)}{2}+1-d^{\mathrm{min}}_{T^{\prime}_{1}}\big{)}+\big{(}\tfrac{k+{\mathrm{\pi}}(k)}{2}-d^{\mathrm{min}}_{T^{\prime}_{i}}+{\mathrm{rad}}(T^{\prime}_{i})\big{)}$
$\displaystyle=k+({\mathrm{rad}}(T^{\prime}_{1})-d^{\mathrm{min}}_{T^{\prime}_{1}})+({\mathrm{rad}}(T^{\prime}_{i})-d^{\mathrm{min}}_{T^{\prime}_{i}})+1$
$\displaystyle=k+\tfrac{k+k_{1}}{2}-1-\big{(}1+{\mathrm{\pi}}(T_{1})+\tfrac{k-k_{1}}{2}\big{)}+\tfrac{k+k_{i}}{2}-1-\big{(}1+{\mathrm{\pi}}(T_{i})+\tfrac{k-k_{i}}{2}\big{)}+1$
$\displaystyle=k+k_{1}-{\mathrm{\pi}}(T_{1})+k_{i}-{\mathrm{\pi}}(T_{i})-3.$

The leaves $x$ in $G_{i}$ and $y$ in $G_{j}$ with $i,j\in\\{2,\dots,s\\}$ and
$i<j$ that are farthest from each other in $T^{\prime}$ have distance

$\displaystyle\ell_{i,j}$
$\displaystyle=\big{(}{\mathrm{rad}}(T^{\prime}_{i})+\tfrac{k-{\mathrm{\pi}}(k)}{2}+1-d^{\mathrm{min}}_{T^{\prime}_{i}}\big{)}+\big{(}\tfrac{k-{\mathrm{\pi}}(k)}{2}+1-d^{\mathrm{min}}_{T^{\prime}_{j}}+{\mathrm{rad}}(T^{\prime}_{j})\big{)}$
$\displaystyle=k-{\mathrm{\pi}}(k)+({\mathrm{rad}}(T^{\prime}_{i})-d^{\mathrm{min}}_{T^{\prime}_{i}})+({\mathrm{rad}}(T^{\prime}_{j})-d^{\mathrm{min}}_{T^{\prime}_{j}})+2$
$\displaystyle=k-{\mathrm{\pi}}(k)+\tfrac{k+k_{i}}{2}-1-\big{(}1+{\mathrm{\pi}}(T_{i})+\tfrac{k-k_{i}}{2}\big{)}+\tfrac{k+k_{j}}{2}-1-\big{(}1+{\mathrm{\pi}}(T_{j})+\tfrac{k-k_{i}}{2}\big{)}+2$
$\displaystyle=k-{\mathrm{\pi}}(k)+k_{i}-{\mathrm{\pi}}(T_{i})+k_{j}-{\mathrm{\pi}}(T_{j})-2.$

Finally, any $x=v_{i}$ and $y=v_{j}$, $1\leq i<j\leq t$, have distance

${\mathrm{dist}}_{T^{\prime}}(v_{i},v_{j})=2\big{(}\tfrac{k-{\mathrm{\pi}}(k)}{2}+1\big{)}=k-{\mathrm{\pi}}(k)+2.$

Before we can determine the diameter of $T^{\prime}$, we need to sort out the
longest paths of $T^{\prime}$ from those given above. By premise,
${\mathrm{diam}}(T^{\prime}_{1})\geq{\mathrm{diam}}(T^{\prime}_{2})\geq\dots\geq{\mathrm{diam}}(T^{\prime}_{s})$.
Next, if $t>0$ then we obviously have that
$\ell_{1}>{\mathrm{diam}}(T^{\prime}_{1})$ and, by $k_{1}\geq
k_{2}\geq\dots\geq k_{s}$, that $\ell_{1}\geq\ell_{i}$ for all
$i\in\\{2,\dots,s\\}$. Moreover, in case of $t\geq 2$, we also find that

$\ell_{1}-{\mathrm{dist}}_{T^{\prime}}(v_{i},v_{j})=(k+k_{1}-{\mathrm{\pi}}(T_{1})-1)-(k-{\mathrm{\pi}}(k)+2)=k_{1}+{\mathrm{\pi}}(k)-{\mathrm{\pi}}(T_{1})-3$

for all $1\leq i<j\leq t$. If $k_{1}=3$ then, because
${\mathrm{\pi}}(k)={\mathrm{\pi}}(k_{1})=1$, we get
$\ell_{1}-{\mathrm{dist}}_{T^{\prime}}(v_{i},v_{j})=1-{\mathrm{\pi}}(T_{1})\geq
0$, which means $\ell_{1}\geq{\mathrm{dist}}_{T^{\prime}}(v_{i},v_{j})$. This
holds even more so if $k_{1}>3$.

If $s\geq 2$ then

$\displaystyle\ell_{1,2}-\ell_{1,i}$ $\displaystyle=$
$\displaystyle(k+k_{1}-{\mathrm{\pi}}(T_{1})+k_{2}-{\mathrm{\pi}}(T_{2})-3)-(k+k_{1}-{\mathrm{\pi}}(T_{1})+k_{i}-{\mathrm{\pi}}(T_{i})-3)$
$\displaystyle=$
$\displaystyle((k_{2}-1)-{\mathrm{\pi}}(T_{2}))-((k_{i}-1)-{\mathrm{\pi}}(T_{i}))$
$\displaystyle=$
$\displaystyle({\mathrm{rad}}(T_{2})-{\mathrm{\pi}}(T_{2}))-({\mathrm{rad}}(T_{i})-{\mathrm{\pi}}(T_{i}))$
$\displaystyle\geq$ $\displaystyle 0\text{ for all }i\geq 2\text{ by
Lemma~{}\ref{lem:technical}},$
$\displaystyle\ell_{1,2}-{\mathrm{diam}}(T^{\prime}_{1})$ $\displaystyle=$
$\displaystyle(k+k_{1}-{\mathrm{\pi}}(T_{1})+k_{2}-{\mathrm{\pi}}(T_{2})-3)-(k+k_{1}-{\mathrm{\pi}}(T_{1})-2)$
$\displaystyle=$ $\displaystyle k_{2}-{\mathrm{\pi}}(T_{2})-1>0\text{ since
}k_{2}\geq 3,\text{ and}$ $\displaystyle\text{if }t>0\text{ then
}\ell_{1,2}-\ell_{1}$ $\displaystyle=$
$\displaystyle(k+k_{1}-{\mathrm{\pi}}(T_{1})+k_{2}-{\mathrm{\pi}}(T_{2})-3)-(k+k_{1}-{\mathrm{\pi}}(T_{1})-1)$
$\displaystyle=$ $\displaystyle k_{2}-{\mathrm{\pi}}(T_{2})-2\geq 0\text{
because }k_{2}\geq 3.$

Moreover, if $s>2$ then

$\displaystyle\ell_{1,2}-\ell_{2,3}$ $\displaystyle=$
$\displaystyle(k+k_{1}-{\mathrm{\pi}}(T_{1})+k_{2}-{\mathrm{\pi}}(T_{2})-3)-(k-{\mathrm{\pi}}(k)+k_{2}-{\mathrm{\pi}}(T_{2})+k_{3}-{\mathrm{\pi}}(T_{3})-2)$
$\displaystyle=$
$\displaystyle((k_{1}-1)-{\mathrm{\pi}}(T_{1}))-((k_{3}-1)-{\mathrm{\pi}}(T_{3}))+{\mathrm{\pi}}(k)-1$
$\displaystyle=$
$\displaystyle({\mathrm{rad}}(T_{1})-{\mathrm{\pi}}(T_{1}))-({\mathrm{rad}}(T_{3})-{\mathrm{\pi}}(T_{3}))+{\mathrm{\pi}}(k)-1$
$\displaystyle\geq$ $\displaystyle 0\text{ if }{\mathrm{\pi}}(k)=1\text{ by
Lemma~{}\ref{lem:technical} and}$ $\displaystyle\ell_{2,3}-\ell_{i,j}$
$\displaystyle=$
$\displaystyle(k-{\mathrm{\pi}}(k)+k_{2}-{\mathrm{\pi}}(T_{2})+k_{3}-{\mathrm{\pi}}(T_{3})-2)-(k-{\mathrm{\pi}}(k)+k_{i}-{\mathrm{\pi}}(T_{i})+k_{j}-{\mathrm{\pi}}(T_{j})-2)$
$\displaystyle=$
$\displaystyle\big{(}((k_{2}-1)-{\mathrm{\pi}}(T_{2}))-((k_{i}-1)-{\mathrm{\pi}}(T_{i}))\big{)}+\big{(}((k_{3}-1)-{\mathrm{\pi}}(T_{3}))-((k_{j}-1)-{\mathrm{\pi}}(T_{j}))\big{)}$
$\displaystyle=$
$\displaystyle\big{(}({\mathrm{rad}}(T_{2})-{\mathrm{\pi}}(T_{2}))-({\mathrm{rad}}(T_{i})-{\mathrm{\pi}}(T_{i}))\big{)}+\big{(}({\mathrm{rad}}(T_{3})-{\mathrm{\pi}}(T_{3}))-({\mathrm{rad}}(T_{j})-{\mathrm{\pi}}(T_{j}))\big{)}$
$\displaystyle\geq$ $\displaystyle 0\text{ if }1<i<j\leq s\text{ by
Lemma~{}\ref{lem:technical}.}$

It remains to compare $\ell_{1,2}$ and $\ell_{2,3}$ in the even case where
${\mathrm{\pi}}(k)=0$:

$\displaystyle\ell_{1,2}-\ell_{2,3}=((k_{1}-1)-{\mathrm{\pi}}(T_{1}))-((k_{3}-1)-{\mathrm{\pi}}(T_{3}))+{\mathrm{\pi}}(k)-1$
$\displaystyle=(k_{1}-{\mathrm{\pi}}(T_{1}))-(k_{3}-{\mathrm{\pi}}(T_{3}))-1\begin{cases}\geq
0,&\text{if }k_{1}-{\mathrm{\pi}}(T_{1})>k_{3}-{\mathrm{\pi}}(T_{3}),\\\
<0,&\text{otherwise}\end{cases}$

We are now ready to estimate the diameter of $T^{\prime}$ and, thus, the
radius. If $s=1$ (and therefore $t>0$) then

${\mathrm{diam}}(T^{\prime})=\max\\{{\mathrm{diam}}(T^{\prime}_{1}),\ell_{1},\dots,\ell_{t},{\mathrm{dist}}_{T^{\prime}}(v_{i},v_{j})\mid
1\leq i<j\leq t\\}.$

From the observations above, ${\mathrm{diam}}(T^{\prime})=\ell_{1}$. In Step
(ii.ii.2.), we see that $k=k_{1}+2(1-{\mathrm{\pi}}(T_{1}))$ and so

$\ell_{1}=k+k_{1}-{\mathrm{\pi}}(T_{1})-1=k+(k-2+2{\mathrm{\pi}}(T_{1}))-{\mathrm{\pi}}(T_{1})-1=2k-3+{\mathrm{\pi}}(T_{1}).$

Obviously, ${\mathrm{\pi}}(T^{\prime})=1-{\mathrm{\pi}}(T_{1})$, which means
that ${\mathrm{rad}}(T^{\prime})=k-1$. Note also that, since
$n\geq|V(G_{1})|+2$ (because $\\{u,v_{1}\\}\subseteq V(G)\setminus V(G_{1})$)

$k-1\leq|V(G_{1})|+(k-k_{1})\leq(n-2)+(2-2{\mathrm{\pi}}(T_{1}))\leq n.$

If $s\geq 2$ then let

$\displaystyle m_{1}$
$\displaystyle=\max\\{{\mathrm{diam}}(T^{\prime}_{1}),\dots,{\mathrm{diam}}(T^{\prime}_{s})\\},$
$\displaystyle m_{2}$ $\displaystyle=\max\\{\ell_{i,j}\mid 1\leq i<j\leq
s\\},$ $\displaystyle m_{3}$
$\displaystyle=\max\\{\ell_{1},\dots,\ell_{t}\\},$ $\displaystyle m_{4}$
$\displaystyle=\max\\{{\mathrm{dist}}_{T^{\prime}}(v_{i},v_{j})\mid 1\leq
i<j\leq t\\}.$

Then, apparently,
${\mathrm{diam}}(T^{\prime})=\max\\{m_{1},m_{2},m_{3},m_{4}\\}$ and, thus,

${\mathrm{diam}}(T^{\prime})=\begin{cases}\ell_{2,3},&\text{if }p=0\text{ and
}s>2\text{ and }k_{1}-{\mathrm{\pi}}(T_{1})=k_{3}-{\mathrm{\pi}}(T_{3}),\\\
\ell_{1,2},&\text{otherwise},\\\ \end{cases}$

according to the considerations above. In the first case, where

${\mathrm{diam}}(T^{\prime})=\ell_{2,3}=k-{\mathrm{\pi}}(k)+k_{2}-{\mathrm{\pi}}(T_{2})+k_{3}-{\mathrm{\pi}}(T_{3})-2,$

the value $k-{\mathrm{\pi}}(k)+k_{2}+k_{3}-2$ is even because of $p=0$, and,
therefore,
${\mathrm{\pi}}(T^{\prime})={\mathrm{\pi}}(T_{2})+{\mathrm{\pi}}(T_{3})-2{\mathrm{\pi}}(T_{2})\cdot{\mathrm{\pi}}(T_{3})$.
Since $k_{1}\geq k_{2}\geq k_{3}$ are of the same parity and because

$k_{1}-{\mathrm{\pi}}(T_{1})\geq k_{2}-{\mathrm{\pi}}(T_{2})\geq
k_{3}-{\mathrm{\pi}}(T_{3})=k_{1}-{\mathrm{\pi}}(T_{1}),$

it must be the case that $k_{1}=k_{2}=k_{3}$ and
${\mathrm{\pi}}(T_{1})={\mathrm{\pi}}(T_{2})={\mathrm{\pi}}(T_{3})$. Moreover,
Step (ii.ii.2.) sets
$k=k_{1}+k_{2}-2\cdot{\mathrm{\pi}}(T_{1})\cdot{\mathrm{\pi}}(T_{2})$ in this
case. Because $k_{1}=k_{3}$ and ${\mathrm{\pi}}(T_{1})={\mathrm{\pi}}(T_{3})$,
we get

$\displaystyle\ell_{2,3}$
$\displaystyle=k-2+(k_{1}+k_{2}-2\cdot{\mathrm{\pi}}(T_{1})\cdot{\mathrm{\pi}}(T_{2}))-({\mathrm{\pi}}(T_{2})+{\mathrm{\pi}}(T_{3})-2{\mathrm{\pi}}(T_{2})\cdot{\mathrm{\pi}}(T_{3}))=2k-2-{\mathrm{\pi}}(T^{\prime})$

and, hence, ${\mathrm{rad}}(T^{\prime})=k-1$. Moreover, since
$n\geq|V(G_{1})|+|V(G_{2})|+1$ (because $u\in V(G)\setminus(V(G_{1})\cup
V(G_{2}))$), we have

$\displaystyle(k-1)+(k-1)$
$\displaystyle\leq(|V(G_{1})|+(k-k_{1}))+(|V(G_{2})|+(k-k_{2}))$
$\displaystyle=(|V(G_{1})|+|V(G_{2})|)+(k-k_{1}-k_{2})+k$
$\displaystyle\leq(n-1)-2\cdot{\mathrm{\pi}}(T_{1})\cdot{\mathrm{\pi}}(T_{2})+k$
$\displaystyle\leq n+(k-1),$

which means that $k-1\leq n$.

In the other case, where

${\mathrm{diam}}(T^{\prime})=\ell_{1,2}=k+k_{1}-{\mathrm{\pi}}(T_{1})+k_{2}-{\mathrm{\pi}}(T_{2})-3,$

we distinguish between $p=0$ and $p=1$. If $p=0$ then $k+k_{1}+k_{2}-3$ is odd
and
${\mathrm{\pi}}(T^{\prime})=1-{\mathrm{\pi}}(T_{1})-{\mathrm{\pi}}(T_{2})+2\cdot{\mathrm{\pi}}(T_{1})\cdot{\mathrm{\pi}}(T_{2})$.
Moreover, Step (ii.ii.2.) sets
$k=k_{1}+k_{2}-2\cdot({\mathrm{\pi}}(T_{1})+{\mathrm{\pi}}(T_{2})-{\mathrm{\pi}}(T_{1})\cdot{\mathrm{\pi}}(T_{2}))$,
and we get

$\displaystyle\ell_{1,2}$ $\displaystyle=$ $\displaystyle
k-2+(k_{1}+k_{2}-2\cdot({\mathrm{\pi}}(T_{1})+{\mathrm{\pi}}(T_{2})-\cdot{\mathrm{\pi}}(T_{1})\cdot{\mathrm{\pi}}(T_{2}))-(1-{\mathrm{\pi}}(T_{1})-{\mathrm{\pi}}(T_{2})+2\cdot{\mathrm{\pi}}(T_{1})\cdot{\mathrm{\pi}}(T_{2}))$
$\displaystyle=$ $\displaystyle 2k-2-{\mathrm{\pi}}(T^{\prime}),$

which again means, ${\mathrm{rad}}(T^{\prime})=k-1$. Otherwise, if $p=1$ then
$k+k_{1}+k_{2}-3$ is even and
${\mathrm{\pi}}(T^{\prime})={\mathrm{\pi}}(T_{1})+{\mathrm{\pi}}(T_{2})-2\cdot{\mathrm{\pi}}(T_{1})\cdot{\mathrm{\pi}}(T_{2})$.
In this final case, Step (ii.ii.2.) defines
$k=k_{1}+k_{2}-1-2\cdot{\mathrm{\pi}}(T_{1})\cdot{\mathrm{\pi}}(T_{2}))$ and,
thus,

$\displaystyle\ell_{1,2}$ $\displaystyle=$ $\displaystyle
k-2+(k_{1}+k_{2}-1-2\cdot{\mathrm{\pi}}(T_{1})\cdot{\mathrm{\pi}}(T_{2}))-({\mathrm{\pi}}(T_{1})+{\mathrm{\pi}}(T_{2})-2\cdot{\mathrm{\pi}}(T_{1})\cdot{\mathrm{\pi}}(T_{2}))=2k-2-{\mathrm{\pi}}(T^{\prime})$

and we can conclude that ${\mathrm{rad}}(T^{\prime})=k-1$ holds in every case.
Similarly to the previous case, we also get

$\displaystyle(k-1)+(k-1)$
$\displaystyle\leq(|V(G_{1})|+(k-k_{1}))+(|V(G_{2})|+(k-k_{2}))$
$\displaystyle=(|V(G_{1})|+|V(G_{2})|)+(k-k_{1}-k_{2})+k$
$\displaystyle\leq(n-1)-(2\cdot{\mathrm{\pi}}(T_{1})\cdot{\mathrm{\pi}}(T_{2})+1)+k$
$\displaystyle\leq n+(k-1),$

and, again, $k-1\leq n$.

With $T^{\prime}$, the algorithm has created a $k$-leaf root of $H$ with
${\mathrm{rad}}(T^{\prime})=k-1\leq n$ and ${\mathrm{\pi}}(k)=p$. Step
(ii.ii.4.) extends $T^{\prime}$ to a tree $T$ by attaching the universal
vertex $u$ of $G$ as a leaf pendent to a center vertex of $T^{\prime}$.
Obviously, $T$ is a $k$-leaf root of $G$ with ${\mathrm{\pi}}(k)=p$ and
property (T1) ${\mathrm{rad}}(T)=k-1\leq n$ because
${\mathrm{dist}}_{T}(x,y)={\mathrm{dist}}_{T^{\prime}}(x,y)$ for all $x,y\in
V(H)=V(G)-u$ and

${\mathrm{dist}}_{T}(u,x)\leq{\mathrm{rad}}(T)+1={\mathrm{rad}}(T^{\prime})+1=(k-1)+1=k.$

Moreover, $T$ has property (T2) $d^{\mathrm{min}}_{T}=1+{\mathrm{\pi}}(T)$. If
${\mathrm{\pi}}(T)=0$ then the center of $T$ is a single vertex $z$, which is
also the min-max center. Since $z$ is adjacent to the leaf $u$, we get
$d^{\mathrm{min}}_{T}=1$. Otherwise, if ${\mathrm{\pi}}(T)=1$ then $T$ has two
center vertices $z_{1}$ and $z_{2}$ where, without loss of generality, $u$ is
attached to $z_{1}$. That makes $z_{2}$ the min-max center with distance
$d^{\mathrm{min}}_{T}=2$ to leaf $u$. This concludes the proof of Proposition
4.

With the following proposition, we summarize what we have so far and cover the
disconnected case.

###### Proposition 5

Let $G$ be a ccg on $n$ vertices and without true twins and let
$p\in\\{0,1\\}$ be a given parity. Then $(T,k)=\rho(G,p)$ provides a $k$-leaf
root $T$ of $G$ with ${\mathrm{\pi}}(k)=p$ and $k\leq n+1$. If $G$ is
connected then $(T,k)$ satisfies (T1) and (T2).

After the Propositions 3 and 4, it remains to handle disconnected input. In
this case, $G$ has $s\geq 0$ non-trivial connected components
$G_{1},\ldots,G_{s}$ and $t\geq 0$ isolated vertices $v_{1},\ldots,v_{t}$ such
that $s+t\geq 2$.

If $s=0$ then $G$ consists of $n\geq 2$ isolated vertices and, thus, Step
(iii.iii.2.) sets $k=2$ for even parity and $k=3$, otherwise. Then, by Lemma
5, Step (iii.iii.3.) returns a $k$-leaf root $T$ of $G$.

For $s>0$, every $G_{i}$ is a connected ccg without true twins. By Proposition
4, Step (iii.iii.1.) provides a $k_{i}$-leaf root $T_{i}$ of parity $p$ for
every $G_{i}$, $1\leq i\leq s$. The value assigned to $k$ in Step (iii.iii.2.)
is the maximum $k_{m}=\max\\{k_{1},\dots,k_{s}\\}$. Since
$k_{m}\leq|V(G_{m})|+1$, we have $k\leq m+1$. According to Lemma 4, the same
step produces a $k$-leaf root
$T^{\prime}_{i}=\eta\left(T_{i},\tfrac{k-k_{i}}{2}\right)$ of $G_{i}$ for all
$i\in\\{1,\dots,s\\}$. Finally, by Lemma 5, Step (iii.iii.3.) returns a
$k$-leaf root $T$ of $G$. This proves Proposition 5.

The following, last proposition finalized the proof of Theorem 3.1 because it
shows that the $k$-leaf root $T$ returned by $\rho(G,p)$ is optimal with
respect to both, the value of $k$ and the diameter of $T$.

###### Proposition 6

Let $G$ be a ccg without true twins and let $p\in\\{0,1\\}$ be a given parity.
Then $(T,k)=\rho(G,p)$ provides a $k$-leaf root $T$ of $G$ that is _optimal_
for parity $p$ (hence, ${\mathrm{\pi}}(k)=p$). If $G$ is connected then
$(T,k)$ satisfies (T3).

That $(T,k)=\rho(G,p)$ provides a $k$-leaf root $T$ of $G$ with
${\mathrm{\pi}}(k)=p$ has just been established. To prove Proposition 6, we
only need to show that $T$ fulfills (T3) for connected input graphs $G$ and
that $k$ is always parity-optimal.

We begin with the proof of (T3) and, like for Proposition 5, this works by
induction on the vertex number of $G$. Again, for the base case, Proposition 3
handles the star with two leaves, the smallest connected ccg without true
twins and more than one vertex. Proposition 3 settles the theorem for all
stars.

Now, let $G$ have more than three vertices. That $G$ is connected and not a
star leads us to Case ii. of $\rho$, again. Borrowing the argumentation from
the proof of Proposition 5, we immediately get that

  * •

$G$ has a unique universal cutvertex $u$ and $H=G-u$ has $s\geq 1$ non-trivial
connected components $G_{1},\ldots,G_{s}$, each a ccg without true twins, and
$t\geq 0$ isolated vertices $v_{1},\ldots,v_{t}$ such that $s+t\geq 2$,

  * •

by induction hypothesis, Step (ii.ii.1.) provides $k_{i}$-leaf roots $T_{i}$
of parity $p$ for all $G_{i},1\leq i\leq s$, which are optimal and satisfy
(T3), here,

  * •

$k_{1}\geq k_{2}\geq\dots\geq k_{s}$, if, without loss of generality, we
assume

${\mathrm{diam}}(T_{1})\geq{\mathrm{diam}}(T_{2})\geq\dots\geq{\mathrm{diam}}(T_{s}),$

  * •

Step (ii.ii.3.) produces $k$-leaf roots
$T^{\prime}_{i}=\eta\left(T_{i},\tfrac{k-k_{i}}{2}\right)$ of all $G_{i},1\leq
i\leq s$ with

$\displaystyle k$
$\displaystyle=\begin{cases}k_{1}+2(1-{\mathrm{\pi}}(T_{1})),&\text{if
}s=1,\\\
k_{1}+k_{2}-1-2\cdot{\mathrm{\pi}}(T_{1})\cdot{\mathrm{\pi}}(T_{2})&\text{if
}s\geq 2\text{ and }p=1,\\\
k_{1}+k_{2}-2\cdot{\mathrm{\pi}}(T_{1})\cdot{\mathrm{\pi}}(T_{2}),&\text{if
}s>2,p=0\text{ and
}k_{1}-{\mathrm{\pi}}(T_{1})=k_{3}-{\mathrm{\pi}}(T_{3}),\\\
k_{1}+k_{2}-2\cdot({\mathrm{\pi}}(T_{1})+{\mathrm{\pi}}(T_{2})-{\mathrm{\pi}}(T_{1})\cdot{\mathrm{\pi}}(T_{2})),&\text{otherwise,}\end{cases}$
$\displaystyle{\mathrm{diam}}(T^{\prime}_{i})$
$\displaystyle={\mathrm{diam}}(T_{i})+k-k_{i},\text{ and}$
$\displaystyle{\mathrm{rad}}(T^{\prime}_{i})$
$\displaystyle={\mathrm{rad}}(T_{i})+\tfrac{k-k_{i}}{2}=\tfrac{k+k_{i}}{2}-1,$

  * •

Step (ii.ii.3.) produces
$T^{\prime}=\mu(k,T^{\prime}_{1},\dots,T^{\prime}_{s},v_{1},\dots,v_{t})$ with

${\mathrm{diam}}(T^{\prime})=\begin{cases}k+k_{1}-{\mathrm{\pi}}(T_{1})-1,&\text{if
}s=1,\\\ k+k_{2}-{\mathrm{\pi}}(T_{2})+k_{3}-{\mathrm{\pi}}(T_{3})-2,&\text{if
}s>2\text{ and }p=0\text{ and
}k_{1}-{\mathrm{\pi}}(T_{1})=k_{3}-{\mathrm{\pi}}(T_{3}),\\\
k+k_{1}-{\mathrm{\pi}}(T_{1})+k_{2}-{\mathrm{\pi}}(T_{2})-3,&\text{otherwise,
and}\end{cases}$

  * •

$(T,k)=\rho(G,p)$, as assembled in Step (ii.ii.4.), represents a $k$-leaf root
of $G$ with ${\mathrm{diam}}(T)={\mathrm{diam}}(T^{\prime})$.

Next, consider an arbitrary $k^{\prime}$-leaf root $R$ of $G$ and, for all
$i\in\\{1,\dots,s\\}$, let $R_{i}$ be the smallest subtree of $R$ with leaf
set $V(G_{i})$. Observe that the $R_{i}$-trees are pairwise vertex-disjoint.
Then $R_{i}$ is a $k^{\prime}$-leaf root of $G_{i}$ and, since $T_{i}$ has
(T3),

${\mathrm{diam}}(R_{i})\geq{\mathrm{diam}}(T_{i})+k^{\prime}-k_{i}=({\mathrm{diam}}(T_{i})-k+k_{i})+k^{\prime}-k_{i}={\mathrm{diam}}(T^{\prime}_{i})+k^{\prime}-k.$

Let $u_{i}$ be the unique universal vertex of $G_{i}$ by Proposition 2. By
Lemma 3, there is a center vertex $z_{i}$ of $R_{i}$ with
${\mathrm{dist}}_{R_{i}}(u_{i},z_{i})\leq k^{\prime}-{\mathrm{rad}}(R_{i})$.
Let $x_{i}$ and $y_{i}$ be the two leaves of a diametral path in $R_{i}$.
Then, the center vertex $z_{i}$ of $T_{i}$ is on the $x_{i},y_{i}$-path and
${\mathrm{dist}}_{R_{i}}(u_{i},z_{i})={\mathrm{dist}}_{R}(u_{i},z_{i})$.

Suppose $s=1$. Then ${\mathrm{dist}}_{R}(z_{1},v_{1})>{\mathrm{rad}}(R_{1})$
for, otherwise,

${\mathrm{dist}}_{R}(u_{1},v_{1})\leq{\mathrm{dist}}_{R}(u_{1},z_{1})+{\mathrm{dist}}_{R}(z_{1},v_{1})\leq(k^{\prime}-{\mathrm{rad}}(R_{1}))+{\mathrm{rad}}(R_{1})=k^{\prime},$

and $u_{1}$ and $v_{1}$ would be adjacent in $G$. In $R$, the longest path
between $v_{1}$ and a vertex in $\\{x_{1},y_{1}\\}$ must contain $z_{1}$, and
it has the length $\ell$ that fulfills

$\ell\geq{\mathrm{dist}}_{R}(v_{1},z_{1})+{\mathrm{rad}}(R_{1})>2{\mathrm{rad}}(R_{1})\geq{\mathrm{diam}}(R_{1})\geq{\mathrm{diam}}(T^{\prime}_{1})+k^{\prime}-k.$

Hence, ${\mathrm{diam}}(R)>{\mathrm{diam}}(T^{\prime}_{1})+k^{\prime}-k$ and
we conclude

$\displaystyle{\mathrm{diam}}(R)$
$\displaystyle\geq{\mathrm{diam}}(T^{\prime}_{1})+k^{\prime}-k+1=(2{\mathrm{rad}}(T^{\prime}_{1})-{\mathrm{\pi}}(T^{\prime}_{1}))+k^{\prime}-k+1$
$\displaystyle=(k+k_{1}-2)-{\mathrm{\pi}}(T^{\prime}_{1})+k^{\prime}-k+1$
$\displaystyle=(k+k_{1}-{\mathrm{\pi}}(T_{1})-1)+k^{\prime}-k$
$\displaystyle={\mathrm{diam}}(T)+k^{\prime}-k,$

as claimed.

If $s\geq 2$ then
${\mathrm{dist}}_{R}(z_{i},z_{j})\geq{\mathrm{rad}}(R_{i})+{\mathrm{rad}}(R_{j})-k^{\prime}+1$
for all $1\leq i<j\leq s$ since, otherwise,

$\displaystyle{\mathrm{dist}}_{R}(u_{i},u_{j})$
$\displaystyle\leq{\mathrm{dist}}_{R}(u_{i},z_{i})+{\mathrm{dist}}_{R}(z_{i},z_{j})+{\mathrm{dist}}_{R}(z_{j},u_{j})$
$\displaystyle\leq(k^{\prime}-{\mathrm{rad}}(R_{i}))+({\mathrm{rad}}(R_{i})+{\mathrm{rad}}(R_{j})-k^{\prime})+(k^{\prime}-{\mathrm{rad}}(R_{j}))=k^{\prime},$

and $u_{i}$ and $u_{j}$ would be adjacent in $G$. In $R$, the longest path
going between a vertex in $\\{x_{i},y_{i}\\}$ and a vertex in
$\\{x_{j},y_{j}\\}$ contains $z_{i}$ and $z_{j}$. The length $\ell_{i,j}$ of
this path fulfills

$\displaystyle\ell_{i,j}$
$\displaystyle\geq{\mathrm{rad}}(R_{i})+{\mathrm{dist}}_{R}(z_{i},z_{j})+{\mathrm{rad}}(R_{j})$
$\displaystyle\geq{\mathrm{rad}}(R_{i})+\big{(}{\mathrm{rad}}(R_{i})+{\mathrm{rad}}(R_{j})-k+1\big{)}+{\mathrm{rad}}(R_{j})$
$\displaystyle={\mathrm{diam}}(R_{i})+{\mathrm{\pi}}(R_{i})+{\mathrm{diam}}(R_{j})+{\mathrm{\pi}}(R_{j})-k^{\prime}+1.$

Because ${\mathrm{diam}}(R)\geq\ell_{1,2}$ and ${\mathrm{\pi}}(R_{1})\geq 0$
and ${\mathrm{\pi}}(R_{2})\geq 0$, we find that

$\displaystyle{\mathrm{diam}}(R)$
$\displaystyle\geq{\mathrm{diam}}(R_{1})+{\mathrm{diam}}(R_{2})-k^{\prime}+1$
$\displaystyle\geq({\mathrm{diam}}(T_{1})+k^{\prime}-k_{1})+({\mathrm{diam}}(T_{2})+k^{\prime}-k_{2})-k^{\prime}+1$
$\displaystyle=(2{\mathrm{rad}}(T_{1})-{\mathrm{\pi}}(T_{1})-k_{1})+(2{\mathrm{rad}}(T_{2})-{\mathrm{\pi}}(T_{2})-k_{2})+k^{\prime}+1$
$\displaystyle=(2k_{1}-2-{\mathrm{\pi}}(T_{1})-k_{1})+(2k_{2}-2-{\mathrm{\pi}}(T_{2})-k_{2})+k^{\prime}+(k-k)+1$
$\displaystyle=(k+k_{1}-{\mathrm{\pi}}(T_{1})+k_{2}-{\mathrm{\pi}}(T_{2})-3)+k^{\prime}-k.$

Hence, if $p=1$ or $s=2$ or ($s>2$ and)
$k_{1}-{\mathrm{\pi}}(T_{1})>k_{3}-{\mathrm{\pi}}(T_{3})$ then (as
${\mathrm{diam}}(T)=k+k_{1}-{\mathrm{\pi}}(T_{1})+k_{2}-{\mathrm{\pi}}(T_{2})-3$,
here) we already get

${\mathrm{diam}}(R)\geq{\mathrm{diam}}(T)+k^{\prime}-k.$

In the remaining case, we have $p=0$ and $s>2$ and
$k_{1}-{\mathrm{\pi}}(T_{1})=k_{3}-{\mathrm{\pi}}(T_{3})$. Like in the proof
of Theorem 5, we can conclude that $k_{1}=k_{2}=k_{3}$ and
${\mathrm{\pi}}(T_{1})={\mathrm{\pi}}(T_{2})={\mathrm{\pi}}(T_{3})$, here.
Thus, ${\mathrm{diam}}(T_{1})={\mathrm{diam}}(T_{2})={\mathrm{diam}}(T_{3})$
and
${\mathrm{diam}}(T^{\prime}_{1})={\mathrm{diam}}(T^{\prime}_{2})={\mathrm{diam}}(T^{\prime}_{3})$,
too. If we write $\delta={\mathrm{diam}}(T^{\prime}_{1})+k^{\prime}-k$ then
${\mathrm{diam}}(R_{i})\geq\delta$ for all $i\in\\{1,2,3\\}$.

Firstly, we show that at least one of the three length
$\ell_{1,2},\ell_{1,3},\ell_{2,3}$ is at least $2\delta-k^{\prime}+2$. If
${\mathrm{diam}}(R_{i})+{\mathrm{\pi}}(R_{i})>\delta$ for some
$i\in\\{1,2,3\\}$, then

$\displaystyle\ell_{i,j}$
$\displaystyle\geq{\mathrm{diam}}(R_{i})+{\mathrm{\pi}}(R_{i})+{\mathrm{diam}}(R_{j})+{\mathrm{\pi}}(R_{j})-k^{\prime}+1$
$\displaystyle\geq(\delta+1)+\delta-k^{\prime}+1$ $\displaystyle\geq
2\delta-k^{\prime}+2$

for all $j\in\\{1,2,3\\}\setminus\\{i\\}$ and we are done, already. Therefore,
consider that ${\mathrm{diam}}(R_{i})+{\mathrm{\pi}}(R_{i})\leq\delta$ for all
$i\in\\{1,2,3\\}$. Then, since and
$\delta\leq{\mathrm{diam}}(R_{i})\leq\delta-{\mathrm{\pi}}(R_{i})$ for all
$i\in\\{1,2,3\\}$, we have

${\mathrm{diam}}(R_{1})+{\mathrm{\pi}}(R_{1})={\mathrm{diam}}(R_{2})+{\mathrm{\pi}}(R_{2})={\mathrm{diam}}(R_{3})+{\mathrm{\pi}}(R_{3})=\delta.$

Hence,
${\mathrm{rad}}(R_{1})={\mathrm{rad}}(R_{2})={\mathrm{rad}}(R_{3})=\tfrac{\delta}{2}$,
which implies that $\delta$ is even. If
${\mathrm{dist}}_{R}(z_{i},z_{j})\geq\delta-k^{\prime}+2$ for any
$i,j\in\\{1,2,3\\}$, then

$\displaystyle\ell_{i,j}$
$\displaystyle\geq{\mathrm{rad}}(R_{i})+{\mathrm{dist}}_{R}(z_{i},z_{j})+{\mathrm{rad}}(R_{j})$
$\displaystyle\geq\tfrac{\delta}{2}+(\delta-k^{\prime}+2)+\tfrac{\delta}{2}$
$\displaystyle=2\delta-k^{\prime}+2$

and done, again. So, finally, assume that
${\mathrm{dist}}_{R}(z_{i},z_{j})\leq\delta-k^{\prime}+1$ for all
$i\in\\{1,2,3\\}$. Then, since we have

${\mathrm{dist}}_{R}(z_{i},z_{j})\geq{\mathrm{rad}}(R_{i})+{\mathrm{rad}}(R_{j})-k^{\prime}+1=\tfrac{\delta}{2}+\tfrac{\delta}{2}-k^{\prime}+1$

from before,
${\mathrm{dist}}_{R}(z_{1},z_{2})={\mathrm{dist}}_{R}(z_{1},z_{3})={\mathrm{dist}}_{R}(z_{2},z_{3})=\delta-k^{\prime}+1$.
Let $w$ be the last vertex $w$ on the $z_{1},z_{2}$-path in $R$ that is
closest to $z_{3}$ and let $\delta_{i}$ be the distances between $z_{i}$ and
$w$ for all $i\in\\{1,2,3\\}$. Then, for all $1\leq i<j\leq 3$, it must be

$\delta_{i}+\delta_{j}={\mathrm{dist}}_{R}(z_{i},z_{j})=\delta-k^{\prime}+1.$

Solving the system of the three linear equations above yields

$\delta_{1}=\delta_{2}=\delta_{3}=\tfrac{1}{2}(\delta-k^{\prime}+1),$

which implies that $k^{\prime}$ is odd, a contradiction to
${\mathrm{\pi}}(k^{\prime})={\mathrm{\pi}}(k)=p=0$.

So at least one length, say $\ell_{1,2}$, is at least $2\delta-k^{\prime}+2$.
This means that

$\displaystyle{\mathrm{diam}}(R)$ $\displaystyle\geq\ell_{1,2}\geq
2\delta-k^{\prime}+2$
$\displaystyle=({\mathrm{diam}}(T^{\prime}_{1})+k^{\prime}-k)+({\mathrm{diam}}(T^{\prime}_{3})+k^{\prime}-k)-k^{\prime}+2$
$\displaystyle=({\mathrm{diam}}(T_{1})+k-k_{1}+k^{\prime}-k)+({\mathrm{diam}}(T_{3})+k-k_{3}+k^{\prime}-k)-k^{\prime}+2$
$\displaystyle=(2{\mathrm{rad}}(T_{1})-{\mathrm{\pi}}(T_{1})+k^{\prime}-k_{1})+(2{\mathrm{rad}}(T_{3})-{\mathrm{\pi}}(T_{3})+k^{\prime}-k_{3})-k^{\prime}+2$
$\displaystyle=(2{\mathrm{rad}}(T_{1})-{\mathrm{\pi}}(T_{1})-k_{1})+(2{\mathrm{rad}}(T_{3})-{\mathrm{\pi}}(T_{3})-k_{3})+k^{\prime}+(k-k)+2$
$\displaystyle=k+(k_{1}-2-{\mathrm{\pi}}(T_{1}))+(k_{3}-2-{\mathrm{\pi}}(T_{3}))+k^{\prime}-k+2$
$\displaystyle=(k+k_{1}-{\mathrm{\pi}}(T_{1})+k_{3}-{\mathrm{\pi}}(T_{3})-2)+k^{\prime}-k.$

Because here,
${\mathrm{diam}}(T)=k+k_{1}-{\mathrm{\pi}}(T_{1})+k_{3}-{\mathrm{\pi}}(T_{3})-2$,
we have now shown that
${\mathrm{diam}}(R)\geq{\mathrm{diam}}(T)+k^{\prime}-k$.

It remains to prove that the value of $k$ in $(T,k)=\rho(G,p)$ is optimal with
respect to leaf roots of $G$ with parity $p$. For the connected case, this can
be seen as follows. By Corollary 1, $2k^{\prime}-2\geq{\mathrm{diam}}(R)$
holds for every $k^{\prime}$-leaf roots $R$ of $G$. Hence,

$2k^{\prime}-2\geq{\mathrm{diam}}(R)\geq{\mathrm{diam}}(T)+k^{\prime}-k\geq
2k-3+k^{\prime}-k=k+k^{\prime}-3,$

since ${\mathrm{diam}}(T)=2{\mathrm{rad}}(T)-{\mathrm{\pi}}(T)\geq
2(k-1)-1=2k-3$. Now, $2k^{\prime}-2\geq k+k^{\prime}-3$ implies that
$k^{\prime}\geq k-1$ and, because both, $k$ and $k^{\prime}$, have the same
parity, $k^{\prime}\geq k$. That is, $T$ is an optimal $k$-leaf root of $G$
with parity $p$.

Finally, let $G$ be a disconnected graph with $s\geq 0$ non-trivial connected
components $G_{1},\dots,G_{s}$ and $t\geq 0$ isolated vertices
$v_{1},\dots,v_{t}$ such that $s+t\geq 2$. By Theorem 5, $(T,k)=\rho(G,k)$
results from finding
$(T_{1},k_{1})=\rho(G_{1},p),\dots,(T_{s},k_{s})=\rho(G_{s},p)$ in Step
(iii.iii.1.) and assembling them to a $k$-leaf root $T$ for $G$ with
$k=\max\\{k_{1},\dots,k_{s},p+2\\}$ in the Steps (iii.iii.2.) and
(iii.iii.3.). After handling the connected case above, we know that $T_{i}$ is
an optimal $k_{i}$-leaf root of $G_{i}$ with parity $p$ for all
$i\in\\{1,\dots,s\\}$.

Clearly, if $s=0$ then a $(p+2)$-leaf root is the best possible for parity
$p$, and we are done. Otherwise, assume, without loss of generality, that
$k=k_{1}$. Moreover, let $R$ be a $p$-parity $k^{\prime}$-leaf root of $G$
and, for all $i\in\\{1,\dots,s\\}$, let $R_{i}$ be the smallest subtree of $R$
with leaf set $V(G_{i})$. Then $R_{1}$ is a $k^{\prime}$-leaf root of $G_{1}$.
Since $k_{1}$ is optimal for $G_{1}$, we have that $k^{\prime}\geq k_{1}=k$,
thus, $T$ is an optimal $k$-leaf root of $G$ with parity $p$. This proves
Proposition 6 and, with it, also Theorem 3.1. ∎

Lemma 6. _Let $T$ be a compressed tree with $n$ leaves and with explicitly
given min-max center $z$, center $Z$, diameter ${\mathrm{diam}}(T)$, and leaf-
distance $d^{\mathrm{min}}_{T}$. For all integers $\delta\geq 0$, the
compressed tree $T^{\prime}=\eta(T,\delta)$ can be computed in ${\cal O}(n)$
time together with min-max center $z^{\prime}$, center $Z^{\prime}$, diameter
${\mathrm{diam}}(T^{\prime})$, and leaf distance
$d^{\mathrm{min}}_{T^{\prime}}$ of $T^{\prime}$. _

###### Proof

By definition, $T^{\prime}$ is obtained from $T$ by replacing all $n$ pendant
edges with new paths of length $\delta+1$, each. In the compressed encoding,
this takes just $n$ modifications of the weight of edges. More precisely, if
$v(\ell)x$ is a pendent edge of $T$ representing a path of length $\ell$ that
ends at leaf $x$ (where we simply take $\ell=1$ for an unweighted edge) then
$T^{\prime}$ has the same pendent edge $v(\ell^{\prime})x$ with the new weight
$\ell^{\prime}=\ell+\delta$. The $n$ constant-time modifications take ${\cal
O}(n)$ time, altogether.

According to Lemma 4, $z^{\prime}=z$, $Z^{\prime}=Z$,
${\mathrm{diam}}(T^{\prime})={\mathrm{diam}}(T)+2\delta$ and
$d^{\mathrm{min}}_{T^{\prime}}=d^{\mathrm{min}}_{T}+\delta$, which takes just
constant time to compute. ∎

Lemma 7. _Let $s\geq 0$ be an integer and, for all $i\in\\{1,\dots,s\\}$, let
$T_{i}$ be a given, compressed tree with explicitly given min-max center
$z_{i}$, center $Z_{i}$, diameter ${\mathrm{diam}}(T_{i})$, and leaf-distance
$d^{\mathrm{min}}_{T_{i}}$. For all integers $k\geq 2$ and vertices
$v_{1},\dots,v_{t}$, the merged compressed tree
$T^{\prime}=\mu(k,T_{1},\dots,T_{s},v_{1},\dots,v_{t})$ with center
$Z^{\prime}$ and diameter ${\mathrm{diam}}(T^{\prime})$ can be computed in
${\cal O}(s+t)$ time. _

###### Proof

According to definition, the computation of $T^{\prime}$ by $\mu$ starts with
finding the critical index $m$, which is the smallest number in
$\\{1,\dots,s\\}$ with
$d^{\mathrm{min}}_{T_{m}}=\min\\{d^{\mathrm{min}}_{T_{i}}\mid 1\leq i\leq
s\\}$. Since $d^{\mathrm{min}}_{T_{i}}$ is explicitly known for all given
trees, $m$ is found after iterating the input once in ${\cal O}(s)$ time.

Then, every tree $T_{i},1\leq i\leq s$ is attached at $z_{i}$ to a new vertex
$c$ by a path of at most
$\tfrac{k-{\mathrm{\pi}}(k)}{2}+1-d^{\mathrm{min}}_{T_{i}}$ edges and every
vertex $v_{j},1\leq j\leq t$ is attached to $c$ with a path of length
$\tfrac{k-{\mathrm{\pi}}(k)}{2}+1$. Each of these paths is represented by one
edge of the respective weight and, hence, this takes ${\cal O}(s+t)$ time.

It remains to show that $Z^{\prime}$ and ${\mathrm{diam}}(T^{\prime})$ can be
computed alongside $T^{\prime}$ without consuming essentially more computing
time. Both parameters require the identification of a diametral path in
$T^{\prime}$. We recall that every diametral path $P$ connects two leaves of
the tree $T^{\prime}$ and, therefore, is either entirely included in one of
the trees $T_{1},\dots,T_{s}$ or contains $c$ and connects leaves that stem
from different input trees or vertices $v_{1},\dots,v_{t}$. To be able to
cover the first case, we search a tree $T_{a}$ with
${\mathrm{diam}}(T_{a})=\min\\{{\mathrm{diam}}(T_{i})\mid 1\leq i\leq s\\}$.
This works in ${\cal O}(s)$ time since the diameters are given. If, at the
end, $P$ turns out to be part of $T_{a}$ then $Z^{\prime}=Z_{a}$ and
${\mathrm{diam}}(T^{\prime})={\mathrm{diam}}(T_{a})$, which is computed in
${\cal O}(1)$ time.

For the other possibility, we firstly think of the case where $P$ connects two
leaves $v_{i}$ and $v_{j}$, $1\leq i<j\leq t$. Then, obviously,
${\mathrm{diam}}(T^{\prime})=k-{\mathrm{\pi}}(k)+2\geq{\mathrm{diam}}(T_{a})$
and $Z^{\prime}=\\{c\\}$, which can be decided and computed in ${\cal O}(1)$
time.

Secondly, one or both end vertices of $P$ may be leaves of the trees
$T_{1},\dots,T_{s}$. To efficiently find $P$ under this condition, we hook
additional computations into the iteration of these trees during the
evaluation of the $\mu$-operation. More precisely, while a tree $T_{i}$ is
attached to $c$ by a path of length $p_{i}$ (that is,
$p_{i}=\tfrac{k+{\mathrm{\pi}}(k)}{2}-d^{\mathrm{min}}_{T_{i}}$ for $i=m$ and,
otherwise, $p_{i}=\tfrac{k-{\mathrm{\pi}}(k)}{2}+1-d^{\mathrm{min}}_{T_{i}}$),
we memorize the $T^{\prime}$-distance

$d_{i}=\max\\{{\mathrm{dist}}_{T^{\prime}}(c,v)\mid v\text{ is leaf in
}T_{i}\\}=p_{i}+{\mathrm{rad}}(T_{i})=p_{i}+\left\lceil\tfrac{{\mathrm{diam}}(T_{i})}{2}\right\rceil$

between $c$ and a farthest leaf of $T_{i}$. As ${\mathrm{diam}}(T_{i})$ is
known in advance for all $i\in\\{1,\dots,s\\}$, this takes just ${\cal O}(1)$
additional time per iteration and, thus, ${\cal O}(s)$ time in total. We also
define

$d_{0}=\begin{cases}{\mathrm{dist}}_{T^{\prime}}(c,v_{1})=\tfrac{k-{\mathrm{\pi}}(k)}{2}+1,&\text{if
}t>0,\\\ 0,&\text{otherwise},\end{cases}$

the $T^{\prime}$-distance between $c$ and any present leaf
$v_{1},\dots,v_{t}$. Observe for later that, if $t>0$ then

$\displaystyle d_{i}-d_{0}$
$\displaystyle=p_{i}+{\mathrm{rad}}(T_{i})-\tfrac{k-{\mathrm{\pi}}(k)}{2}+1$
$\displaystyle\geq\tfrac{k+{\mathrm{\pi}}(k)}{2}-d^{\mathrm{min}}_{T_{i}}+{\mathrm{rad}}(T_{i})-\tfrac{k-{\mathrm{\pi}}(k)}{2}+1$
$\displaystyle\geq\tfrac{(k+{\mathrm{\pi}}(k))-(k-{\mathrm{\pi}}(k))}{2}+1\text{
since }d^{\mathrm{min}}_{T_{i}}\leq{\mathrm{rad}}(T_{i})$
$\displaystyle={\mathrm{\pi}}(k)+1\geq 1,$

hence, $d_{i}>d_{0}$ for all $i\in\\{1,\dots,s\\}$.

After the evaluation of $\mu$ and the associated completion of $T^{\prime}$,
we determine values $i_{1}$ and $i_{2}$ such that

$d_{i_{1}}=\max\\{d_{i}\mid 0\leq i\leq s\\}\text{ and
}d_{i_{2}}=\max\\{d_{i}\mid 0\leq i\leq s,i\not=i_{1}\\},$

which takes ${\cal O}(s)$ time. If a diametral path $P$ of $T^{\prime}$ runs
through $c$ and has at least one end vertex in one of the trees
$T_{1},\dots,T_{s}$ then, obviously, the length of this path is
$d=d_{i_{1}}+d_{i_{2}}$. We can detect this situation in ${\cal O}(1)$ time by
checking $d>{\mathrm{diam}}(T_{a})$ and $t>1\Rightarrow
d>k-{\mathrm{\pi}}(k)+2$. In this case, we infer that
${\mathrm{diam}}(T^{\prime})=d$ and $Z^{\prime}$ is on $P$. More precisely, if
$Z^{\prime}=\\{z^{\prime}_{1},z^{\prime}_{2}\\}$ (with
$z^{\prime}_{1}=z^{\prime}_{2}$ if ${\mathrm{\pi}}(T^{\prime})=1$) then
$Z^{\prime}$ is situated on the longer subpath of $P$ with $z^{\prime}_{1}$ at
distance $\delta_{1}=\left\lceil\tfrac{d_{i_{1}}-d_{i_{2}}}{2}\right\rceil$
from $c$ and $z^{\prime}_{2}$ at distance
$\delta_{2}=\left\lfloor\tfrac{d_{i_{1}}-d_{i_{2}}}{2}\right\rfloor$.

To conclude the proof, we show that $Z^{\prime}$ is situated on the recently
inserted weighted edge $c(p_{i_{1}})z_{i_{1}}$, or more precisely,
$p_{i_{1}}\geq\delta_{1}\geq\delta_{2}\geq 0$. That $\delta_{2}\geq 0$ holds
since, otherwise, $d_{i_{1}}<d_{i_{2}}$. Similarly, we note that, if one of
the end vertices of $P$ is a leaf of $v_{1},\dots,v_{t}$ then $i_{2}=0$ since,
otherwise, $d_{0}=d_{i_{1}}<d_{i_{2}}$. So, $i_{1}$ is in $\\{1,\dots,s\\}$,
and we further observe that

$2{\mathrm{rad}}(T_{i_{1}})-{\mathrm{\pi}}(T_{i_{1}})={\mathrm{diam}}(T_{i_{1}})\leq{\mathrm{diam}}(T_{a})<d_{i_{1}}+d_{i_{2}}=p_{i_{1}}+{\mathrm{rad}}(T_{i_{1}})+d_{i_{2}},$

because $T_{a}$ has the largest diameter among the given $s$ trees. This means
that ${\mathrm{rad}}(T_{i_{1}})\leq p_{i_{1}}+d_{i_{2}}$. Using this for the
estimation of $\delta_{1}$, we get

$\displaystyle\delta_{1}$
$\displaystyle=\left\lceil\tfrac{d_{i_{1}}-d_{i_{2}}}{2}\right\rceil\leq\tfrac{p_{i_{1}}+{\mathrm{rad}}(T_{i_{1}})-d_{i_{2}}}{2}\leq\tfrac{p_{i_{1}}+(p_{i_{1}}+d_{i_{2}})-d_{i_{2}}}{2}$
$\displaystyle=p_{i_{1}}.$

Hence, if $\delta_{1}=\delta_{2}=0$ then $z^{\prime}_{1}=z^{\prime}_{2}=c$. If
$\delta_{1}=p_{i_{1}}$ then $z^{\prime}_{1}=z_{i_{1}}$ and, if
$\delta_{1}>\delta_{2}$ in this case, then the edge $c(p_{i_{1}})z_{i_{1}}$ is
split into the weighted edge $c(p_{i_{1}}-1)z^{\prime}_{2}$ and the edge
$z^{\prime}_{2}z^{\prime}_{1}$. Otherwise, if also
${\mathrm{\pi}}(T^{\prime})=0$, then the center
$z^{\prime}_{1}=z^{\prime}_{2}$ is inserted by splitting the edge
$c(p_{i_{1}})z_{i_{1}}$ into the weighted edges $c(\delta_{1})z^{\prime}_{1}$
and $z^{\prime}_{1}(p_{i_{1}}-\delta_{1})z_{i_{1}}$. In the final case,
$c(p_{i_{1}})z_{i_{1}}$ is replaced by inserting the center edge
$z^{\prime}_{1}z^{\prime}_{2}$ between $c(\delta_{2})z^{\prime}_{2}$ and
$z^{\prime}_{1}(p_{i_{1}}-\delta_{1})z_{i_{1}}$. Altogether, this implies that
$Z^{\prime}$ and ${\mathrm{diam}}(T^{\prime})$ are always found in ${\cal
O}(s)$ time. ∎

Theorem 4.1. _Given a chordal cograph $G$ on $n$ vertices and $m$ edges and a
parity $p$ (either odd or even), a (compressed) $\kappa$-leaf root of $G$ with
minimum integer $\kappa$ of parity $p$ can be computed in ${\cal O}(n+m)$
time. _

###### Proof

Let $G$ be a ccg and $p\in\\{0,1\\}$ a parity. We can assume that $G$ is free
of true twins as, otherwise, we can remove $x$ for every pair $x,y$ of true
twins in $G$ in linear time and, when $(T,k)$ has been computed, insert every
$x$ pendant to the parent of the corresponding twin leaf $y$ into $T$. The
cotree ${\cal T}$ of $G$ is computed in Line 1, which works on linear time
${\cal O}(n+m)$ as discussed in Section 2.

We begin with connected input graphs and use complete induction on $n$ to show
that, then, Algorithm 1 puts $(T,k)=\rho(G,p)$ on top of the stack ${\cal S}$
before finishing the last visited node of ${\cal T}$ by the post-order-loop in
Lines 1 to 1, which requires ${\cal O}(n)$ steps. Since $G$ is connected and
free of true twins, the induction start is at $n=3$ with $G$ the star with
center $u$ and two leaves $v_{1},v_{2}$. For any star with leaves
$v_{1},\dots,v_{t}$, the cotree has a 1-root $X$ with leaf child $u$ and a
0-child that has the leaf-children $v_{1},\dots,v_{t}$, only. This means,
Algorithm 1 iterates just one 1-node (the root $X$), heads directly into Line
1, and, accordingly, handles this case like Case i. of the $\rho$-operation.
Afterwards, it pushes $(T,k)=\rho(G,p)$ on top of the stack ${\cal S}$ before
the for-loop finishes $X$, the last visited node of ${\cal T}$. It is easy to
see that, the $(4-p)$-leaf root $T$ on $t+1$ vertices is constructed in ${\cal
O}(t)={\cal O}(n)$ time.

Next for the induction step, where $n>3$ and $G$ is not a star. The algorithm
enters Line 1 because $G$ is connected and, thus, the cotree ${\cal T}$ has a
1-root $X$ with leaf-child $u$ and a 0-child $Y$ with, in turn, 1-children
$Z_{1},\dots,Z_{s}$, $s\geq 1$. Due to post-order traversal, the algorithm
consecutively iterates through the subtrees ${\cal T}_{Z_{1}},\dots,{\cal
T}_{Z_{s}}$ before entering $Y$ and then $X$. Since the graphs
$G_{1},\dots,G_{s}$ that correspond to ${\cal T}_{Z_{1}},\dots,{\cal
T}_{Z_{s}}$ are connected and have strictly fewer vertices than $G$ (they all
miss $u$), the induction assumption states that ${\cal S}$ carries the
sequence $(T_{1},k_{1})=\rho(G_{1},p),\dots,(T_{s},k_{s})=\rho(G_{s},p)$ on
its top. Hence, Algorithm 1 retrieves this list of interim results in Line 1.
Although unmentioned for clarity in the listing of Algorithm 1, every tree
$T_{i}$, $1\leq i\leq s$ is retrieved together with the explicit information
on center, min-max center, diameter, and leaf distance. Altogether, this takes
${\cal O}(|V(G_{1})|)+\dots+{\cal O}(|V(G_{s})|)={\cal O}(n)$ time.

After that, it is easy to check that $k$ is computed exactly like in Case ii.
in the listing of the $\rho$-operation in Section 3. Hence, Line 1 computes
the same extended $k$-leaf roots $T^{\prime}_{1},\dots,T^{\prime}_{s}$ as
$\rho$ and, by Lemma 6, this takes ${\cal O}(|V(G_{1})|)+\dots+{\cal
O}(|V(G_{s})|)={\cal O}(n)$ time. Notice that the subroutine $\eta$ includes
min-max center $z^{\prime}_{i}$, center $Z^{\prime}_{i}$, diameter
${\mathrm{diam}}(T^{\prime}_{i})$, and leaf distance
$d^{\mathrm{min}}_{T^{\prime}_{i}}$ for every tree $T^{\prime}_{i}$, $1\leq
i\leq s$. Based on that, the Lines 1 and 1 produce the same merged $k$-leaf
root $T$ as $\rho$ does. According to Lemma 7 and because $s+t\leq n$, this
needs just ${\cal O}(s+t)={\cal O}(n)$ time. The subroutine $\mu$ explicitly
returns only the center $Z=\\{z_{1},z_{2}\\}$ and the diameter
${\mathrm{diam}}(T)$ with $T$. However, the min-max center $z$ and the leaf
distance $d^{\mathrm{min}}_{T}$ are immediately determined in the next Line 1
due to attaching $u$. If ${\mathrm{\pi}}(T)=0$ then $z=z_{1}=z_{2}$ and
$d^{\mathrm{min}}_{T}=1$ and, otherwise, $z$ the center that is not chooses as
the parent of $u$ and $d^{\mathrm{min}}_{T}=2$. This means that
$(T,k)=\rho(G,p)$, including $z$, $Z$, ${\mathrm{diam}}(T)$, and
$d^{\mathrm{min}}_{T}$, is subsequently pushed onto ${\cal S}$ in Line 1. This
finishes the processing of $X$, the last visited node of ${\cal T}$, after
${\cal O}(n)$ time in total.

For a disconnected graph $G$, we also show that the loop in Lines 1 to 1 puts
$(T,k)=\rho(G,p)$ on top of the stack ${\cal S}$. The cotree ${\cal T}$ of $G$
has a 0-root $X$, which has 1-children $Z_{1},\dots,Z_{s}$, $s\geq 0$ and
leaf-children $V_{1},\dots,V_{t}$ such that $s+t\geq 2$. Notice that $X$, as
the root of ${\cal T}$, has no parent. Then, as argued before, the post-order
traversal consecutively iterates through ${\cal T}_{Z_{1}},\dots,{\cal
T}_{Z_{s}}$ before entering the node $X$ in Line 1. Since the graphs
$G_{1},\dots,G_{s}$ are connected, we have seen above that iterating the
children of $X$ takes ${\cal O}(|V(G_{1})|)+\dots+{\cal O}(|V(G_{s})|)={\cal
O}(n)$ time and puts the sequence
$(T_{1},k_{1})=\rho(G_{1},p),\dots,(T_{s},k_{s})=\rho(G_{s},p)$ on top of the
stack ${\cal S}$. Again unmentioned, every tree $T_{i}$, $1\leq i\leq s$ comes
with explicitly designated min-max center, center, diameter and leaf distance.
Altogether, this takes ${\cal O}(|V(G_{1})|)+\dots+{\cal O}(|V(G_{s})|)={\cal
O}(n)$ time. Like in Case iii. of the $\rho$-operation, the value of $k$ is
the maximum among $\\{k_{1},\dots,k_{s},p+2\\}$. So, by Lemmas 6 and 7,
$(T,k)=\rho(G,p)$ is correctly computed in Lines 1 and 1 in ${\cal O}(n)$
time. Then Line 1 puts $(T,k)$ on top of ${\cal S}$, which finishes $X$, the
last visited node of ${\cal T}$.

Since ${\cal O}(n)\leq{\cal O}(m)$, the Algorithm takes ${\cal O}(n+m)$ time
in each of the above cases to finally reach Line 1, where $(T,k)=\rho(G,p)$
waits accessible at the top of ${\cal S}$. Hence, because $G$ is a ccg without
true twins, Theorem 3.1 tells us that Algorithm 1 provides an optimal $k$-leaf
root $T$ of $G$ with ${\mathrm{\pi}}(k)=p$ at this point. This proves Theorem
4.1. ∎

Lemma 8. _For all integers $i\geq 1$, the graph $F_{i}$ is a (odd)
$k_{i}$-leaf power for $k_{i}=2^{i+2}-1$ but not a $(k_{i}-2)$-leaf power and
a (even) $k^{\prime}_{i}$-leaf power for $k^{\prime}_{i}=k_{i}+2^{i}-1$ but
not a $(k^{\prime}_{i}-2)$-leaf power. _

###### Proof

We show by induction on $i$ that $(T_{i},k_{i})=\rho(F_{i},1)$ and
$(T^{\prime}_{i},k^{\prime}_{i})=\rho(F_{i},0)$ with
${\mathrm{\pi}}(T_{i})={\mathrm{\pi}}(T^{\prime}_{i})=0$. This proves the
lemma because, by Theorem 3.1, $\rho$ provides an optimal leaf root of the
given parity.

For the induction start at $i=1$, we leave it to the reader to check that
$(T_{1},k_{1})=\rho(F_{1},1)$ and
$(T^{\prime}_{1},k^{\prime}_{1})=\rho(F_{1},1)$ provide a $k_{1}$-leaf root
$T_{1}$ of $F_{1}$ with $k_{1}=7$ and ${\mathrm{diam}}(T_{1})=8$ and a
$k^{\prime}_{1}$-leaf root $T^{\prime}_{1}$ with $k^{\prime}_{1}=8$ and
${\mathrm{diam}}(T^{\prime}_{1})=10$.

For the induction step let $i>0$ and assume that
$(T_{i-1},k_{i-1})=\rho(F_{i-1},1)$ with ${\mathrm{\pi}}(T_{i-1})=0$ and
$(T^{\prime}_{i-1},k^{\prime}_{i-1})=\rho(F_{i-1},0)$ with
${\mathrm{\pi}}(T^{\prime}_{i-1})=0$.

We complete the proof by following the constructions of $\rho(F_{i},1)$ and
$\rho(F_{i},0)$ as introduced in Section 3. First, note that

$F_{i}=t_{i}\ \leavevmode\hbox to8.34pt{\vbox
to8.34pt{\pgfpicture\makeatletter\hbox{\hskip 4.17046pt\lower-4.17046pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{