Indian Institute of Technology Madras, Chennai,
Indiagirishb@cse.iitm.ac.inhttps://orcid.org/0000-0002-1825-0097 University of
Tokyo, Tokyo<EMAIL_ADDRESS>Indian Institute of
Technology Madras, Chennai<EMAIL_ADDRESS>University of Tokyo,
Tokyo<EMAIL_ADDRESS>Jane Open Access and Joan R. Public
[100]Replace ccsdesc macro with valid one John Q. Open and Joan R. Access 2
42nd Conference on Very Important Topics (CVIT 2016) CVIT 2016 CVIT 2016
December 24–27, 2016 Little Whinging, United Kingdom 42 23

# Succinct Data Structure for Chordal Graphs with Bounded Vertex Leafage

Girish Balakrishnan  Sankardeep Chakraborty  N S Narayanaswamy  Kunihiko
Sadakane

###### Abstract

Chordal graphs is a well-studied large graph class that is also a strict
super-class of path graphs. Munro and Wu (ISAAC 2018) have given an
$(n^{2}/4+o(n^{2}))-$bit succinct representation for $n-$vertex unlabeled
chordal graphs. A chordal graph $G=(V,E)$ is the intersection graph of sub-
trees of a tree $T$. Based on this characterization, the two parameters of
chordal graphs which we consider in this work are leafage, introduced by Lin,
McKee and West (Discussiones Mathematicae Graph Theory 1998) and vertex
leafage, introduced by Chaplick and Stacho (Discret. Appl. Math. 2014).
Leafage is the minimum number of leaves in any possible tree $T$
characterizing $G$. Let $L(u)$ denote the number of leaves of the sub-tree in
$T$ corresponding to $u\in V$ and $k=\max\limits_{u\in V}L(u)$. The smallest
$k$ for which there exists a tree $T$ for $G$ is called its vertex leafage.

In this work, we improve the worst-case information theoretic lower bound of
Munro and Wu (ISAAC 2018) for chordal graphs when vertex leafage is bounded
and leafage is unbounded. The class of unlabeled $k-$vertex leafage chordal
graphs that consists of all chordal graphs with vertex leafage at most $k$ and
unbounded leafage, denoted $\mathcal{G}_{k}$, is introduced for the first
time. For $k>1$ in $o(n/\log n)$, we obtain a lower bound of $((k-1)n\log
n-kn\log k-O(\log n))-$bits on the size of any data structure that encodes a
graph in $\mathcal{G}_{k}$. Further, for every $k-$vertex leafage chordal
graph $G$ such that $k>1$ in $o(n/\log n)$, we present a $((k-1)n\log
n+o(kn\log n))-$bit data structure, constructed using the succinct data
structure for path graphs with $kn/2$ vertices. Our data structure supports
adjacency query in $O(k\log n)$ time and using additional $2n\log n$ bits, an
$O(k^{2}d_{v}\log n+\log^{2}n)$ time neighbourhood query where $d_{v}$ is
degree of $v\in V$.

###### keywords:

Boxicity, Interval Number, Succinct Data Structure

###### category:

##  1 Introduction

A data structure for a graph class $\mathcal{G}$ is succinct if it takes
$(\log|\mathcal{G}|+o(\log|\mathcal{G}|))-$bits of space; here $|\mathcal{G}|$
denotes the number of graphs in $\mathcal{G}$. A succinct representation for
graph $G=(V,E)$ in $\mathcal{G}$ is expected to support the following queries
for each pair of vertices $u,v\in V$:

  * •

$\texttt{adjacency}(u,v)$: returns "YES" if and only if vertices $u$ and $v$
are adjacent in $G$.

  * •

$\texttt{neighborhood}(u)$: returns all the vertices in $V$ that are adjacent
to vertex $u$.

  * •

$\texttt{degree}(u)$: returns the number of vertices adjacent to vertex $u$.

The earliest work on space-efficient data structures for graph classes was by
Itai and Rodeh [10] for vertex labeled planar graphs and by Jacobson [11] for
class of static unlabeled trees and planar graphs. In recent years, succinct
data structures for intersection graphs is getting lot of attention. A few of
them are, Acan et al. [2] for interval graphs, Acan et al. [1] for families of
intersection graphs on circle, Munro and Wu [14] for chordal graphs and
Balakrishnan et al. [3] for path graphs.

A recent paper by Chakraborty and Jo [5] improve the information theoretic
lower bound for interval graphs as given by Acan et al. [2] by bounding
maximum degree. For bounded maximum degree $\Delta$ in $O(n^{\epsilon})$ where
$1<\epsilon<1$, they give a lower bound of
$(\frac{1}{6}n\log\Delta-O(n))-$bits and a $(n\log\Delta+O(n))-$bit space-
efficient data structure. They also give a $((\chi-1)n+o(\chi n))-$bit space-
efficient data structure for interval graphs with bounded chromatic number
$\chi$ for $\chi=o(\log n)$. In Balakrishnan et al. [4], such a
parameterization has been applied to a larger graph class, namely, the class
of graphs with $d-$dimensional $t-$representation where parameters $d$ and $t$
are bounded. A $((2td-1)n\log n+o(tdn\log n))-$bit succinct data structure for
graphs with $d-$dimensional $t-$representation is presented in [4]. Special
cases of this graph class are graphs with bounded boxicity with $t=1$ and
bounded interval number with $d=1$. Chordal graphs is also a large graph class
that is a generalization of interval graphs. A graph is a chordal graph if it
contains only cycles of length at most three. Lin et al. [12] introduced the
parameter leafage and Chaplick and Stacho [6] the parameter vertex leafage for
chordal graphs. In this work, we define the $k-$vertex leafage chordal graphs
that contains chordal graphs with bounded vertex leafage and unbounded
leafage. When vertex leafage and leafage are equal to two we get interval
graphs and when vertex leafage is two and leafage is unbounded we get path
graphs. We present a data structure for $k-$vertex leafage chordal graphs
using succinct data structure for path graphs and prove that it is succinct.

Convention. Throughout the rest of this paper, set of vertices and edges of a
graph $G$ will be denoted by $V(G)$ and $E(G)$, respectively.

Our Results. We present the following two theorems. The following theorem
proves a lower bound on the class of $k-$vertex leafage graphs, denoted
$\mathcal{G}_{k}$.

######  Theorem 1.1.

For $k>0$ in $o(n/\log n),\log|\mathcal{G}_{k}|\geq(k-1)n\log n-kn\log
k-O(\log n)$.

The next theorem proves the existence of a matching data structure that
supports adjacency query efficiently. For neighbour query we use additional
$2n\log n$ bits.

######  Theorem 1.2.

For $k\in o(n/\log n)$, a graph $G\in\mathcal{G}_{k}$ has a $(k-1)n\log
n+o(kn\log n)$-bit succinct data structure that supports adjacency query in
$O(k\log n)$ time and using additional $2n\log n$ bits the neighbourhood query
for vertex $v$ in $O(k^{2}d_{v}\log n+\log^{2}n)$ time where $d_{v}$ is the
degree of $v\in V(G)$.

Organisation of the Paper. Section 2 gives details of the compact data
structures we have used in the construction of the succinct data structure of
$k-$vertex leafage chordal graphs along with characterisation of chordal and
path graphs. It also formalizes and explains the method of partial coloring,
first used in Acan et al. [1], to obtain the lower bound for
$\mathcal{G}_{k}$. Section 3 defines the $k-$vertex leafage chordal graphs and
also gives a lower bound on the cardinality of the class. The succinct data
structure design is given in Section 4 and it contains in Section 4.1, the
method to convert a $k-$vertex leafage chordal graph with $n$ vertices to a
path graph with $kn/2$ vertices.

##  2 Preliminaries

From Golumbic [8] we have, the following characterisations of chordal graphs
and path graphs.

######  Theorem 2.1.

The graph $G$ is a chordal graph if and only if there exists a clique tree
$T$, such that for every $v\in V(G)$, the set of maximal cliques containing
$v$ form a sub-tree of $T$ such that two vertices are adjacent if the
corresponding sub-trees intersect.

######  Theorem 2.2.

The graph $G$ is a path graph if and only if there exists a clique tree $T$,
such that for every $v\in V(G)$, the set of maximal cliques containing $v$ is
a path in $T$ such that two vertices are adjacent if the corresponding paths
intersect.

Succinct Data Structure for Ordinal Trees. Tree $T$ is called an ordinal tree
if for $z>0$ and any $u\in V(T)$ with children $\\{u_{1},\ldots,u_{z}\\}$, for
$1\leq i<j\leq z$, $u_{i}$ is to the left of $u_{j}$ [16]. By considering
ordinal trees as balanced parenthesis Navarro and Sadakane [16] has given a
$2n+o(n)$ bit succinct data structure.

######  Lemma 2.3.

For any ordinal tree $T$ with $n$ nodes, there exists a $2n+o(n)$ bit Balanced
Parentheses (BP) based data structure that supports the following functions
among others in constant time :

  1. 1.

${\texttt{lca}}(i,j)$, returns the lowest common ancestor of two nodes $i,j$
in $T$, and

  2. 2.

${\texttt{child}}(i,v)$, returns the $q-$th child of $v$ in $T$.

Rank-Select Data Structure. Bit-vectors are extensively used in the succinct
representation given in Section 4. The following data structure due to
Golynski et al. [9] and the functions supported by it are useful.

######  Lemma 2.4.

Let $B$ be an $n-$bit vector and $b\in\\{0,1\\}$. There exists an $n+o(n)$ bit
data structure that supports the following functions in constant time:

  1. 1.

${\texttt{rank}}(B,b,i)$: Returns the number of $b$’s up to and including
position $i$ in the bit vector $B$ from the left.

  2. 2.

${\texttt{select}}(B,b,i)$: Returns the position of the $i$-th $b$ in the bit
vector $B$ from left. For $i\notin[n]$ it returns 0.

Non-Decreasing Integer Sequence Data Structure. Given a set of positive
integers in the non-decreasing order we can store them efficiently using the
differential encoding scheme for increasing numbers; see Section 2.8 of [15].
Let $S$ be the data structure that supports differential encoding for
increasing numbers then the function $\texttt{accessNS}(S,i)$ returns the
$i-$th number in the sequence.

######  Lemma 2.5.

Let $S$ be a sequence of $n$ non-decreasing positive integers
$a_{1},\ldots,a_{n},1\leq a_{i}\leq n$. There exists a $2n+o(n)$ bit data
structure that supports ${\texttt{accessNS}}(S,i)$ in constant time.

######  Proof 2.6.

We will prove the lemma by giving a construction of such a data structure.
$a_{1}$ will be represented by a sequence of $a_{1}$ 1’s followed by a 0.
Subsequently, $a_{i}$’s are represented by storing $a_{i}-a_{i-1}$ many 1’s
followed by a 0. It will take at most $2n$ bits since there are $n$ 0’s and at
most $n$ 1’s. Let this bit string be stored using the data structure of Lemma
2.4 and be denoted as $B$. $B$ takes $2n+o(n)$ bits. $\texttt{accessNS}(S,i)$
can be implemented using $\texttt{rank}(B,1,\texttt{select}(B,0,i))$.

Succinct Data Structure for Path Graphs. From [3] we have the following
succinct data structure for path graphs that supports adjacency and
neighbourhood queries with slight modifications in input. In the following
lemma the endpoints of paths are input to the queries whereas in [3] the path
indices are given as input.

######  Lemma 2.7.

A path graph $G$ has an $n\log n+o(n\log n)$-bit succinct representation. For
a $u\in V(G)$, let $P_{u}=(s_{u},t_{u})$ be the path corresponding $u$ in
clique tree $T$ of $G$. The succinct representation constructed from the
clique tree $T$ representation supports for $u\in V(G)$ the following queries:

  1. 1.

${\texttt{adjacencyPG}(s_{u},t_{u},s_{v},t_{v})}$: Returns true if
$P_{u}=(s_{u},t_{u})$ intersects $P_{v}=(s_{v},t_{v})$ in $O(\log n)$ time
else false,

  2. 2.

${\texttt{pathep}(u)}$: Returns the endpoints of path $P_{u}$, corresponding
to $u$, in $T$ in $O(\log n)$ time, and

  3. 3.

${\texttt{neighbourhoodPG}(s_{u},t_{u})}$: Returns the list of paths
intersecting $P_{u}=(s_{u},t_{u})$ in $O(d_{u}\log n)$ time where $d_{u}$ is
the degree of vertex $u$.

  4. 4.

${\texttt{getHPStartNode}(v)}$: Returns the start node of heavy path $\pi$
that contains $v\in V(T)$ in constant time. If $v$ is not the first child,
that is, it is adjacent to its parent by a light edge, then $v$ itself is
returned.

Permutations. The following data structure by Munro et al. [13], gives a
succinct representation for storing permutation of $[n]$.

######  Lemma 2.8 ([13]).

Given a permutation of $[n]$ there exists an $(n\log n+o(n\log n))$-bit data
structure that supports the following queries.

  * •

$\pi(i)$: Returns the $i-$th value in the permutation in $O(1)$ time.

  * •

$\pi^{-1}(j)$: Returns the position of the $j-$th value in the permutation in
$O(f(n))$ time for any increasing function $f(n)=o(\log n)$.

Method of Partial Coloring. Let $\mathcal{G}$ be a graph class. A partial
coloring of $G$ is the triple $\langle G,U,g\rangle$ where,

  * •

$U\subseteq V(G)$ such that for $s>0,|U|=s$, and

  * •

$g:U\rightarrow\\{1,\ldots,s\\}$ is a bijection.

Every vertex $u\in U$ is said to have color $g(u)$ and vertices in
$V(G)\backslash U$ are said to be uncolored. Two partially colored graphs
$\langle H_{1},U_{1},g_{1}\rangle$ and $\langle H_{2},U_{2},g_{2}\rangle$ are
said to be different when either:

  1. 1.

$E(H_{1})\neq E(H_{2})$, or

  2. 2.

$E(H_{1})=E(H_{2})=E(H)$ for some $H\in\mathcal{G}$ and there exists $u\in
V(H)\backslash U$ such that its colored neighbourhood in $\langle
H_{1},U_{1},g_{1}\rangle$ and $\langle H_{2},U_{2},g_{2}\rangle$ are
different.

Else, they are same. The method of counting by partial coloring as given in
Theorem 1 of Acan et al. [1] can be defined using the following proposition.

######  Proposition 2.9.

Let $\mathcal{G}^{\prime}$ be the class of partially colored graphs obtained
from class of graphs $\mathcal{G}$ by selecting $m$ vertices out of $n$ and
coloring them using $m$ distinct colors. Then,
$|\mathcal{G}^{\prime}|\leq{n\choose m}m!|\mathcal{G}|$. If there exists a
graph class $\mathcal{G}^{c}\subset\mathcal{G}^{\prime}$ then
$|\mathcal{G}^{\prime}|\geq|\mathcal{G}^{c}|$ and
$|\mathcal{G}|\geq\frac{|\mathcal{G}^{c}|}{{n\choose m}m!}$.

Remark: While computing $|\mathcal{G}^{\prime}|$, indistinguishable partially
colored graphs can also be counted since we only require an upper bound,
however, this is not the case while computing $|\mathcal{G}^{c}|$.

##  3 Class of $k-$Vertex Leafage Chordal Graphs and its Lower Bound

In this section, we define the class of $k-$vertex leafage chordal graphs,
denoted $\mathcal{G}_{k}$, followed by the lower bound for
$\log|\mathcal{G}_{k}|$. According to Theorem 2.1, a graph $G$ is a chordal
graph if there exists a tree $T$ such that corresponding to every vertex $v\in
V(G)$ there exists a sub-tree $T_{v}$ of $T$ and $\\{u,v\\}\in E(G)$ if and
only if $V(T_{u})\cap V(T_{v})\neq\phi$ where $T_{v}$ is the sub-tree
corresponding to $v\in V(G)$. We call $T$ the tree model of $G$. For every
chordal graph there exists a tree $T$ called the clique tree such that $V(T)$
is the set of maximal cliques of $G$. The leafage of a chordal graph $G$,
denoted $l(G)$, is the minimum number of leaves of a tree $T$ out of all
possible trees characterising $G$. Leafage was studied by Lin et al. in [12].
Later, Chaplick and Stacho in [6] studied vertex leafage, denoted $vl(G)$. Let
$L(u)$ denote the number of leaves of the sub-tree in $T$ corresponding to
$u\in V$ and $k=\max\limits_{u\in V}L(u)$. The smallest $k$ for which there
exists a tree $T$ for $G$ is called its vertex leafage.

Class of $k-$Vertex Leafage Chordal Graphs. The class of chordal graphs can be
considered as the generalisation of path graphs using vertex leafage as the
parameter. Theorem 2.2 implies that path graphs are chordal graphs with vertex
leafage equal to two and unbounded leafage. Generalizing this,
$\mathcal{G}_{k}$ is the set of all chordal graphs with vertex leafage at most
$k$ and unbounded leafage. Succinct data structure for path graphs is given by
Balakrishnan et al. in [3]. In this paper, we present a succinct data
structure for chordal graphs with vertex leafage at most $k$ for $k\in
o(n/\log n)$ using succinct data structure for path graphs as black-box.

Lower Bound. In order to derive the lower bound for $\log|\mathcal{G}_{k}|$ by
implementing Proposition 2.9, we define two new graph classes,
$\mathcal{G}^{\prime}_{k}$ and $\mathcal{G}^{c}_{k}$, where
$\mathcal{G}^{\prime}_{k}$ corresponds to $\mathcal{G}^{\prime}$ and
$\mathcal{G}^{c}_{k}$ to $\mathcal{G}^{c}$ of Proposition 2.9.

Graph Class $\mathcal{G}^{\prime}_{k}$. We consider the class of all partially
colored $k-$vertex leafage chordal graphs, denoted $\mathcal{G}^{\prime}_{k}$,
that has for fixed $1\leq m\leq n$, $m$ out of $n$ vertices colored using
colors $\\{1,\ldots,m\\}$. Graphs in $\mathcal{G}^{\prime}_{k}$ are obtained
from graphs in $\mathcal{G}_{k}$ as follows. The input to the procedure is
$G\in\mathcal{G}_{k}$ and a set $\\{v_{1},\ldots,v_{m}\\}$ of $m$ vertices of
$G$. For each $G\in\mathcal{G}_{k}$, we get a set of ${n\choose m}m!$ graphs
of $\mathcal{G}^{\prime}_{k}$ where each graph $G^{\prime}$ is obtained by
coloring the selected $m$ vertices of $G$ by a permutation of
$\\{1,\ldots,m\\}$. A partially colored graph in $\mathcal{G}^{\prime}_{k}$ is
denoted $\langle H,U,g\rangle$ where $U\subset V(H),|U|=m$, and
$g:U\rightarrow\\{1,\ldots,m\\}$.

######  Lemma 3.1.

For each $k\geq 1$,
$\log|\mathcal{G}^{\prime}_{k}|\leq\log|\mathcal{G}_{k}|+n\log
n-(n-m)\log(n-m)-2n+O(\log n)$.

######  Proof 3.2.

The $m$ vertices given as input to the procedure can be selected in $n\choose
m$ ways and there are $m!$ ways of coloring it. Thus, from each $G$ in
$\mathcal{G}_{k}$ we get ${n\choose m}m!$ partially colored graphs. Hence, we
have $|\mathcal{G}^{\prime}_{k}|\leq|\mathcal{G}_{k}|\frac{n!}{(n-m)!}$.
Taking log on both sides and using Stirling’s approximation, that is, $\log
n!=n\log n-n+O(\log n)$, we get
$\log|\mathcal{G}^{\prime}_{k}|\leq\log|\mathcal{G}_{k}|+n\log
n-(n-m)\log(n-m)-2n+O(\log n)$.

Graph Class $\mathcal{G}^{c}_{k}$. As per Proposition 2.9, we construct the
class $\mathcal{G}^{c}_{k}\subset\mathcal{G}^{\prime}_{k}$ for which we can
obtain exact count. We give a construction mechanism for graphs in
$\mathcal{G}^{c}_{k}$ such that all graphs in it have the following
properties. For $G\in\mathcal{G}^{c}_{k}$,

  * •

$U\subseteq V(G)$, with $|U|=m$, is fixed and have a fixed coloring using
colors $\\{1,\ldots,m\\}$,

  * •

let $T$ be the tree corresponding to $G$ then the sub-trees in the clique tree
corresponding to vertices in $U$ consist of only one node, and

  * •

sub-trees of $T$ corresponding to vertices in $V(G)\backslash U$ have $k$
leaves.

In other words, for all the partially colored graphs in $\mathcal{G}^{c}_{k}$,
$U$ and $g$ are fixed. Based on the tree model, the vertices of a graph
$H\in\mathcal{G}^{c}_{k}$ with tree model $T$ are of two types:

  1. 1.

basis vertices $U$: $m$ vertices of $U$ are represented by single-node sub-
tree in $T$, and

  2. 2.

dependent vertices $V(H)\backslash U$: rest of the $(n-m)$ vertices are
represented by sub-trees in $T$ with number of leaves equal to $k$.

We have the following useful proposition:

######  Proposition 3.3.

For a tree $T$, the set $V^{\prime}\subseteq V(T)$ uniquely defines a sub-tree
$T^{\prime}$ of $T$ such that $V^{\prime}$ are its leaves.

The sub-trees corresponding to the basis and dependent vertices are called
basis and dependent sub-trees, respectively. The input to the procedure that
constructs $H$ are:

  1. 1.

$n,m,k,$ and

  2. 2.

$\mathcal{J}=\\{J_{1},\ldots,J_{n-m}\\}$ where for $1\leq i\leq n-m$,
$J_{i}=\\{a^{i}_{1},\ldots,a^{i}_{k}\\}$, where for $1\leq t\leq k,1\leq
a^{i}_{t}\leq m$.

The construction mechanism that constructs the partially colored graph
$\langle H,U,g\rangle$ is as follows.

  1. 1.

Consider a fixed tree $T$ with $m>0$ nodes and let them be colored from 1 to
$m$.

  2. 2.

Construction of basis sub-trees. For $1\leq j\leq m$, let each node $b_{j}\in
V(T)$ be a single node sub-tree, $T_{j}$. These sub-trees are the basis sub-
trees. The basis sub-trees correspond to the $m$ basis vertices of $H$,
denoted by $U$. Let the basis vertices be colored by the color assigned to the
nodes to which they are assigned.

  3. 3.

Construction of dependent sub-trees. For $1\leq i\leq n-m$, construct sub-tree
$T_{i}$ from $J_{i}=\\{a^{i}_{1},\ldots,a^{i}_{k}\\}$, where for $1\leq t\leq
k,a^{i}_{t}\in V(T)$, such that $J_{i}$ is the set of leaves of $T_{i}$; as
per Proposition 3.3, $J_{i}$ uniquely defines a sub-tree. These sub-trees are
called dependent sub-trees and correspond to the dependent vertices in
$V(H)\backslash U$.

Convention. A node $a_{j}\in V(T)$ will also be used to denote the sub-tree
$T_{j}$ corresponding to the basis vertex of $H$.

Thus, $H$ is defined by $\mathcal{J}=\\{J_{1},\ldots,J_{n-m}\\}$ where each
$J_{i}$ defines a sub-tree $T_{i}$. From the construction above we have the
following lemma.

######  Lemma 3.4.

$\mathcal{G}^{c}_{k}\subseteq\mathcal{G}^{\prime}_{k}$.

######  Proof 3.5.

From the construction given above, any graph $G\in\mathcal{G}^{c}_{k}$ has a
fixed $U\subset V(G)$ where $|U|=m$ that is colored using colors
$\\{1,\ldots,m\\}$ such that there exists a tree model of $G$ with:

  1. 1.

vertices in $U$ corresponding to single node sub-trees,

  2. 2.

sub-trees of vertices in $U$ are colored using colors $\\{1,\ldots,m\\}$, and

  3. 3.

sub-trees of vertices in $V(G)\backslash U$ with $k$ leaves are uncolored.

Since $\mathcal{G}^{c}_{k}$ is a special class of partially colored chordal
graphs with leafage $k$, $\mathcal{G}^{c}_{k}\subset\mathcal{G}^{\prime}_{k}$.

Computing $|\mathcal{G}^{c}_{k}|$. In order to compute $|\mathcal{G}^{c}_{k}|$
and use Proposition 2.9, we first note the following.

######  Proposition 3.6.

$\log|\mathcal{G}^{\prime}_{k}|\geq\log|\mathcal{G}^{c}_{k}|$.

######  Proof 3.7.

From Lemma 3.4.

Let $K$ denote the set of all possible $\mathcal{J}$’s. We have the following
useful proposition and lemma.

######  Proposition 3.8.

For $1\leq i,i^{\prime}\leq n-m,1\leq j\leq m$, if $J_{i}\neq J_{i^{\prime}}$
then wlog there exists $a_{j}\in U$ such that $a_{j}\in J_{i}$ and
$a_{j}\notin J_{i^{\prime}}$.

######  Lemma 3.9.

Let $\mathcal{J},\mathcal{J}^{\prime}\in K$ where
$\mathcal{J}=\\{J_{1},\ldots,J_{n-m}\\}$ and
$\mathcal{J}^{\prime}=\\{J^{\prime}_{1},\ldots,J^{\prime}_{n-m}\\}$ such that
for $1\leq s\leq n-m,J_{s}\neq J^{\prime}_{s}$. Then the uncolored dependent
vertex corresponding to $s$ has different colored basis vertices as neighbours
in the graphs generated from $\mathcal{J}$ and $\mathcal{J}^{\prime}$.

######  Proof 3.10.

From Proposition 3.8, we know that the dependent vertex $u$ corresponding to
$J_{s}$ will have at least one basis vertex in its neighbourhood that is not
present in the neighbourhood of the dependent vertex corresponding to
$J^{\prime}_{s}$.

The following is the central lemma used to obtain the lower bound. For $1\leq
s\leq n-m$, let $\mathcal{J}(H)$ denote the $\mathcal{J}\in K$ that produces
the graph $H\in\mathcal{G}^{c}_{k}$.

######  Lemma 3.11.

Let $\langle H_{1},U,g\rangle,\langle H_{2},U,g\rangle$ be constructed from
$\mathcal{J},\mathcal{J}^{\prime}\in K$. Then $\langle H_{1},U,g\rangle$ and
$\langle H_{2},U,g\rangle$ are same if and only if
$\mathcal{J}=\mathcal{J}^{\prime}$.

######  Proof 3.12.

We prove both directions as follows:

  1. 1.

If $\langle H_{1},U,g\rangle=\langle H_{2},U,g\rangle$ then
$\mathcal{J}=\mathcal{J}^{\prime}$. We prove its contrapositive, that is, if
$\mathcal{J}\neq\mathcal{J}^{\prime}$ then $\langle
H_{1},U,g\rangle\neq\langle H_{2},U,g\rangle$. If
$\mathcal{J}\neq\mathcal{J}^{\prime}$ then for $1\leq s\leq n-m$ there exists
$J_{s}\neq J^{\prime}_{s}$. Let $V$ denote the set of vertices in $H_{1}$ and
$H_{2}$. By Lemma 3.9, there exists $u\in V\backslash U$ corresponding to $s$
such that $N_{H_{1}}(u)\cap U\neq N_{H_{2}}(u)\cap U$ where $N_{H_{1}}(u)$ and
$N_{H_{2}}(u)$ are the neighbours of $u$ in $H_{1}$ and $H_{2},$ respectively.
Thus, $E(H_{1})\neq E(H_{2})$ and so by definition $\langle
H_{1},U,g\rangle\neq\langle H_{2},U,g\rangle$.

  2. 2.

If $\mathcal{J}=\mathcal{J}^{\prime}$ then $\langle H_{1},U,g\rangle$ and
$\langle H_{2},U,g\rangle$ are same by construction.

In order to obtain $|\mathcal{G}^{c}_{t,d}|$ we prove the following lemma
first.

######  Lemma 3.13.

$|\mathcal{G}^{c}_{k}|=|K|$.

######  Proof 3.14.

The proof establishes a bijection between $\mathcal{G}^{c}_{t,d}$ and $K$ as
follows.

  * •

Every graph of $\mathcal{G}^{c}_{t,d}$ is produced by some element of $K$.
Every $\mathcal{J}\in K$ produces a $G\in\mathcal{G}^{c}_{t,d}$. Since every
set of leaf nodes obtained from $\mathcal{J}$ describes some $(n-m)$ sub-trees
with $k$ leaves each such that they represent a graph this is true.

  * •

For every $\mathcal{J}\in K$, a distinct graph of $\mathcal{G}^{c}_{t,d}$ is
produced. As per Lemma 3.11, if $\mathcal{J},\mathcal{J}^{\prime}\in K$ are
different then the graphs $H,H^{\prime}\in\mathcal{G}^{c}_{t,d}$ produced from
them are different.

Thus, $|\mathcal{G}^{c}_{t,d}|=|K|$.

The following is an important lemma.

######  Lemma 3.15.

$\log|\mathcal{G}^{c}_{k}|\geq kn\log n-kn\log k$.

######  Proof 3.16.

From Lemma 3.13, we know that $|\mathcal{G}^{c}_{k}|=|K|$. So we count number
of $\mathcal{J}$’s that can be obtained. For $1\leq t\leq n-m$, the $k$ leaves
in $J_{t}$ can be selected in ${m\choose k}$ ways. For $n-m$ vertices it can
be done in ${m\choose k}^{n-m}$ ways, that is, $|K|={m\choose k}^{n-m}$. Using
the relation that ${m\choose k}$ equals $\big{(}\frac{me}{k}\big{)}^{k}$
asymptotically for very large $m$ compared to $k$ we have ${m\choose
k}^{n-m}>\big{(}\frac{m}{k}\big{)}^{k(n-m)}$, that is, there are at least
$\big{(}\frac{m}{k}\big{)}^{k(n-m)}$ distinct $\mathcal{J}$ that can be
constructed. Thus,
$|\mathcal{G}^{c}_{k}|=|K|>\big{(}\frac{m}{k}\big{)}^{k(n-m)}$. Then, for
fixed $\epsilon>1$ and $m=n/\epsilon$, we have
$|\mathcal{G}^{c}_{k}|\geq\big{(}\frac{n}{\epsilon
k}\big{)}^{\big{(}1-\frac{1}{\epsilon}\big{)}kn}$. Taking logarithm we have,

$\log|\mathcal{G}^{c}_{k}|\geq k\Big{(}1-\frac{1}{\epsilon}\Big{)}n\log
n-k\Big{(}1-\frac{1}{\epsilon}\Big{)}n\log k$

As $n$ tends to infinity,

$\log|\mathcal{G}^{c}_{k}|\geq kn\log n-kn\log k.$

See 1.1

######  Proof 3.17.

Applying Proposition 3.6 to Lemma 3.1 we have,

$\displaystyle\log|\mathcal{G}_{k}|$
$\displaystyle\geq\log|\mathcal{G}^{\prime}_{k}|-n\log
n+(n-m)\log(n-m)+2n-O(\log n)$
$\displaystyle\geq\log|\mathcal{G}^{c}_{k}|-n\log n-O(\log n)$

Applying Lemma 3.15 to the above expression, we have,

$\displaystyle\log|\mathcal{G}_{k}|$ $\displaystyle\geq(k-1)n\log n-kn\log
k-O(\log n)$

We have the following proposition.

######  Proposition 3.18.

For $k>0$, in $o(n/\log n)$ and sufficiently large $n$,
$\log|\mathcal{G}_{k}|\geq(k-1)n\log n$.

##  4 Succinct Data Structure

The high-level procedure used to obtain the succinct data structure for
$k-$vertex leafage chordal graph $G$ given as $(T,\\{T_{1},\ldots,T_{n}\\})$
is as follows:

  1. 1.

From the clique tree $T$, obtain path graph $H$ with $(k-1)n$ vertices by
decomposing each sub-tree $T_{i},1\leq i\leq n$, into at most $(k-1)$ paths
such that each path created corresponds to a vertex of $H$. The input
$(T,\\{T_{1},\ldots,T_{n}\\})$ is decomposed into paths and we get
$(T,\\{\mathcal{P}_{1},\ldots,\mathcal{P}_{n}\\})$ where
$\mathcal{P}_{i}=\mathcal{P}^{\prime}_{i}\cup\mathcal{P}^{\prime\prime}_{i},1\leq
i\leq n,$ where $\mathcal{P}^{\prime}_{i}=\\{P_{1}^{i},\ldots,P_{k/2}^{i}\\}$
and $\mathcal{P}^{\prime\prime}_{i}=\\{P_{k/2+1}^{i},\ldots,P_{k-1}^{i}\\}$
such that if we have $T$ and $\mathcal{P}^{\prime}_{i}$ we can compute
$\mathcal{P}^{\prime\prime}_{i}$.

  2. 2.

Out of the $(k-1)n$ paths, we store $kn/2$ paths of $H$ and clique tree $T$
using the data structure for path graphs given in [3]. The rest of the
$(k/2-1)n$ paths are computed from the clique tree $T$ and the stored $kn/2$
paths of $H$. In other words, for each $T_{i},\mathcal{P}^{\prime}_{i}$ is
stored and $\mathcal{P}^{\prime\prime}_{i}$ is computed from
$\mathcal{P}^{\prime}_{i}$ and $T$.

The succinct representation for $G$ consists of the following contents:

  1. 1.

$(T,\mathcal{P}^{\prime}_{1}\cup\mathcal{P}^{\prime}_{2}\cup\ldots\mathcal{P}^{\prime}_{n})$
is stored using the method for storing path graphs given in [3]. This data
structure stores the clique tree $T$ using the data structure of Lemma 2.3.

  2. 2.

for $1\leq j\leq k/2$, the mapping from indices of
$P_{j}^{i}\in\mathcal{P}^{\prime}_{i}$ to the indices of paths in the data
structure of [3] that stores
$(T,\mathcal{P}^{\prime}_{1}\cup\mathcal{P}^{\prime}_{2}\cup\ldots\cup\mathcal{P}^{\prime}_{n})$
as mentioned in the above step.

We first present the method to transform a $k-$vertex leafage chordal graph
$G$ to path graph $H$ with $(k-1)n$ vertices followed by the construction of
the data structure.

###  4.1 Transforming $(T,\\{T_{1},\ldots,T_{n}\\})$ to
$(T,\mathcal{P}^{\prime}_{1}\cup\ldots\cup\mathcal{P}^{\prime}_{n})$

The transformation from $(T,\\{T_{1},\ldots,T_{n}\\})$ to
$(T,\mathcal{P}^{\prime}_{1}\cup\ldots\cup\mathcal{P}^{\prime}_{n})$ happens
in two steps as below:

  1. a.

pre-process the clique tree $T$ into an ordinal tree, and

  2. b.

decompose each $T_{i},1\leq i\leq n$, into
$\mathcal{P}^{\prime}_{i}\cup\mathcal{P}^{\prime\prime}_{i}$.

Pre-processing is done using the method as explained in Section 3 of [3]. We
describe it here for ease of reading.

Pre-processing the Clique Tree. Fix a root node for $T$ and perform heavy path
decomposition on it. For $v\in V(T)$ order its children $(w_{1},\ldots,w_{c})$
such that $\\{v,w_{1}\\}$ is a heavy edge. Let the children adjacent to $v$ by
light edges $(w_{2},\ldots,w_{c})$, be ordered arbitrarily. This ordering of
children of a node of the clique tree makes it an ordinal tree. Label the
nodes of this ordinal tree based on the pre-order traversal; see Section 12.1
of [7] for more details of the pre-order traversal of trees. Labels assigned
to nodes in this manner are called the pre-order labels of the nodes.
Throughout the rest of our paper, this ordinal rooted clique tree labeled with
pre-order will be referred to as the clique tree; see Section 3 of [3] for
more details. After pre-processing, $T$ is an ordinal tree on which heavy-path
decomposition is performed such that all heavy edges are left aligned and
nodes are numbered based on the order in which they are visited in the pre-
order traversal of $T$. Since $G$ is $k-$vertex leafage chordal graph, the
number of leaves of $T_{i}$ is at most $k$. We obtain the clique tree
representation of the path graph $H\in\mathcal{G}_{k}(2,(k-1)n)$, denoted
$(T,\mathcal{P}^{\prime}_{1}\cup\mathcal{P}^{\prime\prime}_{1}\cup\ldots\cup\mathcal{P}^{\prime}_{n}\cup\mathcal{P}^{\prime\prime}_{n})$,
by carefully selecting the $k-1$ paths from sub-tree $T_{i},1\leq i\leq n$.
The function getPaths that does this is explained next.

Function getPaths. Given the sub-tree $T_{i}$ of $T$ with number of leaves at
most $k$, the function returns the set of paths $\mathcal{P}^{\prime}_{i}$
such that:

  1. 1.

$|\mathcal{P}^{\prime}_{i}|\leq k/2$,

  2. 2.

$\mathcal{P}^{\prime}_{i}$ along with $T$ can uniquely determine
$\mathcal{P}^{\prime\prime}_{i}$, and

  3. 3.

$T_{i}=\mathcal{P}^{\prime}_{i}\cup\mathcal{P}^{\prime\prime}_{i}$.

The function can be implemented as follows. Let the leaves of $T_{i}$ labeled
based on the order in which nodes are visited in the pre-order traversal of
the clique tree, be $\\{l_{1},\ldots,l_{k_{i}}\\},k_{i}\leq k$. For $1\leq
j\leq k_{i}/2$, pair the smallest leaf $l_{j}$ with the largest leaf
$l_{k_{i}-j+1}$ to get path $P_{j}$. Let the set of paths obtained from
$T_{i}$ be denoted by $\mathcal{P}^{\prime}_{i}$.

Ordering Paths in $\mathcal{P}^{\prime}_{i}$. Let
$\mathcal{P}^{\prime}_{i}=\\{P_{1}^{i},\ldots,P_{k_{i}}^{i}\\},1\leq k_{i}\leq
k/2$. For $1\leq j<j^{\prime}\leq k_{i}/2,$ $P_{j}^{i}=(a_{j},b_{j})$ and
$P_{j^{\prime}}^{i}=(a_{j^{\prime}},b_{j^{\prime}})$,
$P_{j}^{i}\prec_{\mathcal{P}}P_{j^{\prime}}^{i}$ if $a_{j}\leq
a_{j^{\prime}}\leq b_{j^{\prime}}\leq b_{j}$. $\prec_{\mathcal{P}}$ is a total
order on $\mathcal{P}_{i}$, since for any two paths
$P_{j}^{i},P_{j^{\prime}}^{i}\in\mathcal{P}_{i}$, either $a_{j}\leq
a_{j^{\prime}}\leq b_{j^{\prime}}\leq b_{j}$ or $a_{j^{\prime}}\leq a_{j}\leq
b_{j}\leq b_{j^{\prime}}$.

Relation Between $P_{j}^{i},P_{j+1}^{i}\in\mathcal{P}^{\prime}_{i}$. For
$1\leq j\leq k/2-1$, the paths connecting $P_{j}^{i}$ and $P_{j+1}^{i}$ are
the paths in $\mathcal{P}^{\prime\prime}_{i}$. They are computed using the
function connector. Let $P_{j}^{i}=(a_{j},b_{j})$ and
$P_{j+1}^{i}=(a_{j+1},b_{j+1})$. We define connector based on the following
two conditions:

  1. 1.

$P_{j}^{i}$ and $P_{j+1}^{i}$ are not intersecting: Since
$P_{j}^{i}\prec_{\mathcal{P}}P_{j+1}^{i}$ and $P_{j+1}^{i}$ is contained
inside a sub-tree rooted at $\texttt{lca}(a_{j},b_{j})$,
$\texttt{connector}(i,j,j+1)=(\texttt{lca}(a_{j},b_{j}),\texttt{lca}(a_{j+1},b_{j+1}))$
connects $P_{j}^{i}$ and $P_{j+1}^{i}$.

  2. 2.

$P_{j}^{i}$ and $P_{j+1}^{i}$ are intersecting:
$\texttt{connector}(i,j,j+1)=\texttt{NULL}$ in this case.

We have the following useful lemmas.

######  Lemma 4.1.

For $1\leq i\leq n$, the following holds:

  1. 1.

$|\mathcal{P}^{\prime}_{i}|\leq k/2$ and $|\mathcal{P}^{\prime\prime}_{i}|\leq
k/2-1$,

  2. 2.

${T_{i}=\mathcal{P}^{\prime}_{i}\cup\mathcal{P}^{\prime\prime}_{i}}$ where
${\mathcal{P}^{\prime\prime}_{i}=\texttt{connector}(i,1,2)\cup\texttt{connector}(i,2,3)\cup\ldots\cup}$
${\texttt{connector}(i,k_{i}/2-1,k_{i}/2)}$, and

  3. 3.

$T=\bigcup\limits_{i=1}^{n}F_{i}$ where
${F_{i}=\mathcal{P}^{\prime}_{i}\cup\mathcal{P}^{\prime\prime}_{i}}$.

######  Proof 4.2.

The proofs are as follows:

  1. 1.

There are at most $k$ leaves and every leaf is paired with another to get a
path. Thus, the number of paths is $k/2$. In the case of odd number of leaves,
we get a path with endpoints $(a,b)$ where $a$ and $b$ are the leaf and root
of $T_{i}$, respectively. Thus, the number of paths in $\mathcal{P}_{i}$ is
$\lceil k/2\rceil$.

  2. 2.

A tree $T^{\prime}$ is the union of paths from the leaves to the root. We will
prove that there is a path from every endpoint of $\mathcal{P}_{i}$ to the
root of $T_{i}$. The proof is by induction on number of leaves of $T_{i}$. As
the base case we have for $l=2$, $T_{i}=P_{1}$. We can see that the result is
true as there are no connectors. Let it be true for some $l^{\prime}>1$.
Consider the path $P_{j}^{\prime},j^{\prime}\leq(l^{\prime}+1)/2$, obtained by
pairing the last two available leaves as per the algorithm of getPaths. Then,
there are two cases to consider.

    1. (a)

$P_{j^{\prime}-1},P_{j^{\prime}}$ are intersecting: In this case, adding
$P_{j^{\prime}}$ to $\mathcal{P}_{i}$ will ensure that
$T_{i}=\mathcal{P}_{i}\cup\texttt{connector}(i,1,2)\cup\texttt{connector}(i,2,3)\cup\ldots\cup\texttt{connector}(i,k_{i}/2-1,k_{i}/2),k_{i}=l^{\prime}+1$
where $\texttt{connector}(i,k_{i}/2-1,k_{i}/2)=\texttt{NULL}$. Since
$P_{j^{\prime}-1},P_{j^{\prime}}$ are intersecting there is a path from the
end points of $P_{j^{\prime}}$ to the root of $T_{i}$.

    2. (b)

$P_{j^{\prime}-1},P_{j^{\prime}}$ are non-intersecting: In this case, adding
$P_{j^{\prime}}$ to $\mathcal{P}_{i}$ and
$\texttt{connector}(i,k_{i}/2-1,k_{i}/2)\neq\texttt{NULL}$ will ensure that
$T_{i}=\mathcal{P}_{i}\cup\texttt{connector}(i,1,2)\cup\texttt{connector}(i,2,3)\cup\ldots\cup\texttt{connector}(i,k_{i}/2-1,k_{i}/2),k_{i}=(l^{\prime}+1)/2$.
Since $\texttt{connector}(i,k_{i}/2-1,k_{i}/2)\neq\texttt{NULL}$ it connects
$P_{j^{\prime}-1}$ and $P_{j^{\prime}}$ and thus, there is a path from end
points of $P_{j^{\prime}}$ to the root of $T_{i}$.

  3. 3.

Since, $T=\bigcup\limits_{i=1}^{n}T_{i}$ is a property of chordal graphs and
$T_{i}=F_{i}$ as shown above; see 2.1 for characterisations of chordal graphs.

######  Lemma 4.3.

For $1\leq j\leq k_{i}/2$, let $P_{j}^{i}\in\mathcal{P}^{\prime}_{i}$ such
that $P_{j}^{i}=(a_{j}^{i},b_{j}^{i})$,
$e={\texttt{lca}}(a_{j}^{i},b_{j}^{i})$ and $Q_{1}=(e,b_{j}^{i})$. Also, let
${\texttt{connector}(i,j,j+1)\neq\texttt{NULL}}$. Then,

  1. 1.

$(e,c)\in E(Q)$ is a light edge, and

  2. 2.

$(e,c^{\prime})\in E({\texttt{connector}}(i,j,j+1))$ is a light edge.

Finally, we have the following proposition and lemma regarding adjacency and
neighbourhood of $v\in V(G)$.

######  Proposition 4.4.

$\\{u,v\\}\in E(G)$ if and only if there exists
$P\in\mathcal{P}^{\prime}_{u}\cup\mathcal{P}^{\prime\prime}_{u},Q\in\mathcal{P}^{\prime}_{v}\cup\mathcal{P}^{\prime\prime}_{v}$,
such that $P\cap Q\neq\phi$.

For $1\leq j\leq k_{v},1\leq j^{\prime}\leq k_{v}-1$, let $\beta(P_{j}^{v})$
and $\beta(\texttt{connector}(v,j^{\prime},j^{\prime}+1))$ represent the paths
in
$\mathcal{P}^{\prime}_{i}\cup\mathcal{P}^{\prime\prime}_{i}\cup\ldots\cup\mathcal{P}^{\prime}_{n}\cup\mathcal{P}^{\prime\prime}_{n}$
intersecting $P_{j}^{v}$ and $\texttt{connector}(v,j^{\prime},j^{\prime}+1)$,
respectively.

######  Lemma 4.5.

For $1\leq i\leq n$, let
$\mathcal{P}_{i}=\mathcal{P}^{\prime}_{i}\cup\mathcal{P}^{\prime\prime}_{i}$.
For $P\in\mathcal{P}_{i}$ the following holds:

  1. 1.

$|\beta(P)|\leq(k-1)d_{i}$, and

  2. 2.

$\sum\limits_{P\in\mathcal{P}_{i}}|\beta(P)|\leq(k-1)^{2}d_{i}$ where $d_{i}$
is degree of $v_{i}\in V(G)$.

######  Proof 4.6.

By Lemma 4.1, the tree $T_{i}$ corresponding to $v_{i}\in V(G)$ is decomposed
into set of paths
$\mathcal{P}_{i}=\mathcal{P}^{\prime}_{i}\cup\mathcal{P}^{\prime\prime}_{i}$.

  1. 1.

Since each $P\in\mathcal{P}^{\prime}_{i}$ can have at most $d_{i}$ trees
corresponding to vertices of $G$ intersecting it and each tree has at most
$k-1$ paths in the path graph $H$, we have $|\beta(P)|\leq(k-1)d_{i}$.

  2. 2.

$\sum\limits_{P\in\mathcal{P}_{i}}|\beta(P)|\leq(k-1)^{2}d_{i}$, since
$|\mathcal{P}_{i}|=k-1$ and $|\beta(P)|\leq(k-1)d_{i}$.

###  4.2 Construction

Index of Paths in $G$ and $H$. For
$P_{1}^{i},\ldots,P_{k_{i}}^{i}\in\mathcal{P}^{\prime}_{i}$, we index paths of
$G$ and $H$ in the following ways:

  1. 1.

in $G$ paths are ordered
$\\{P_{1}^{1},\ldots,P_{k_{1}}^{1},\ldots,P_{1}^{n},\ldots,P_{k_{n}}^{n}\\}$
where $P_{1}^{i},1\leq i\leq n$ is in the increasing order of the starting
nodes of $P_{1}^{i}$ and for $1\leq j\leq k_{i},P_{j}^{i}$ are ordered based
on $\prec_{\mathcal{P}}$, and

  2. 2.

in $H$ paths are ordered based on their starting nodes; this is as per the
storage scheme followed in [3] for path graphs.

We will order the vertices of $G$ based on the order of the starting nodes of
the first paths $P_{1}^{i}\in\mathcal{P}_{i}$ of each $T_{i}$. The data
structure for $k-$vertex leafage chordal graphs consists of the following
components.

Path Graph $H$. The path graph $H$ that we store is
$(T,\bigcup\limits_{i=1}^{n}\mathcal{P}^{\prime}_{i})$ where
$|\bigcup\limits_{i}\mathcal{P}^{\prime}_{i}|\leq nk/2$. For $1\leq i\leq n$,
we do not store
$\texttt{connector}(i,1,2),\texttt{connector}(i,2,3),\ldots,\\\
\texttt{connector}(i,k_{i}-1,k_{i})$ but compute it when required. In other
words, $T_{i}$ can be computed from $T$ and $\mathcal{P}^{\prime}_{i}$. Thus,
path graph $H$ can be stored using $\frac{nk}{2}\log n+o(nk\log n)$ bits as
per Lemma 2.7. The data structures used in the succinct representation of path
graphs as given in Lemma 2.7 does not require $T$ to be a clique tree of $H$
as long as the number of nodes in $T$ is constant times $|V(H)|$, so
$(T,\bigcup\limits_{i=1}^{n}\mathcal{P}_{i})$ is a valid input that represents
$H$.

Array $K$. $K$ is a one dimensional array of length $n$. For $1\leq i\leq
n,K[i]$ stores $|\mathcal{P}^{\prime}_{i}|$, that is, the number of paths that
the sub-tree $T_{i}$ gets decomposed into. $K$ takes at most $n\log k$ bits of
space. The following function is supported.

  * •

$\texttt{getSize}(i):$ Given $1\leq i\leq n,$ the function returns $K[i]$ else
0.

Bit-vector $F$. $F$ is a bit vector of length at most $kn/2$. Let the index of
the first path of each vertex in the order
$(P_{1}^{1},\ldots,P_{k_{1}}^{1},\ldots,P_{1}^{n},\ldots,P^{n}_{k_{n}})$ be
$\\{i_{1},\ldots,i_{n}\\}$ where $P_{j}^{i}\in\mathcal{P}^{\prime}_{i},1\leq
i\leq n,1\leq j\leq k_{i}$. Since the vertices are numbered based on the start
node of their first paths, $\\{i_{1},\ldots,i_{n}\\}$ is an increasing
sequence of numbers with maximum value of $kn/2$ and can be stored using the
differential encoding scheme of Lemma 2.5. This data structure is also denoted
by $F$ and takes at most $kn+o(kn)$ bits of space. The following function is
supported.

  * •

$\texttt{getIndex}(i):$ Given $1\leq i\leq n,$ the function returns
$\texttt{accessNS}(i,F)$ else 0. $\texttt{accessNS}(i,F)$ returns the value at
the $i-$th position in the sequence $\\{i_{1},\ldots,i_{n}\\}$.

Bit-vector $D$. Consider the order of paths
$O=(P_{1}^{1},\ldots,P_{k_{1}}^{1},\ldots,P_{1}^{n},\ldots,P_{k_{n}}^{n})$.
For $1\leq j\leq kn/2,D[j]=i$ if $O[j]$ is a path corresponding to $u_{i}\in
V(G)$. Since $D$ is an increasing sequence it can be stored using the data
structure of Lemma 2.5 taking $O(kn)$ bits. $D$ contains at most $n$ 1’s and
$kn/2$ 0’s.

Permutation $\pi$. $\pi$ store the mapping of indices of paths in $H$ to paths
in $G$ by storing the indices of paths
$(P_{2}^{1},\ldots,P_{k_{1}}^{1},\ldots,P_{2}^{n},\ldots,P^{n}_{k_{n}})$ in
$G$ in that order. $\pi$ is stored using the data structure of Lemma 2.8 and
takes $\left(\frac{k}{2}-1\right)n\log n+o(kn\log n)$ bits of space.

Function alpha. The function alpha takes $1\leq i\leq n$, as input and returns
the indices of paths in $\mathcal{P}^{\prime}_{i}$ corresponding to $u_{i}\in
V(G)$ in the clique tree representation of $H$. Function returns
$\\{\pi(p),\ldots,\pi(p+s)\\}$ where $p\leftarrow\texttt{getIndex}(i)-i+1$ and
$s\leftarrow\texttt{getSize}(i)$. $\texttt{getIndex}(i)-i+1$ is the index of
$P_{2}^{i}$ in
$(P_{2}^{1},\ldots,P_{k_{1}}^{1},\ldots,P_{2}^{n},\ldots,P^{n}_{k_{n}})$.

######  Lemma 4.7.

Given the index $1\leq i\leq n$, of $u_{i}\in V(G)$, ${\texttt{alpha}(i)}$
returns the indices in $H$ of paths in $\mathcal{P}^{\prime}_{i}$
corresponding to $u_{i}$ in $O(k_{i})$ time.

Bit-vector $C$. $C$ is an array of $n$ bit-vectors each of length $(k/2-1$.
For $1\leq i\leq n,1\leq j\leq k/2-1$, $C[i][j]=1$ if
$\texttt{connector}(i,j,j+1)\neq\texttt{NULL}$ else $C[i][j]=0$. $C$ takes a
total space of $n(k/2-1)$ bits. The following function is supported.

  * •

$\texttt{isConnector}(i,j):$ Given $1\leq i\leq n,1\leq j\leq k/2-1$, the
function returns true if $C[i][j]=1$ else false.

Function getCPath. For $1\leq i\leq n,1\leq j\leq k_{i}/2-1$ and
$P_{j}^{i}=(a_{j},b_{j}),P_{j+1}^{i}=(a_{j^{\prime}},b_{j^{\prime}})$, the
function takes paths $P_{j}^{i}$ and $P_{j+1}^{i}$ as input and returns
$\texttt{connector}(i,j,j+1)$ if $\texttt{isConnector}(i,j))$ is true else
NULL. Note that $H$ stored as per Lemma 2.7 contains the clique tree $T$ and
this allows us to perform the lca operation.

######  Lemma 4.8.

For $1\leq i\leq n,1\leq j\leq k_{i}/2-1,$ given paths $P_{j}^{i},P_{j+1}^{i}$
as input, the function ${\texttt{getCPath}(P_{j}^{i},P_{j+1}^{i})}$ returns
${\texttt{connector}(i,j,j+1)}$ in constant time.

######  Proof 4.9.

We have $P_{j}^{i}=(a_{j},b_{j}),P_{j+1}^{i}=(a_{j^{\prime}},b_{j^{\prime}})$
as input. Using $T$ stored in the data structure of $H$ and lca of Lemma 2.3
we can check if $\texttt{isConnector}(i,j))$ is true. If true then we can get
$\texttt{connector}(i,j,j+1)=(\texttt{lca}(a_{j},b_{j}),\texttt{lca}(a_{j^{\prime}},b_{j^{\prime}}))$
in constant time as lca takes constant time. Else,
$\texttt{connector}(i,j,j+1)=\texttt{NULL}$. So
$\texttt{getCPath}(P_{j}^{i},P_{j+1}^{i})$ can be completed in constant time.

######  Lemma 4.10.

For $k\in o(n/\log n)$, there exists a $(k-1)n\log n+o(kn\log n)$-bit succinct
data structure for the class of $k-$vertex leafage chordal graphs.

######  Proof 4.11.

The data structure for $k-$vertex leafage chordal graphs consists of the
following components:

  1. 1.

$H$ takes $\frac{nk}{2}\log n+o(nk\log n)$ bits of space,

  2. 2.

$K$ takes $n\log k$ bits of space,

  3. 3.

$F,C,$ and $D$ take $O(kn)$ bits of space each, and

  4. 4.

$\pi$ takes $\left(\frac{k}{2}-1\right)n\log n+o(kn\log n)$ bits of space.

Thus, the total space taken is $(k-1)n\log n+o(kn\log n)$ bits. From Theorem
1.1 we have,$\geq(k-1)n\log n\leq\log|\mathcal{G}_{k}|+\frac{3kn}{2}\log
k+\frac{3kn}{2}+O(\log n)$. Substituting in $(k-1)n\log+o(kn\log n)$ we have,

$\displaystyle(k-1)n\log n+o(kn\log n)$
$\displaystyle\leq\log|\mathcal{G}_{k}|+\frac{3kn}{2}\log
k+\frac{3kn}{2}+O(\log n)$
$\displaystyle\leq\log|\mathcal{G}_{k}|+o((k-1)n\log n)$

Using Proposition 3.18, we have,

$\displaystyle(k-1)n\log n+o(kn\log n)$
$\displaystyle\leq\log|\mathcal{G}_{k}|+o(\log|\mathcal{G}_{k}|)$

Thus, the data structure is succinct.

Figure 1: (a) An example 4-vertex leafage chordal graph $G$, (b) clique tree
representation of $G$ after pre-processing, (c) the index of the paths
generated from the sub-trees along with their start node (second row), end
node (third row), and index (forth row), (d) the components of the succinct
data structure for $G$.

###  4.3 Adjacency and Neighbourhood Queries

The following lemma is useful.

######  Lemma 4.12.

Let $T_{i}$ and $T_{i^{\prime}}$ intersect and
$P_{1}^{i}=(a_{1}^{i},b_{1}^{i}),P_{1}^{i^{\prime}}=(a_{1}^{i^{\prime}},b_{1}^{i^{\prime}})$.
Wlog,

  1. 1.

if $a_{1}^{i}\leq a_{1}^{i^{\prime}}\leq b_{1}^{i^{\prime}}\leq b_{1}^{i}$,
then

    1. a.

there exists $P_{j}^{i},1\leq j\leq k_{i}/2$ such that $P_{j}^{i}\cap
P_{1}^{i^{\prime}}\neq\phi$, or

    2. b.

there exists ${\texttt{connector}}(i,j,j+1)\cap
P_{j}^{i^{\prime}}\neq\phi,1\leq j\leq k_{i}/2-1$.

  2. 2.

Else, $a_{1}^{i}\leq a_{1}^{i^{\prime}}\leq b_{1}^{i}\leq b_{1}^{i^{\prime}}$
or $a_{1}^{i^{\prime}}\leq a_{1}^{i}\leq b_{1}^{i^{\prime}}\leq b_{1}^{i}$.

Adjacency Query. Given indices of two vertices $u_{i},u_{j}\in V(G)$ and the
succinct representation for the $k-$vertex leafage chordal graphs, the
adjacency query returns true if $\\{u_{i},u_{j}\\}\in E(G)$ else false. The
characterisation of $\\{u_{i},u_{j}\\}\in E(G)$ in terms of path intersections
in $(T,\mathcal{P}_{1}\cup\ldots\cup\mathcal{P}_{n})$ where
$\mathcal{P}_{i}=\mathcal{P}^{\prime}_{i}\cup\mathcal{P}^{\prime\prime}_{i},1\leq
i\leq n,$ is given by Proposition 4.4. Algorithm 1 gives an implementation of
the adjacency query.

1 Function  _adjacency(_$i,j$_)_:

2
$\mathcal{P}^{\prime}_{i}\leftarrow\texttt{alpha}(i),\mathcal{P}^{\prime}_{j}\leftarrow\texttt{alpha}(j),s\leftarrow\texttt{NULL}$

3 Let $P_{1}^{i}=(a_{1}^{i},b_{1}^{i})$ and $P_{1}^{j}=(a_{1}^{j},b_{1}^{j})$
obtained using $\texttt{pathep}(\texttt{getIndex}(i))$ and
$\texttt{pathep}(\texttt{getIndex}(j))$, respectively.

4 Check if $P_{1}^{i}$ and $P_{1}^{j}$ intersect as follows:

5 if  _${\texttt{adjacencyPG}(H,P_{1}^{i},P_{1}^{j})}$ is true_ then

6 return true

7

8 Check if endpoints of first path of one falls within the range of the end
points of the first path of the other as follows:

9 if  _$a_{1}^{i}\leq a_{1}^{j}\leq b_{1}^{j}\leq b_{1}^{i}$_ then

10 $s\leftarrow i$

11

12 if  _$a_{1}^{j}\leq a_{1}^{i}\leq b_{1}^{i}\leq b_{1}^{j}$_ then

13 $s\leftarrow j$

14

15 if  _${s\neq\texttt{NULL}}$_ then

16 if  _$s=i$_ then

17 foreach  _${1\leq t\leq\texttt{getSize}(i)-1}$_ do

18 if
_${\texttt{adjacencyPG}(H,\texttt{pathep}(\mathcal{P}^{\prime}_{i}[t]),\texttt{pathep}(\mathcal{P}^{\prime}_{j}[1]))}$
is true_ then

19 return true

20

21 foreach  _${2\leq t\leq\texttt{getSize}(i)-1}$_ do

22 if  _$t=2$ and
${\texttt{adjacencyPG}(H,\texttt{getCPath}(\texttt{getIndex}(i),\mathcal{P}^{\prime}_{i}[t]),\texttt{pathep}(\mathcal{P}^{\prime}_{j}[1]))}$
is true_ then

23 return true

24

25 else

26 if
_${\texttt{adjacencyPG}(H,\texttt{getCPath}(\mathcal{P}^{\prime}_{i}[t-1],\mathcal{P}^{\prime}_{i}[t]),\texttt{pathep}(\mathcal{P}^{\prime}_{j}[1]))}$
is true_ then

27 return true

28

29

30

31

32 if  _$s=j$_ then

33 Perform the same steps as done in Line 15 for the case $s=i$ with $i$ and
$j$ interchanged.

34

35 return false

36

Algorithm 1 Given indices $i,j$ as input, the function returns true if
$\\{u_{i},u_{j}\\}\in E(G)$ else false.

######  Lemma 4.13.

For $k\in o(n/\log n)$, the class of $k-$vertex leafage chordal graphs have a
$(k-1)n\log n+o(kn\log n)$ bit succinct data structure that supports adjacency
query in $O(k\log n)$ time.

######  Proof 4.14.

As per Lemma 4.10, $k-$vertex leafage chordal graphs have a $(k-1)n\log
n+o(kn\log n)$ bit succinct data structure. Given the succinct representation
and indices $i,j$ of vertices in $G$, Algorithm 1 checks if
$\\{u_{i},u_{j}\\}\in E(G)$. In Line 1 of Algorithm 1, the paths corresponding
to $T_{i}$ and $T_{j}$ are obtained using alpha of Lemma 4.7 and in Line 2,
the endpoints of $P_{1}^{i}$ and $P_{1}^{j}$ are obtained using pathep of
Lemma 2.7. The endpoints $(a_{t}^{i},b_{t}^{i})$ of
$P_{t}^{i}\in\\{P_{1}^{i},\ldots,P_{k_{i}}^{i}\\}$ is such that $a_{1}^{i}\leq
a_{t}^{i}\leq b_{t}^{i}\leq b_{1}^{i}$; same is true for $j$. The following
two cases arise based on Lemma 4.12:

  1. 1.

$P_{1}^{i}$ and $P_{1}^{j}$ are not contained inside each other: If the sub-
trees intersect then, this corresponds to the case (b) of Lemma 4.12. In this
case, we check if $P_{1}^{i}$ and $P_{1}^{j}$ intersect or not. In Algorithm
1, this is done in Lines 4 to 6.

  2. 2.

$P_{1}^{j}$ is contained inside the sub-tree rooted at
$\texttt{lca}(a_{1}^{i},b_{1}^{i})$ or vice versa: If the sub-trees intersect
then, this corresponds to the case (a) of Lemma 4.12. Wlog let $P_{1}^{j}$ be
contained inside the sub-tree rooted at $\texttt{lca}(a_{1}^{i},b_{1}^{i})$ as
shown in Line 8 of Algorithm 1. In this case we need to check if $P_{1}^{j}$
intersects any one of $P_{t}^{i},2\leq t\leq k$. If $P_{1}^{j}$ does not
intersect any one of $P_{t}^{i}$ then no other path of $u_{i}$ will intersect
any path $P_{t}^{i}$. This is because the root of the sub-tree $T_{j}$ is
$\texttt{lca}(a_{1}^{j},b_{1}^{j})$. The adjacency check is done using the
adjacencyPG function of path graphs data structure of Lemma 2.7 and takes
$O(k\log n)$ time for $k$ paths of $u_{i}$. This case is handled in Lines 15
to 24.

The function returns false if all the other checks fail to return true. By
Lemma 4.7, alpha takes $O(k)$ time. By Lemma 2.7, pathep and adjacencyPG take
$O(\log n)$ time. Also, getSize and getIndex takes constant time. Each of the
loops run at most $k$ times with loop body taking at most $O(\log n)$ time.
Thus, the total time to finish adjacency function is $O(k\log n)$.

Neighbourhood Query. Given $v\in V(G)$ and the succinct representation of
$k-$vertex leafage chordal graph $G$, the neighbourhood query returns the
neighbours of $v$. We use the following additional data structure.

Array $Y$. $Y$ is a one dimensional array of length at most $n$ that stores an
array at each of its locations. For $1\leq i\leq n$, $Y[i]$ stores the array
of records where each record is of the form $(r,s)$ such that $1\leq r\leq n$
is the index of the sub-tree that has node $u_{i}\in V(T)$ as the lca of
endpoints of $P_{1}^{r}$ and for $1\leq s\leq n$, node $u_{s}$ as the lca of
endpoints of $P_{k_{r}}^{r}$. The records at $Y[i]$ are stored in the
increasing order of $s$. The total space taken by $Y$ is $2n\log n$ bits as
each tree takes $2\log n$ bits and there are $n$ trees. The following function
is supported.

  * •

$\texttt{getNhb}(l,l^{\prime},a)$: Given $1\leq l,l^{\prime}\leq n,$ the
function returns the list of trees with index $1\leq j\leq n$, such that lca
of endpoints of $P_{1}^{j}$ is equal to $l$ and lca of endpoints of
$P_{k_{j}}^{j}$ greater than or equal to $l^{\prime}$ and less than or equal
to $a$ in $O(\log n+d)$ time where $d$ is the number of trees returned. The
function can be implemented as follows:

    1. 1.

Performing binary search on the array $A$ of records at $Y[l]$ to first obtain
the range of $s$ values greater than or equal to $l^{\prime}$. Let this range
be $[p_{1},p_{2}]$.

    2. 2.

Performing second binary search on $A[p_{1},p_{2}]$ to obtain the range of $s$
values that are less than or equal to $a$ in $A[p_{1},p_{2}]$. Let this range
be $[p^{\prime}_{1},p^{\prime}_{2}]$.

    3. 3.

Return the indices of trees, that is, the $r$ values stored in records
$A[p^{\prime}_{1},p^{\prime}_{2}]$.

The binary search takes $O(\log n)$ time and the tree indices are returned in
$d$ time where $d=p^{\prime}_{2}-p^{\prime}_{1}+1$. Thus, getNhb takes a total
time of $O(\log n+d)$.

Algorithm 2 gives an implementation of the neighbourhood query.

1 Function  _neighbourhood(_$i$_)_:

2
$\mathcal{P}^{\prime}_{i}\leftarrow\texttt{alpha}(i),\mathcal{P}\leftarrow\phi$

3 Add $\texttt{pathep}(\texttt{getIndex}(i))$ to $\mathcal{P}$

4 foreach  _${j\in\mathcal{P}^{\prime}_{i}}$_ do

5 Add $\texttt{pathep}(j)$ to $\mathcal{P}$

6

7 Add $\texttt{getCPath}(\texttt{getIndex}(i),\mathcal{P}^{\prime}_{i}[1])$ to
$\mathcal{P}$ if it is not NULL

8 foreach  _${1\leq j\leq\texttt{getSize}(i)-1}$_ do

9 Add
$\texttt{getCPath}(\mathcal{P}^{\prime}_{i}[j],\mathcal{P}^{\prime}_{i}[j+1])$
to $\mathcal{P}$ if it is not NULL

10

11 $N\leftarrow\phi$

12 Let $t$ be a bit-vector of length $n$ initialised to 0

13 foreach  _$(a,b)\in\mathcal{P}$_ do

14 $N^{\prime}\leftarrow\texttt{neighbourhoodPG}(a,b)$

15

16 foreach  _$j^{\prime}\in N^{\prime}$_ do

17 $p\leftarrow\pi^{-1}(j^{\prime})$

18 if  _$t[p]\neq 1$_ then

19 Add $D[p]$ to $N$

20 $t[p]\leftarrow 1$

21

22

23

24 $P_{1}^{i}\leftarrow\texttt{pathep}(\texttt{getIndex}(i))$

25 $P_{2}^{i}\leftarrow\texttt{pathep}(\mathcal{P}_{i}[1])$

26

27 Let
$P_{1}^{i}=(a_{1},b_{1}),P_{2}^{i}=(a_{2},b_{2}),l\leftarrow\texttt{lca}(a_{1},b_{1}),l^{\prime}\leftarrow
l$

28 if  _${\texttt{lmost\\_child}}({\texttt{parent}}(l))=l$_ then

29 $v\leftarrow{\texttt{parent}}({\texttt{getHPStartNode}}(l))$

30

31 else

32 $v\leftarrow{\texttt{parent}}(l)$

33

34 while  _$v\neq{\texttt{NULL}}$_ do

35 Add $\texttt{getNhb}(v,l^{\prime},b_{1})$ to $N$

36 $l\leftarrow v$

37 if  _${\texttt{child}}(1,{\texttt{parent}}(l))=l$_ then

38 $v\leftarrow{\texttt{parent}}({\texttt{getHPStartNode}}(l))$

39

40 else

41 $v\leftarrow{\texttt{parent}}(l)$

42

43

44

Algorithm 2 Given index $i$ as input, the function returns the set of vertices
adjacent to $u_{i}\in V(G)$.

######  Lemma 4.15.

For $k\in o(n/\log n)$, the class of $k-$vertex leafage chordal graphs have a
$(k-1)n\log n+o(kn\log n)$ bit succinct data structure that supports
neighbourhood query for vertex $v_{i}$ in $O(k^{2}d_{i}\log n+\log^{2}n)$ time
using additional $2n\log n$ bits where $d_{i}$ is the degree of $v_{i}$.

######  Proof 4.16.

Let $G$ be a $k-$vertex leafage chordal graph and the sub-tree $T_{i}$ of
clique tree $T$ of $G$ correspond to $v_{i}\in V(G)$. Lines 2 to 8 of
Algorithm 2 decompose $T_{i}$ into paths
$\mathcal{P}=\\{P_{1}^{i},\ldots,P_{k_{i}}^{i},\texttt{connector}(i,1,2),\texttt{connector}(i,2,3),\ldots,\texttt{connector}(i,k_{i}/2-1,k_{i}/2)\\}$
as described in Lemma 4.1. In Lines 11 and 12 of Algorithm 2 we obtain the
neighbours in $H$ of all paths in $\mathcal{P}$. From Lemma 4.5, we know that
$\sum\limits_{P\in\mathcal{P}}|\beta(P)|\leq k(k-1)d_{i}/2$. Thus, total time
taken by Lines 11 and 12 is $O(k^{2}d_{i}\log n)$ as neighbourhoodPG takes
$O(d_{v_{i}}\log n)$ time. The loop at Line 13 takes $O(d_{v_{i}}f(n))$ time
as $\pi^{-1}$ take $O(f(n))$ time as per Lemma 2.8. All the sub-trees $T_{j}$
whose connectors intersect $P_{1}^{i}=(a_{1}^{i},b_{1}^{i})$ are obtained by
searching for sub-trees with lca as a node in the path connecting the root of
$T_{i}$ to root of $T$ and with a path $P_{p}^{j},1\leq p\leq k_{j}$ contained
inside sub-tree rooted at $\texttt{lca}(a_{1}^{i},b_{1}^{i})$; these are the
only connectors due to Lemma 4.12. The loop at Line 25 iterates $O(\log n)$
times till the root is reached. This is because as a consequence of Lemma 4.3,
for the connector paths we only count the light edges of $T$, as the heavy
paths are left aligned and they are part of the paths connecting the leaves.
Further, as per Lemma 6 of [3], there are at most $O(\log n)$ light edges in
any path of $T$. getNhb takes $O(\log n+d_{i})$ time and the loop at Line 21
runs $O(\log n)$ times. So total time taken by the loop is
$O(\log^{2}n+d_{i}\log n)$. Since $f(n)=o(\log n)$ as per Lemma 2.8, the total
time taken by Algorithm 2 is $O(k^{2}d_{i}\log n+\log^{2}n)$.

Thus, we have the following theorem. See 1.2

######  Proof 4.17.

From Lemma 4.10, we know that for $k\in o(n/\log n)$, the $(k-1)n\log
n+o(kn\log n)$-bit data structure is succinct. From Lemma 4.13, we know that
the data structure supports adjacency query in time $O(k\log n)$ and from
Lemma 4.15, we know that the neighbourhood query is supported in time
$O(k^{2}d_{i}\log n+\log^{2}n)$ using additional $2n\log n$ bits.

##  5 Conclusion

The parameters, leafage and vertex leafage, are defined for chordal graphs
which is a special case of intersection graphs. In comparison, boxicity and
interval number allow us to model general graphs as intersection graphs.
However, they do not give a tree model like in the case of chordal graphs. We
ask the following question: “Can leafage and vertex leafage be generalized for
any graph?" The answer is positive if we consider the nice tree-decomposition.
For any graph, the nice tree-decomposition allows us to establish a
correspondence between vertices of the graph and sub-trees of the tree
obtained. As one can see clearly, the parameters leafage and vertex leafage
become applicable to general graphs now. For chordal graphs we know that the
clique tree has nodes that correspond to the maximal cliques of the graph.
However, we lose such nice properties in the case of nice tree-decomposition.
Despite these limitations we think it is worthwhile to generalize these
parameters and design a succinct data structure for the more general class
thus formed. It is also interesting to note that a unit increase in the
leafage parameter increases the number of graphs in the class by $n\log n$ as
compared to $2n\log n$ in the case of boxicity or interval number. From
Balakrishnan et al. [4] we know that for the succinct data structure designed
for graphs with bounded boxicity $d>0$ using the succinct data structure for
interval graphs an efficient but easy implementation for neighbourhood query
is not possible. For bounded leafage parameter where the intersection model is
a tree, it will be interesting to see if there exists a simple and efficient
implementation of the neighbourhood query.

## References

  * [1] H. Acan, S. Chakraborty, S. Jo, K. Nakashima, K. Sadakane, and S.R. Satti.  Succinct navigational oracles for families of intersection graphs on a circle.  Theor. Comput. Sci., 928(C):151–166, Sep 2022.  doi:10.1016/j.tcs.2022.06.022.
  * [2] H. Acan, S. Chakraborty, S. Jo, and S. R. Satti.  Succinct encodings for families of interval graphs.  Algorithmica, 83(3):776–794, 2021.
  * [3] G. Balakrishnan, N. S. Narayanaswamy, S. Chakraborty, and K. Sadakane.  Succinct data structure for path graphs.  In 2022 Data Compression Conference (DCC), pages 262–271, 2022.  doi:10.1109/DCC52660.2022.00034.
  * [4] Girish Balakrishnan, Sankardeep Chakraborty, Seungbum Jo, N S Narayanaswamy, and Kunihiko Sadakane.  Succinct data structure for graphs with $d$-dimensional $t$-representation, 2023.  arXiv:2311.02427.
  * [5] S. Chakraborty and S. Jo.  Compact representation of interval graphs and circular-arc graphs of bounded degree and chromatic number.  Theor. Comput. Sci., 941:156–166, 2023.
  * [6] S. Chaplick and J. Stacho.  The vertex leafage of chordal graphs.  Discrete Applied Mathematics, 168:14–25, 2014.  Fifth Workshop on Graph Classes, Optimization, and Width Parameters, Daejeon, Korea, October 2011.  URL: https://www.sciencedirect.com/science/article/pii/S0166218X1200460X, doi:10.1016/j.dam.2012.12.006.
  * [7] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein.  Introduction to Algorithms, Third Edition.  The MIT Press, 3rd edition, 2009.
  * [8] M. C. Golumbic.  Algorithmic Graph Theory and Perfect Graphs.  North-Holland Publishing Co., NLD, 2004.
  * [9] A. Golynski, J. I. Munro, and S. S. Rao.  Rank/select operations on large alphabets: A tool for text indexing.  In SODA, SODA ’06, page 368–373, USA, 2006. Society for Industrial and Applied Mathematics.
  * [10] A. Itai and M. Rodeh.  Representation of graphs.  Acta Inf., 17(2):215–219, jun 1982.  doi:10.1007/BF00288971.
  * [11] G. J. Jacobson.  Space-efficient static trees and graphs.  30th Annual Symposium on Foundations of Computer Science, pages 549–554, 1989.
  * [12] I.J. Lin, T.A. McKee, and D.B. West.  The leafage of a chordal graph.  Discussiones Mathematicae Graph Theory, 18(1):23–48, 1998.  URL: http://eudml.org/doc/270535.
  * [13] J. I. Munro, R. Raman, V. Raman, and S. S. Rao.  Succinct representations of permutations and functions.  Theor. Comput. Sci., 438:74–88, 2012.
  * [14] J. I. Munro and K. Wu.  Succinct data structures for chordal graphs.  In ISAAC, volume 123 of Leibniz International Proceedings in Informatics (LIPIcs), pages 67:1–67:12, 2018.
  * [15] G. Navarro.  Compact Data Structures - A Practical Approach.  Cambridge University Press, 2016.
  * [16] G. Navarro and K. Sadakane.  Fully functional static and dynamic succinct trees.  ACM Trans. Algorithms, 10(3), May 2014.  doi:10.1145/2601073.


# Excitations of a trapped two component Bose Einstein Condensate

Christopher Ticknor  Theoretical Division, Los Alamos National Laboratory, Los
Alamos, New Mexico 87545, USA  Kavli Institute for Theoretical Physics,
University of California, Santa Barbara, California 93106, USA

###### Abstract

We present analysis of the excitation spectrum for a 2 component quasi2D Bose
Einstein Condensate. We study how excitations change character across the
miscible to immiscible phase transition. We find that the bulk excitations are
typical of a single-component BEC with the addition of interface bending
excitations. We study how these excitations change as a function of the
interaction strength.

###### pacs:

03.75Hh,67.85-d

##  I introduction

Ultracold atoms provide an excellent forum to study complex quantum mechanical
behavior. An example is the superfluid to Mott insulator transition greiner ,
where experimental efforts have imaged this as a quantum phase transition at
the single atom level bakr . A quantum phase transition is a fundamental
change in the ground state as a parameter is altered, in the superfluid-Mott
insulator example the parameter is lattice depth. Near this quantum phase
transition the temperature dependence of superfluidity and quantum criticality
has been studied trotzky ; zhang .

Another system in ultracold atoms, which exhibits a quantum phase transition,
is the 2 component Bose Einstein Condensate (BEC), where by tuning the
interactions between the components the gas can change from a miscible to an
immiscible phase, as has been experimentally demonstrated in Rb papp .
Theoretical studies showed that if $g_{11}g_{22}-g_{12}^{2}$ is greater (less)
than zero, the gas is miscible (immiscible) pu ; eddy . Here $g_{ij}$ is the
coupling strength in the mean field treatment between the $i^{th}$ and
$j^{th}$ component. Interestingly, 2 component BECs have been used to create
vortices matthews  and study non-equilibrium dynamics mertes ; anderson ;
nicklas .

In this work, we look at the character of the excitations across the quantum
phase transition in the 2 component BEC system. For a miscible system, the
modes are collective in nature, and the condensates move either in-phase or
out-of-phase with each other. For the immiscible system, the excitations are
either collective or interface excitations. This work offers a new perspective
into the nature the miscible-immiscible transition with characterization of
the excitations.

There has been previous work on excitation spectra for trapped 2 component BEC
gordon . That work studied symmetry breaking as a function of particle number
and found that a mode goes to zero when the system becomes immiscible, but
they did not study the nature of the quasiparticles. Ref. kim  studied the
ground state and characterized the mode that goes soft (energy goes to zero),
here we extend the analysis to many low-lying modes of the system.

##  II methods

To obtain the excitation spectrum, we solve the Bogoliubov de Gennes equations
pu ; eddy  for a trapped gas with contact interactions. First, we must solve
the Gross Pitaevskii equation for the 2 condensates ($\phi_{i}$):

$\displaystyle
H_{GP}\phi_{i}=\left(H_{0}+\sum_{j}g_{ij}|\phi_{j}|^{2}\right)\phi_{i}=\mu_{i}\phi_{i}.$
(1)

$H_{0}$ is the kinetic energy and trapping potential and $\mu_{i}$ is the
chemical potential for the $i^{th}$ component. We normalize $\phi_{i}$ so that
$\int dV|\phi_{i}|^{2}$=1. Now we consider the ground state and its
excitations to be of the form:
$e^{-i\mu_{i}t/\hbar}\\{\phi_{i}+\lambda(u_{i}e^{-i\omega
t}+v_{i}^{*}e^{i\omega t})\\}$. Substituting this into the time dependent
version of Eq. (1) and collecting powers of $e^{\pm i\omega t}$ and linear
terms in $\lambda$, we find the excitations are given by:

$\displaystyle\left(\begin{array}[]{cc}H_{GP}-\mu_{i}&0\\\ 0&H_{GP}-\mu_{i}\\\
\end{array}\right)\left(\begin{array}[]{c}u_{i}^{\alpha}\\\
v_{i}^{\alpha}\end{array}\right)$ (6)
$\displaystyle+\sum_{j}\left(\begin{array}[]{cc}g_{ij}\phi_{i}\phi_{j}&g_{ij}\phi_{i}\phi_{j}\\\
g_{ij}\phi_{i}\phi_{j}&g_{ij}\phi_{i}\phi_{j}\end{array}\right)\left(\begin{array}[]{c}u_{j}^{\alpha}\\\
v_{j}^{\alpha}\end{array}\right)=\omega_{\alpha}\left(\begin{array}[]{c}u_{i}^{\alpha}\\\
-v_{i}^{\alpha}\end{array}\right).$ (13)

We have assumed $\phi_{i}$ is real, and that the different components have
equal number and mass. The second term contains both the exchange and
anomalous term, which couples $u_{i}^{\alpha}$ to $u_{j}^{\alpha}$ and
$u_{i}^{\alpha}$ to $v_{j}^{\alpha}$, respectively. These terms would be non-
local if the interaction was finite range. These excitations are normalized in
the standard way: $\int dV|u^{\alpha}|^{2}$-$|v^{\alpha}|^{2}=1$ fetter .

To perform this work, we focus on the quasi2D case where high resolution
experimental imaging is possible chicago ; bakr . For clarity, we will focus
on two examples: one is miscible and the other immiscible, both far away from
the transition so the character of the excitations is clear. We consider
$g_{11}=g=$100 and $g_{22}$=1.01g; for the miscible example, we pick
$g_{12}$=0.5g and an immiscible example, we pick $g_{12}$=2g, where
$g=N\sqrt{8\pi}\hbar^{2}a_{s}/ml_{z}$ is the strength of the contact
interaction, $a_{s}$ is the 3D s-wave the scattering length ($a_{s}\ll
l_{z}$), $l_{z}=\sqrt{\hbar/m\omega_{z}}$ is the axial harmonic oscillator
length and $\omega_{z}$ is the trapping frequency in the tightly confined
direction. We only consider $N=N_{1}=N_{2}$ and equal masses. We rescale the
equations into trap units, so the energy scale is $\hbar\omega_{\rho}$ and the
length scale is $l_{\rho}=\sqrt{\hbar/m\omega_{\rho}}$ where $\omega_{\rho}$
is the trapping frequency in the x-y plane. We can loosely relate this to
experiments, for g=100 if we pick $N$=1000, $\omega_{z}$/$\omega_{\rho}$=100,
and $a_{s}$=100 $a_{0}$, then this example corresponds to radial trapping
frequencies, of $2\pi\times$38 Hz for K and $2\pi\times$11 Hz for Cs. It is
worth mentioning that the chemical potentials for each component are about
equal ($\mu=\mu_{1}\sim\mu_{2}$). More importantly, for the immiscible system,
$\mu$ is $8.4\hbar\omega_{\rho}$ and this gives a healing length of $\xi\sim
0.35l_{\rho}$ (for the miscible system $\mu\sim 7.4\hbar\omega_{\rho}$).
Further details of how we solve these equations (1,6) appear in Ref. CThfb .

Figure 1: (color online) The evolution of the ground state from miscible (a)
to immiscible (c). In (a) we show $g_{12}$ only slightly less than
$g_{12}^{c}$, and in (b) we show the quantum gas just after quantum phase
transition when the ground state breaks rotational symmetry and $g_{12}$ only
slightly greater than $g_{12}^{c}$. For (c) we have shown the standard example
of an immiscible gas with $g_{12}/g=2$. The BEC labeled 1 (2) is shown as blue
(red).

##  III results

In Fig. 1 we see the ground state changes character as we vary $g_{12}$. The
component with the smaller $g_{ii}$ is more dense in the middle of the trap.
We define $g_{12}^{c}$ as the value of $g_{12}$ when the ground state changes
character to a broken symmetry state which begins the immiscible regime. When
$g_{12}<g_{12}^{c}$, the ground state of the system has azimuthal symmetry and
the 2 BECs overlap, (a). However as $g_{12}$ is increased to $g_{12}^{c}$, the
ground state suddenly changes, and the azimuthal symmetry is broken, see (b).
As $g_{12}$ is further increased, the 2 BECs separate further and decrease
their overlap as it becomes energetically costly, (c). A similar evolution of
the ground state as a function of $g_{12}$ was reported in Ref. navarro .

It is challenging to find the ground state for all $g_{12}$. To do so, we use
the conjugate gradient method. We have found the best initial guess is one
with a slightly broken symmetry and poor overlap with the final group state.
We seed the noise so that the interface would be along the y axis. If the
overlap between the initial guess and the ground state is too large then it is
easy to get stuck in a local energy minimum. When the conjugate gradient
method fails to find the true ground state, the solutions to the Bogoliubov de
Gennes equations have complex eigenvalues. When we vary $g_{12}$, the previous
solution is thrown out. In this way we reliably find the excitation spectrum
of the 2 component BEC with only real eigenvalues.

Figure 2: (color online) Excitation spectrum for a transition from miscible to
immiscible. The critical $g_{12}^{c}$ is at 1.04g for trapped example with
$g$=100. Note the presence of strong avoided crossings and broken degeneracies
after rotational symmetry has been broken, $g_{12}>g_{12}^{c}$. For the
miscible system as $g$ is increased, the out-of-phase collective excitations
dramatically lower in energy. Some of the excitations shown in Fig. 3 (4) are
labeled on the left (right) of this figure.

In Fig. 2 we show Bogoliubov excitation energies ($\omega_{\alpha}$) as a
function of $g_{12}$. This shows the transition from miscible to immiscible at
$g_{12}^{c}/g\sim 1.04$, where a mode goes soft. Homogeneous theory predicts
this transition at $g_{12}^{c}=\sqrt{g_{11}g_{22}}$ pu ; eddy . The
discrepancy is explained by the trap and finite size of the gas ho . In fact,
if we were to increase g (keep $g_{ij}/g$ fixed); $g^{c}_{12}$ decreases
toward 1. For example if g=400 ($\mu\sim 16\hbar\omega_{\rho}$) then
$g^{c}_{12}\sim 1.01g$. A recent study explored how the trapping and the
kinetic energy contributions impact the criteria for immisciblity wen . Our
findings are consistent with their results.

To further understand Fig. 2, we start with $g_{12}<g_{12}^{c}$ where the
systems is miscible. The quasi-particles are readily classified based on their
azimuthal symmetry and the relative motion of the 2 condensates. As $g_{12}$
increases towards $g_{12}^{c}$, many modes decrease in energy. Then at
$g_{12}^{c}$ two modes go soft or their energies go to zero. For
$g_{12}>g_{12}^{c}$, many degeneracies are broken, and there are many avoided
crossing as $g_{12}$ is further increased. This is where the excitations mix
and change character. For the miscible side of spectrum, there are energy
crossings, but they are protected symmetry and do not couple. To further
understand this transition, we look at the mode which goes soft at
$g_{12}^{c}$.

Figure 3: (color online) We show the density perturbations as a function of x
and y. Theses perturbations are co-spatial, but for clarity they have been
separated. The density moves out of the dashed regions and into the solid
regions. The condensate densities are shown as faint contours. In (a) we show
the out-of-phase slosh mode where (i) moves up and (ii) moves down. This mode
has no center-of-mass motion. In (b) we show the in-phase slosh mode where (i)
and (ii) move together. This is a Kohn mode with center-of-mass motion. For
this example $g_{11}=g=g_{22}/1.01=2g_{12}$ with $g=100$. Energy is shown for
each quasi-particle in trap units.

In Fig. 3 we show density perturbations associated with 2 low-energy
excitations for the miscible system (far left of Fig. 2 with $g=100$). Density
perturbations from Bogoliubov de Gennes theory (T=0) are given by
$\phi_{i}(u_{i}^{\alpha}+v_{i}^{\alpha})$ for the mode $\alpha$. In Fig. 3 we
show both (a) the out-of-phase and (b) the in-phase slosh modes. The
condensates for this example are co-spatial and nearly identical. They look
similar to those in Fig. 1 (a). In this figure, we separated the two
components for clarity. The density moves from the regions define by the
dashed lines to the regimes defined by the solid lines. The color of the
perturbations matches the color for the associated condensate. We have drawn
arrows to illustrate the motion of the density perturbations. The contours are
shown for 0.25, 0.5 and 0.75 of the maximum value of the perturbation, and
condensate density is shown in the background. The energy of the mode is
reported on the figure in trap units.

In Fig. 3 (a) we show a slosh mode, but the motions of the 2 BECs are out-of-
phase with each other. The solid lines coincide with the dashed lines for the
other condensate’s motion. For example, the blue condensate, (i), sloshes from
$y<0$ to $y>0$ while the red condensate, (ii), sloshes from $y>0$ to $y<0$.
There is no center-of-mass motion in this case. In contrast, (b) shows a mode
with center-of-mass motion which is a Kohn mode of energy
1$\hbar\omega_{\rho}$. The motion of each condensate coincides with the other;
both the blue and red condensate slosh from $y>0$ to $y<0$ in phase with each
other. It is important to note that the out-of-phase slosh mode has the lowest
energy, and goes soft at the quantum phase transition.

For $g_{12}<g_{12}^{c}$, modes with $|m|>0$, where $m$ is the azimuthal
quantum number, have a degenerate twin. In our case with real quasi-particle
modes, degenerate modes are related by a rotation of $\pi/2m$. For example in
3 (a) and (b) there are degenerate twins are just rotated by $\pi/2$.

Referring back to the energy spectra in Fig. 2, we see that as $g_{12}$
increases towards $g_{12}^{c}$ the energy of the mode in Fig 3 (a) decreases
(while (b) stays at $1\hbar\omega_{\rho}$). More generally, all out-of-phase
modes significantly lower in energy as $g$ is increased to $g_{12}^{c}$. In
fact, the out-of-phase modes with $m=1$, $m=2$, $m=3$, and $m=0$ are all below
$1\hbar\omega_{\rho}$ at $g_{12}^{c}$. Then at $g_{12}^{c}$ the energy of the
out-of-phase slosh goes to zero and one mode stays zero for
$g_{12}>g_{12}^{c}$. The other mode (rotated by $\pi/2$) shoots up in energy
as $g_{12}$ is further increased beyond $g_{12}^{c}$.

The ground state spontaneously breaks rotational symmetry - which the
Hamiltonian has - and this leads to an extra zero energy Goldstone mode in the
excitations spectrum gold . There are already two Goldstone modes associated
with broken phase symmetry of each condensate, and they are:
$u_{i}^{(1)}=v_{i}^{(1)}=\phi_{i}$ and $u_{i}^{(2)}=-v_{i}^{(2)}=\phi_{i}$. If
one looks more closely at the third mode with $\omega=0$, one finds it is a
rotation of the interface ($u_{i}^{(3)}=v_{i}^{(3)}\neq\phi_{i}$). This extra
zero energy mode has already been observed in the 2 component BECs kim .
Goldstone modes have been discussed in more detail for spinor BECs ho ; ueda ,
and Ref. kan  found similar behavior for a Goldstone mode in an attractive
condensate with a Bogoliubov de Gennes treatment.

As we have said for the miscible system, the classification of the modes is
simple: we use azimuthal symmetry and relative motion of the two condensates.
But for the immiscible system, there is no rotational symmetry, so the
characterization of the excitations must be different. To study this in more
detail, we look at several quasi-particles.

Figure 4: (color online) The quasi-particle density perturbations for the
immiscible system, $g_{12}=2$. The x and y axes are in trap units. (a,b) are
slosh modes, (c,d) are quadrupole modes (e,f) are breathing modes, and (g,h)
are interface modes. The energy is reported in trap units and for this example
$g_{11}=g_{22}/1.01=g_{12}/2=100$.

In Fig. 4 we show the density perturbations associated with quasi-particle
excitations for the immiscible system ($g_{11}=g$, $g_{22}=1.01g$,
$g_{12}=2g$, and g=100). There are two types of quasi-particle modes: first,
bulk excitations which look like those from a standard condensate, and second,
interface excitations where the excitations are localized to the interface
between the 2 condensates. Since there is no azimuthal symmetry, to classify
the bulk modes we need to access how their motion is oriented relative to the
interface. In Fig. 4, to depict the motion of the density perturbations, we
show arrows in a few examples. The density moves from the dashed regions to
the solid regions. We also show the energy of the excitation in trap units.
The contours are shown for 0.25, 0.5 and 0.75 of the maximum value of the
perturbation and condensate density shown in the background.

The collective modes look like those in a standard BEC, however the two BECs
now act collectively to retain the excitation character. First, we look at the
slosh modes of the systems. They are shown in Fig. 4 (a,b). In (a) the slosh
mode with the center-of-mass displacement parallel to the interface (Kohn
mode) is shown and in (b) a slosh mode and center-of-mass displacement is
perpendicular to interface (also a Kohn mode) is shown. The arrows show that
in (a) both the blue and red condensate sloshes from $y>0$ to $y<0$. For
example (b) both the blue and red condensate sloshes from $x<0$ to $x>0$.

Next we show the quadrupole modes in Fig. 4 (c,d). (c) shows a quadrupole mode
with a nodal line along interface, and (d) shows a quadrupole mode where the
density increases at interface. These excitations are typical of a single
component BEC where the excitations are related by a $\pi/2m$ rotation. But in
this case, the 2 BECs collude to make the excitation. Additionally, these two
excitations are very similar in energy.

We show two breathing modes in Fig. 4 (e,f). They can be classified as in-
phase and out-of-phase motion of the 2 condensates. In (e) we show an in-phase
breathing mode, where both BECs inhale at once, or they both move into or out
of the center of the trap in unison. In (f) we show an out-of-phase breathing
mode, where one condensate inhales and the other exhales. The energies of
these modes are notably different: 2 and 2.73 $\hbar\omega_{\rho}$.

There is another class of excitation in the immiscible 2 component BEC:
interface excitations. Two examples are shown in Fig. 4 (g, h). These
excitations are localized along the interface, and in general they are out-of-
phase excitations, i.e. the density of one moves to where the other is
leaving. Note these are low energy excitations, in fact (g) is the lowest
energy excitations, for the system at 0.58 $\hbar\omega_{\rho}$ and (h) is
only slightly higher than the two Kohn modes at 1.08 $\hbar\omega_{\rho}$. If
$g$ is increased the mode in (h) will decrease below 1$\hbar\omega_{\rho}$. So
if the chemical potential is increased, then the interface modes become lower
in energy. To illustrate this, we look at how the excitation energies change
as a function of $g$ while keeping the ratio of the interactions fixed
($g_{12}/2=g_{11}\sim g_{22}$). This is shown in Fig 5 (a). For reference, on
the far right where $g$=600 and $\mu\sim 20\hbar\omega_{\rho}$, we have marked
the interface modes with red $\times$’s, there are 16 interface modes with
energy under 3.5$\hbar\omega_{\rho}$. In contrast, on the far left where
$g=100$, we have marked the interface modes with red $+$’s and there are only
7 modes under 3.5$\hbar\omega_{\rho}$. As one moves up in excitation energy,
each new excitation simply adds another bend to the interface. One more
important point of Fig. 5 (a), is that as $g$ increases the energies of
interface modes decrease.

Figure 5: (color online) The excitation spectrum as a function of g for the
immiscible example ($g_{12}/2=g_{11}=g_{22}/1.01$). The quasiparticles from
Fig. 4 are on the far left side of spectrum. The interface excitations are
marked by $\times$ or $+$ on either side of the figure. The energies of the
quasiparticle shown in Fig. 4 (g,h) are labeled. In (b) and (c) the density
perturbations for the interface excitations when $\mu\sim
20\hbar\omega_{\rho}$ or $g$=600, they are labeled on the right side of (a).
Their energy is reported in trap units.

Fig. 5 (b) and (c) show two examples of the higher energy interface modes.
First, Fig. 5 (b) is a mode with 6 bends in the interface. An interesting
point about (c) is that it is a hybrid mode, it also has some density
perturbations near the edge of the gas, away from the interface. The mode
shown in (c) is in a region where several modes are crossing and their
character is changing. If we further increase $g$, the interface mode lowers
in energy and loses it collective nature and looks more like mode in (b).
Related excitations have been studied in non-equilibrium simulations of 2
component BECs where Rayleigh-Taylor instabilities have been predicted rt1 ;
rt2 ; rt3 . In these studies, the value of $g_{11}$ is changed and this drives
one BEC into the other, the interface then becomes unstable and a Rayleigh-
Taylor instability forms.

##  IV conclusions

In conclusion, we have characterized the excitations of a 2 component BEC
within the Bogoliubov de Gennes framework. We found that as $g_{12}$ is
increased from a miscible regime to an immiscible regime, Fig. 2, generally,
all of the out-of-phase excitations lower in energy. The energy of the out-of-
phase slosh mode goes to zero, Fig. 3 (a). This mode becomes new Goldstone
modes when the rotational symmetry is spontaneously broken in the immiscible
system. We looked at the excitations of the immiscible systems when
$g=g_{12}/2=g_{11}=g_{22}/1.01$ in Fig. 4. We found that there are bulk modes
which look similar to the excitations of a single trapped BEC. There are also
excitations localized at the boundary between the condensates. One of these
interface modes is lowest energy mode when the BECs are immiscible, and there
are many other low energy interface modes, see the red $+$’s or x’s in Fig. 5
(a). Furthermore, if one goes to a more strongly interacting BEC regime (while
still immiscible), the interface modes lower in energy.

Future work will seek to understand the relationship between Bogoliubov
excitations across the miscible-immiscible transition and critical phenomena.
The effect of temperature on this system will be studied within the Hartree
Fock Bogoliubov framework, where Bogoliubov excitations are thermally
occupied. Additionally, we will look at how this collective excitation changes
with non-local dipolar interactions CThfb ; roton .

###### Acknowledgements.

The author gratefully acknowledges support through a LDRD ECR grant, LANL
which is operated by LANS, LLC for the NNSA of the U.S. DOE under Contract No.
DE-AC52-06NA25396. This research was supported in part by the National Science
Foundation under Grant No. NSF PHY11-25915. The author also gratefully
acknowledges conversations with E. Timmermans, L. A. Collins, and R. M.
Wilson.

## References

  * (1) M. Greiner et al., Nature 415, 39 (2002).
  * (2) W. S. Bakr et al. Nature 462, 74 (2009).
  * (3) S. Trotzky et al., Nat. Phys. 6, 998 (2010).
  * (4) X. Zhang et al., Science. 335, 1070 (2012).
  * (5) S. B. Papp, J. M. Pino, and C. E. Wieman, Phys. Rev. Lett. 101, 040402 (2008).
  * (6) H. Pu and N. Bigelow, Phys. Rev. Lett. 80, 1130 (1998); ibid. 80, 1134 (1998).
  * (7) E. Timmermans, Phys. Rev. Lett. 81, 5718 (1998).
  * (8) M. R. Matthews et al., Phys. Rev. Lett. 83, 2498 (1999).
  * (9) K. M. Mertes et al., Phys. Rev. Lett. 99, 190402 (2007).
  * (10) R. P. Anderson, C. Ticknor, A. I. Sidorov, and B. V. Hall Phys. Rev. A 80, 023603 (2009).
  * (11) E. Nicklas et al., Phys. Rev. Lett. 107, 193001 (2011).
  * (12) D. Gordon and C. M. Savage, Phys. Rev. A 58 1440 (1998).
  * (13) J. G. Kim and E. K Lee, Phys. Rev. E 65, 066201 (2002).
  * (14) A. L. Fetter and J. D. Waleck, Quantum Theory of Many-Particle Systems, (Dover, New York 2003).
  * (15) C.-L. Hung, X. Zhang, N. Gemelke, and C. Chin, Nature 470, 236 (2011).
  * (16) C. Ticknor, Phys. Rev. A 85, 033629 (2012); Phys. Rev. A 86, 053602 (2012).
  * (17) R. Navarro, R. Carretero-González, and P. G. Kevrekidis, Phys. Rev. A 80, 023613 (2009).
  * (18) L. Wen et al. Phys. Rev. A 85, 043602 (2012).
  * (19) For a review see: T. Brauner, Symmetry 2, 609 (2010).
  * (20) T.-L. Ho and V. B. Shenoy, Phys. Rev. Lett. 77, 3276 (1996).
  * (21) S. Uchino, M. Kobayashi, and M. Udea, Phys. Rev. A 81, 063623 (2010); S. Uchino, M. Kobayashi, M. Nitta, and M. Ueda Phys. Rev. Lett. 105, 230406 (2010).
  * (22) R. Kanamoto, H. Saito, and M. Ueda, Phys. Rev. Lett. 94, 090404 (2005).
  * (23) K. Sasaki, N. Suzuki, D. Akamatsu, and H. Saito, Phys. Rev. A 80, 063611 (2009); N. Suzuki, H. Takeuchi, K. Kasamatsu, M. Tsubota, and H. Saito, Phys. Rev. A 82, 063604 (2010); H. Takeuchi, N. Suzuki, K. Kasamatsu, H. Saito, and M. Tsubota, Phys. Rev. B 81, 094517 (2010); T. Kadokura, T. Aioi, K. Sasaki, T. Kishimoto, and H. Saito, Phys. Rev. A 85, 013602 (2012).
  * (24) S. Gautam and D. Angom, Phys. Rev. A 81, 053616 (2010).
  * (25) A. Bezett, V. Bychkov, E. Lundh, D. Kobyakov, and M. Marklund, Phys. Rev. A 82, 043608 (2010); D. Kobyakov, V. Bychkov, E. Lundh, A. Bezett, and M. Marklund, Phys. Rev. A 86, 023614 (2012).
  * (26) R. M. Wilson, C. Ticknor, J. L. Bohn, and Eddy Timmermans, Phys. Rev. A 86, 033606 (2012).