# Maximum Boundary Independent Broadcasts in
Graphs and Trees

J. I. Hoepner, G. MacGillivray, and C. M. Mynhardt
Department of Mathematics and Statistics
University of Victoria
PO BOX 1700 STN CSC
Victoria, B.C.
Canada V8W 2Y2
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
(April 16, 2023)

###### Abstract

A broadcast on a connected graph $G$ with vertex set $V(G)$ is a function
$f:V(G)\rightarrow\\{0,1,...,\text{diam}(G)\\}$ such that $f(v)\leq e(v)$ (the
eccentricity of $v$) for all $v\in V$. A vertex $v$ is said to be broadcasting
if $f(v)>0$, with the set of all such vertices denoted $V_{f}^{+}$. A vertex
$u$ hears $f$ from $v\in V_{f}^{+}$ if $d_{G}(u,v)\leq f(v)$. The broadcast
$f$ is hearing independent if no broadcasting vertex hears another. If, in
addition, any vertex $u$ that hears $f$ from multiple broadcasting vertices
satisfies $f(v)\leq d_{G}(u,v)$ for all $v\in V_{f}^{+}$, the broadcast is
said to be boundary independent.

The cost of $f$ is $\sigma(f)=\sum_{v\in V(G)}f(v)$. The maximum cost of
boundary independent broadcasts is denoted $\alpha_{bn}(G)$. We show
$\alpha_{bn}(G)$ can be bounded in terms of the independence number
$\alpha(G)$, and prove that the maximum bn-independent broadcast problem is
NP-hard by a reduction from the independent set problem to an instance of the
maximum bn-independent broadcast problem.

We investigate bounds on $\alpha_{bn}(T)$ when $T$ is a tree in terms of its
order and the number of vertices of degree at least 3, known as the branch
vertices of $T$. We determine a sharp upper bound on $\alpha_{bn}(T)$ when $T$
is a caterpillar, giving $\alpha_{bn}(T)$ exactly for certain families of
caterpillars.

Keywords: broadcast domination; broadcast independence; boundary independence

AMS Subject Classification Number 2010: 05C69

##  1 Introduction

There are several methods by which the concept of independent sets may be
generalized to broadcast independence. If we require that no broadcasting
vertex hears another, we obtain the definition of cost independent broadcasts
introduced by Erwin in [6], which we refer to as hearing independent,
abbreviated h-independent. The definition of boundary independent (or bn-
independent) broadcasts, in which no broadcasts overlap on edges, was
introduced by Neilson [16] and Mynhardt and Neilson [13] as an alternative to
hearing independence.

The maximum cost of a boundary independent broadcast on a given graph $G$ is
referred to as its boundary independence number, denoted $\alpha_{bn}(G)$. For
a given integer $k\geq 0$, the problem of determining whether
$\alpha_{bn}(G)\geq k$ is called the maximum bn-independent broadcast problem.
The hearing independence number $\alpha_{h}(G)$ and the maximum h-independent
broadcast problem are defined similarly.

As any boundary independent broadcast is hearing independent, it follows from
the definitions that $\alpha_{bn}(G)\leq\alpha_{h}(G)$ for all graphs $G$. In
[13], Mynhardt and Neilson showed that $\alpha_{h}(G)/\alpha_{bn}(G)<2$, and
that this bound is asymptotically best possible. They posed the problem of
investigating the ratio $\alpha_{bn}(G)/\alpha(G)$ in [15].

######  Problem 1.1.

Is it true that $\alpha_{bn}(G)<2\alpha(G)$ for any graph $G$?

It was shown in [13] that $\alpha_{bn}(G)\leq n-1$ for all graphs $G$ of order
$n$, with equality if and only if $G$ is a path or a generalized spider, a
tree with exactly one vertex of degree greater than 2. It is easily observed
that ${\alpha(G)\leq n-\delta(G)}$, where $\delta(G)$ denotes the minimum
degree among the vertices of $G$. In [14], Mynhardt and Neilson asked whether
a similar inequality existed for the maximum boundary independence number.

######  Problem 1.2.

Show that $\alpha_{bn}(G)\leq n-\delta(G)$ for any graph $G$ of order $n$.

For any tree $T$, the bound in Problem 1.2 follows immediately from the bound
$\alpha_{bn}(T)\leq n-1$ and the fact that $\delta(T)=1$.

Broadcast definitions and known results are presented in Section 2. In Section
3, we show that $\alpha_{bn}(G)<2\alpha(G)$ for all $G$, solving Problem 1.1.
We further resolve Problem 1.2 by showing that $\alpha_{bn}(G)\leq
n-\delta(G)$ for any graph $G$.

In Section 4, by considering a transformation from independent sets to
boundary independent broadcasts on graphs, we observe that determining whether
$\alpha_{bn}(G)\geq k$ for a given integer $k$ is NP-Complete. In Section 5,
we investigate the maximum boundary independence number of trees and determine
$\alpha_{bn}(G)$ exactly for families of caterpillars. Open problems and
directions for further research are discussed in Section 6.

##  2 Definitions and Background

Erwin [6] defined a broadcast on a nontrivial connected graph $G$ as a
function $f:V(G)\rightarrow\\{0,1,...,\text{diam}(G)\\}$ such that $f(v)$ is
at most the eccentricity $e(v)$ for all vertices $v$. We say a vertex $v$ is
broadcasting if $f(v)\geq 1$, and that $f(v)$ is the strength of $f$ from $v$.
The cost or weight of $f$ is $\sigma(f)=\sum_{v\in V(G)}f(v)$.

Given a broadcast $f$ on $G$ and a broadcasting vertex $v$, a vertex $u$ hears
$f$ from $v$ if $d_{G}(u,v)\leq f(v)$. We define the $f$-neighbourhood of $v$,
denoted by $N_{f}(v)$, as the set of all vertices which hear $f$ from $v$
(including $v$ itself).

The $f$-private neighbourhood of $v$, denoted by $PN_{f}(v)$, consists of
those vertices that hear $f$ only from $v$. The $f$-boundary of $v$ is
$B_{f}(v)=\\{u\in N_{f}(v)\,|\,d(u,v)=f(v)\\}$. The $f$-private boundary
$PB_{f}(v)$ is defined analogously. In particular, $PB_{f}(v)=PN_{f}(v)\cap
B_{f}(v)$. If $u\in N_{f}(v)\backslash B_{f}(v)$, $v$ is said to overdominate
$u$ by $k$, where $k=f(v)-d_{G}(u,v)$. A vertex which does not broadcast or
hear $f$ from any broadcasting vertex is undominated.

Throughout this paper, we partition the set of broadcasting vertices
$V_{f}^{+}$ into ${V_{f}^{1}=\\{v\in V(G)\,|\,f(v)=1\\}}$ and
$V_{f}^{++}=\\{v\in V(G)\,|\,f(v)>1\\}$. We denote the set of undominated
vertices by $U_{f}$. A broadcast $f$ is dominating if $U_{f}=\emptyset$. The
broadcast domination number, $\gamma_{b}(G)$, is the minimum weight of such a
broadcast. An overview of broadcast domination in graphs is given by Henning,
MacGillivray, and Yang in [8].

We say an edge $e=uv$ hears $f$ or is covered by $w\in V_{f}^{+}$ if $u,v\in
N_{f}(w)$ and at least one endpoint does not lie on the $f$-boundary of $w$.
If no such vertex $w$ exists, then $e$ is $uncovered$. The set of uncovered
edges is denoted $U_{f}^{E}$.

An independent set on a graph $G$ is a set of pairwise nonadjacent vertices.
The minimum cardinality of a maximal independent set, called the independent
domination number of $G$, is denoted $i(G)$. A broadcast $f$ is hearing
independent if $x\notin N_{f}(v)$ for any $x,v\in V_{f}^{+}$. It is boundary
independent if $N_{f}(v)\backslash B_{f}(v)\subseteq PN_{f}(v)$ for all $v\in
V_{f}^{+}$.

$v_{1}$$u$$v_{2}$$w_{1}$$w_{2}$ Figure 1: A boundary independent broadcast $f$
on a tree. Vertices $v_{1}$ and $v_{2}$ broadcast at strengths 1 and 2,
respectively. The vertex $v_{2}$ overdominates $u$ by 1, whereas $w_{1}$ and
$w_{2}$ are undominated.

Although efficient broadcast domination was shown to be solvable in polynomial
time for every graph in [7], the complexity of hearing independence was
unknown even for trees until an efficient algorithm was found by Bessy and
Rautenbach in [1].

######  Theorem 2.1.

[1] For any tree $T$ of order $n$, $\alpha_{h}(T)$ can be determined in
$O(n^{9})$ time.

Using a method similar to the proof technique employed by Bessy and Rautenbach
in [1], an $O(n^{9})$ time algorithm to determine $\alpha_{bn}(T)$ for trees
was described in [9].

######  Theorem 2.2.

[9] Given a tree $T$ with $n\geq 3$ vertices, its boundary independent
broadcast number $\alpha_{bn}(T)$ can be determined in $O(n^{9})$ time.

Hearing independence was further studied by Bessy and Rautenbach [2, 3] and by
Dunbar et al. [5]. The more recent study of boundary independent broadcasts
was continued by Mynhardt and Neilson in [12, 14, 15] and by Marchessalt and
Mynhardt in [11]. For terminology and general concepts in graphs theory not
defined in this paper, see Chartrand, Lesniak, and Zhang [4].

##  3 Upper and Lower Bounds on $\alpha_{bn}(G)$

Our focus in this section is to establish bounds on $\alpha_{bn}(G)$ for
general graphs, and determine parameters comparable to $\alpha_{bn}$ to place
the parameter within a chain of inequalities.

In [3], Bessy and Rautenbach found that $\alpha_{h}(G)<4\alpha(G)$, adapting a
proof technique used by Neilson [16] to show that
$\alpha_{h}(G)<2\alpha_{bn}(G)$. Mynhardt and Neilson further studied the
ratio $\frac{\alpha_{bn}(G)}{\alpha(G)}$ in [15] and asked whether it can be
shown that $\frac{\alpha_{bn}(G)}{\alpha(G)}<2$ for all graphs $G$.

######  Theorem 3.1.

For any graph $G$, $\alpha_{bn}(G)<2\alpha(G)$.

###### Proof.

Let $f$ be an $\alpha_{bn}$-broadcast on $G$. If $V_{f}^{+}=V_{f}^{1}$,
$V_{f}^{+}$ is an independent set, so assume there exists $v$ such that
$f(v)\geq 2$. Let $u\in B_{f}(v)$ and consider a subgraph $T_{u}$ consisting
of $u$ and unique geodesics from $u$ to each vertex in $S=\\{x\in
V_{f}^{+}:u\in B_{f}(x)\\}$, the set of all broadcasting vertices heard by $u$
(if $u\in PB_{f}(v)$, $S=\\{v\\}$). Since no edge can be covered by two
different broadcasts, $T_{u}$ is an induced path or spider, hence
$|V(T_{u})|=1+\sum\limits_{w\in S}f(w)$.

Consider a proper two-colouring of $T_{u}$ and define a new boundary
independent broadcast by deleting all broadcasts from the leaves of $T_{u}$
and adding strength-one broadcasts from each vertex in the color set of
highest cardinality (if they have equal cardinality, select one arbitrarily).

Since broadcasts overlap only on boundaries, the broadcasting vertices of the
resulting bn-independent broadcast form an independent set of cardinality at
least $|V(T_{u})|/2$. Repeating the process until no vertices broadcasting at
strength greater than 1 remain yields an independent set on $G$. Since
$|V(T_{u})|<\sum\limits_{w\in S}f(w)$, it follows that
${\alpha_{bn}(G)/2<\alpha(G)}$. ∎

As $\alpha_{bn}(G)\leq\alpha_{h}(G)$ for any graph $G$, Bessy and Rautenbach’s
bound now follows easily from Neilson’s result and Theorem 3.1.

######  Corollary 3.2.

For any graph $G$, $\alpha_{h}(G)<4\alpha(G)$.

Let $\delta(G)$ denote the minimum degree of $G$. It is easy to see that
${\alpha(G)\leq n-\delta(G)}$, as the inclusion of any vertex to an
independent set excludes its neighbours. We determine the analogous result for
maximum boundary independence, thereby solving an open problem posed in [14].

######  Theorem 3.3.

For any graph $G$ of order $n$, $\alpha_{bn}(G)\leq n-\delta(G)$.

###### Proof.

The result is clear if $|V(G)|=1$, so assume the theorem holds for all graphs
$G$ such that $|V(G)|\leq n-1$ and consider a graph $G$ of order $n$. Let $f$
be an $\alpha_{bn}$-broadcast on $G$ with $|V_{f}^{1}|$ maximum. For any $v\in
V_{f}^{++}$, $PB_{f}(v)=\emptyset$, otherwise a new boundary independent
broadcast of equal weight could be constructed by reducing $f(v)$ by 1, and
broadcasting at strength 1 from a vertex in the $f$-private boundary of $v$.

For some $v\in V_{f}^{+}$, consider the graph $G^{\prime}=G-PN_{f}(v)$ of
order $n^{\prime}$, and let $f_{G^{\prime}}$ be $f$ restricted to
$G^{\prime}$. By induction,
$\sigma(f_{G^{\prime}})\leq\alpha_{bn}(G^{\prime})\leq
n^{\prime}-\delta(G^{\prime})$, hence
$\alpha_{bn}(G)=\sigma(f_{G^{\prime}})+f(v)\leq
f(v)+n^{\prime}-\delta(G^{\prime})$.

Consider a vertex $u$ of minimum degree in $G^{\prime}$. First, suppose $u\in
B_{f}(v)$ and let $k=|PN_{f}(v)\cap N_{G}(u)|$. Let $P$ be a $u-v$ geodesic in
$G$. Since $P$ has length $f(v)$ and $u$ is adjacent to $k-1$ vertices in
$PN_{f}(v)-V(P$), we have that $k-1+f(v)\leq|PN_{f}(v)|$. In particular, if
$k+f(v)=|PN_{f}(v)|+1$, then either $PN_{f}(v)$ consists of a path on $f(v)$
vertices (and thus $d(v)=1$), or $f(v)=2$ and $d_{G}(v)=k$. In either case,
since $u$ hears more than one broadcasting vertex under $f$,
$\delta(G)<d_{G}(u)$. Thus,

$\alpha_{bn}(G)\leq f(v)+n^{\prime}-\delta(G^{\prime})\leq
f(v)+n^{\prime}-d_{G}(u)+k\leq n+1-d_{G}(u)\leq n-\delta(G)$.

Otherwise, if $k+f(v)\leq|PN_{f}(v)|$,

$\alpha_{bn}(G)\leq f(v)+n^{\prime}-d_{G}(u)+k\leq n-\delta(G).$

Finally, if $u\notin B_{f}(v)$, then $d_{G}(u)=d_{G^{\prime}}(u)$, hence
$\delta(G)\leq\delta(G^{\prime})$ and $\alpha_{bn}(G)\leq
n-\delta(G^{\prime})\leq n-\delta(G)$ as desired. ∎

##  4 The Hardness of Determining $\alpha_{bn}(G)$

Given a graph $G$ and a positive integer $k$, we may verify that a broadcast
$f$ on $G$ of cost at least $k$ is boundary independent in polynomial time by
checking that $f(u)+f(v)\leq d_{G}(u,v)$ for every pair of distinct
broadcasting vertices $u,v\in V_{f}^{+}$. It follows that the maximum bn-
independent broadcast problem is NP. We proceed to show that the problem is
NP-complete by a transformation from the independent set problem on $G$, which
was shown to be NP-complete by Karp [10], to the maximum bn-independent
broadcast problem on a corresponding graph $C_{G}$.

The corona $G\bigodot H$ of graphs $G$ and $H$ is constructed from $G$ and
$n=|V(G)|$ copies of $H$ by joining the $i$th vertex in $G$ by edges to every
vertex in the $i$th copy of $H$. Let $C_{G}=G\bigodot K_{1}$.

Figure 2: The construction of the corona $K_{4}\bigodot K_{1}$.

######  Proposition 4.1.

Let $G$ be a connected graph on $n\geq 2$ vertices and let $C_{G}=G\bigodot
K_{1}$. Then $\alpha_{bn}(C_{G})=n+\alpha(G)$.

###### Proof.

Let $l_{1},...,l_{n}$ be a labelling of the leaves of $C_{G}$, and let
$v_{1},...,v_{n}$ be a labelling of the remaining vertices such that $l_{i}$
is adjacent to $v_{i}$ for all $i$. Let $S\subseteq\\{v_{1},...,v_{n}\\}$ be a
maximum independent set on the subgraph of $C_{G}$ corresponding to $G$.

Define a broadcast $f$ on $C_{G}$ by

$f(u)=\begin{cases}2&\text{ if }u=l_{i}\text{ for some {i} and }v_{i}\in S\\\
1&\text{ if }u=l_{i}\text{ for some {i} and }v_{i}\notin S\\\ 0&\text{
otherwise.}\end{cases}$

Then $\sum_{u}f(u)=n+\alpha(G)$. Since only leaves broadcast, and since
$d_{C_{G}}(l_{i},l_{j})\leq f(l_{i})+f(l_{j})$ for any pair of leaves
$l_{i}\neq l_{j}$, $f$ is boundary independent. Therefore
$\alpha_{bn}(C_{G})\geq n+\alpha(G)$.

To show that $\alpha_{bn}(C_{G})\leq n+\alpha(G)$, let $f$ be a
$\alpha_{bn}$-broadcast on $C_{G}$. If a vertex $v_{i}$ is broadcasting, the
bn-independent broadcast $f^{\prime}$ on $C_{G}$ defined by
$f^{\prime}(l_{i})=f(v_{i})+1$, $f^{\prime}(v_{i})=0$, and
$f^{\prime}(u)=f(u)$ otherwise has greater cost than $f$, a contradiction. It
follows that $V_{f}^{+}\subseteq\\{l_{1},...,l_{n}\\}$.

Suppose some leaf $l_{i}$ broadcasts at strength $k\geq 3$ under $f$. Since
$f(l_{i})\leq e(l_{i})$, there exist at least $k-2$ leaves which hear $l_{i}$
from a distance greater than $2$. Define a new maximum bn-independent
broadcast $f^{\prime}$ by

$f^{\prime}(l_{i})=\begin{cases}f(l_{i})&\text{ if }f(l_{i})\in\\{1,2\\}\\\
2&\text{ if }f(l_{i})=k>2\\\ 1&\text{ if }f(l_{i})=0\end{cases}$

and consider $R\subseteq\\{v_{1},...,v_{n}\\}$, where $v_{i}\in R$ if and only
if $f^{\prime}(l_{i})=2$. Two vertices adjacent to leaves broadcasting at
strength 2 cannot be adjacent, hence $R$ is an independent set on the subgraph
of $C_{G}$ corresponding to $G$. Since every leaf broadcasts at strength 1 or
2 under $f^{\prime}$, we have that $|R|=\alpha_{bn}(C_{G})-n$. Therefore
$\alpha_{bn}(C_{G})\leq n+|R|\leq n+\alpha(G)$. ∎

######  Corollary 4.2.

Let $G$ be a graph and $k$ a positive integer. The problem of deciding whether
$\alpha_{bn}(G)\geq k$ is NP-complete.

###### Proof.

We have already observed that the maximum bn-independent broadcast problem is
NP. As the transformation described in Proposition 4.1 can be carried out in
polynomial time, the problem is NP-complete. ∎

It follows that for any graph class $\mathcal{C}$ for which $G\in\mathcal{C}$
implies $C_{G}\in\mathcal{C}$, if the independent set problem is known to be
NP-complete for all graphs in $\mathcal{C}$, then so is the maximum bn-
independent set problem.

Graph classes for which the independent set problem is known to be NP-complete
are listed in [17]. In particular, the maximum bn-independent set problem is
NP-complete for planar and toroidal graphs, graphs with maximum degree
$\Delta\in\\{3,4,5,6\\}$, triangle-free and $C_{n}$-free graphs for
$n\in\\{4,5,6\\}$, $K_{n}$-free graphs for $n\in\\{4,6,7\\}$, and house-free
graphs.

##  5 Trees

Let $T$ be a tree. Its branch-leaf representation $\mathcal{BL}(T)$, also
known as the homeomorphic reduction of $T$, is obtained by successively
removing a vertex of degree 2 and adding an edge between its two neighbours
until no such vertices remain. Deleting all leaves yields the branch
representation of $T$, denoted $\mathcal{B}(T)$.

$T$$\mathcal{BL}(T)$$\mathcal{B}(T)$$v$$v$$v$ Figure 3: The branch-leaf
representation and branch representation of a tree $T$.

We partition the vertices of $T$ into sets $B_{T},L_{T},$ and $\tau_{T}$,
where $B_{T}$ denotes the set of branch vertices of $T$, $L_{T}$ the set of
leaves, and $\tau_{T}$ the set of vertices of degree 2, called the trunks of
$T$. We further define a subset $R_{T}$ of $B_{T}$ consisting of branch
vertices adjacent to at most one leaf in $\mathcal{BL}(T)$. In other words, a
branch vertex $b$ belongs to $R_{T}$ if there exists at most one leaf $l\in
L_{T}$ such that for every $b^{\prime}\in B_{T}-b$, the unique $b^{\prime}-l$
path contains $b$. In Figure 3 above, $|B_{T}|=3$ and $R_{T}=\\{v\\}$.

Maximum boundary independent broadcasts on trees were studied by Neilson in
[16], who determined that $\alpha_{bn}(T)\leq n-|B_{T}|+|R_{T}|$ for any tree
$T$ with $B_{T}\neq\emptyset$. Neilson asked whether this upper bound could be
improved to $\alpha_{bn}(T)\leq n-|B_{T}|+\alpha(T[R_{T}])$, where $T[R_{T}]$
is the subgraph of $T$ induced by $R_{T}$.

A caterpillar is a tree with a diametrical path $D$ such that every vertex
lies on $D$ or is adjacent to a vertex on $D$. We proceed to show that
$\alpha_{bn}(C)\leq n-|B_{C}|+\alpha(C[R_{C}])$ for all caterpillars $C$, and
determine $\alpha_{bn}(C)$ exactly for certain subclasses of caterpillars.
Observe that if $C$ is a caterpillar, $C[R_{C}]$ is a path or a forest of
paths.

The following lemma will be useful throughout this section.

######  Lemma 5.1.

[16] If $f$ is an $\alpha_{bn}$-broadcast on a tree $T$, no leaf of $T$ hears
a broadcast from any non-leaf vertex.

In particular, if $f$ is a maximum boundary independent broadcast on a
caterpillar, only leaves and trunks broadcast.

Given a caterpillar $C$, its spine is an (arbitrarily chosen) diametrical
path. Label the leaves of $C$ as $l_{1},...,l_{m}$ such that $l_{1}$ and
$l_{m}$ are the endpoints the spine and for all $i\leq j$,
$d_{C}(l_{1},l_{i})\leq d_{C}(l_{1},l_{j})$. Call $l_{2},...,l_{m-1}$ the
inner leaves of $C$.

######  Lemma 5.2.

Let $f$ be an $\alpha_{bn}$-broadcast on a caterpillar $C$ such that
$|V_{f}^{1}|$ is maximized. Then $l_{1},l_{m}\in V_{f}^{+}$.

###### Proof.

Suppose not. If $l_{1}\in N_{f}(v)$ for some $v\in V_{f}^{+}$, define a new
broadcast $f^{\prime}$ by $f^{\prime}(v)=f(v-1)$, $f^{\prime}(l_{1})=1$, and
$f^{\prime}(w)=f(w)$ for all $w\neq v,l_{1}$. If some vertex $u$ does not hear
$f^{\prime}$, broadcasting at strength 1 from $u$ produces a boundary
independent broadcast of greater cost than $f$, a contradiction. Therefore
$f^{\prime}$ is an $\alpha_{bn}$-broadcast on $C$. By Lemma 5.1, $v$ is a
leaf, hence $d_{C}(l_{1},v)\geq 2$ and so $v\notin V_{f}^{1}$. But then
$|V_{f^{\prime}}^{1}|>|V_{f}^{1}|$, a contradiction.

It follows that $l_{1}\in V_{f}^{+}$. Similarly, $l_{m}\in V_{f}^{+}$. ∎

######  Theorem 5.3.

If $C$ is a caterpillar, then $\alpha_{bn}(C)\leq n-|B_{C}|+\alpha(C[R_{C}])$.

###### Proof.

Let $f$ be an $\alpha_{bn}$-broadcast on $C$ such that $|V_{f}^{1}|$ is
maximized, and let $l_{i}$ be an inner leaf of $C$ adjacent to a branch vertex
$b_{i}$. If $f(l_{i})\geq 3$, then since $l_{1}$ and $l_{m}$ are broadcasting,
$l_{i}$ covers at least $2(f(l_{i})-1)$ edges on the spine.

If $f(l_{i})$ is odd, let $f^{\prime}$ be a broadcast defined by
$f^{\prime}(l_{i})=1$, $f^{\prime}(v)=1$ for all $v$ at an even distance from
$l_{i}$, and $f^{\prime}(v)=f(v)$ for all $v\notin N_{f}[l_{i}]$.

If $f(l_{i})$ is even, define $f^{\prime}$ by $f^{\prime}(l_{i})=2$,
$f^{\prime}(v)=1$ for all $v$ at odd distance at least 3 from $l_{i}$, and
$f^{\prime}(v)=f(v)$ for all $v\notin N_{f}[l_{i}]$.

Figure 4 illustrates the construction of $f^{\prime}$.

$4$$3$$1$$1$$1$$1$$1$$2$$f$$f$$f^{\prime}$$f^{\prime}$ Figure 4: The odd and
even cases.

It follows that $f^{\prime}$ is a boundary independent broadcast on $C$ such
that $\sigma(f^{\prime})=\sigma(f)$ and $|V_{f^{\prime}}^{1}|>|V_{f}^{1}|$, a
contradiction. Thus, $f(l_{i})\leq 2$ for each inner leaf $l_{i}$. Since $f$
is boundary independent, the set of branch vertices adjacent to leaves that
broadcast at strength 2 must form an independent set.

By Lemma 5.1, no branch vertices broadcast under $f$. Let $C^{\prime}$ denote
the subgraph of $C$ induced by removing all inner leaves and branch vertices,
and let $f_{C^{\prime}}$ denote the restriction of $f$ to $C^{\prime}$. Since
$f_{C^{\prime}}$ is boundary independent,
$\sigma(f_{C^{\prime}})\leq\alpha_{bn}(C^{\prime})\leq|V(C^{\prime})|-\delta(C^{\prime})=|V(C^{\prime})|-1$.
Taking the sum over all broadcasting vertices, we find that
${\alpha_{bn}(C)\leq(|V(C^{\prime})|-1)+(L_{C}-2)+\alpha(C[R_{C}])\leq
n-|B_{C}|+\alpha(C[R_{C}])}$. ∎

######  Corollary 5.4.

Let $C$ be a caterpillar with $|V(C)|\geq 3$.

  * i.

If $\tau_{C}=\emptyset$, then $\alpha_{bn}(C)=|L_{C}|+\alpha(C[R_{C}])$.

  * ii.

If $C$ has no two adjacent trunks and no vertices of degree 3, then
$\alpha_{bn}(C)=|L_{C}|+|\tau_{C}|$.

###### Proof.

Suppose $\tau_{C}=\emptyset$, so that every vertex of $C$ is either a branch
vertex or a leaf. By Theorem 5.3, $\alpha_{bn}(C)\leq
n-|B_{C}|+\alpha(C[R_{C}])=|L_{C}|+\alpha(C[R_{C}])$. Observe that $C[R_{C}]$
is a forest of paths, and let $S$ be a maximum independent set of $C[R_{C}]$.
Define a broadcast $f$ on $C$ by

$f(v)=\left\\{\begin{tabular}[c]{rl}2&if $v\in L_{T}$ and $v$ is adjacent to a
vertex in $S$\\\ 1&if $v\in L_{T}$ and $v$ is not adjacent to a vertex in
$S$\\\ 0&if $v\notin L_{T}$.\end{tabular}\right.$

As only leaves broadcast, two broadcasts from $l_{i}$ and $l_{j}$ may overlap
only if one or both vertices broadcast at strength 2. Suppose they do. Without
loss of generality, assume $f(l_{i})=2$. Let $b_{i}$ be the neighbour of
$l_{i}$ in $S$. But then since $b_{i}$ has only one leaf, $f(l_{j})=2$ and
$b_{j}\in S$, hence $d(l_{i},l_{j})\geq 4$. It follows that $f$ is a boundary
independent broadcast on $C$. Thus,
$\sigma(f)=|L_{C}|+\alpha(C[R_{C}])\leq\alpha_{bn}(C)$.

Suppose instead that $C$ has no two adjacent trunks and no vertices of degree
3. Since $R_{C}=\emptyset$, $\alpha_{bn}(C)\leq
n-|B_{C}|+\alpha(C[R_{C}])=|L_{C}|+\tau_{C}$ by Theorem 5.3. Define a
broadcast $f$ on $C$ by

$f(v)=\left\\{\begin{tabular}[c]{rl}1&if $v\in L_{C}$ or $v\in\tau_{C}$\\\
0&otherwise.\end{tabular}\right.$

By definition, no two broadcasting vertices are adjacent. It follows that $f$
is a boundary independent broadcast, hence
$\sigma(f)=|L_{C}|+|\tau_{C}|\leq\alpha_{bn}(C)$. ∎

##  6 Open problems

In [16], Neilson determined that $\alpha_{bn}(T)\leq n-|B_{T}|+|R_{T}|$ for
all trees with at least one branch vertex, which we improved to
$\alpha_{bn}(C)\leq n-|B_{C}|+\alpha(C[R_{C}])$ for caterpillars. It is
unknown whether this result can be extended to all trees.

######  Question 6.1.

For any tree $T$ of order $n$ and at least one branch vertex, is it true that
$\alpha_{bn}(T)\leq n-|B_{T}|+\alpha(C[R_{T}])$?

In particular, we found that equality holds for caterpillars $C$ with no
trunks, as well as caterpillars with no branches of degree 3 and no two
adjacent trunks, when $|V(C)|\geq 3$.

######  Problem 6.2.

Characterize trees $T$ such that $\alpha_{bn}(T)=n-|B_{T}|+\alpha(C[R_{T}])$.

######  Problem 6.3.

Fine a closed formula to determine $\alpha_{bn}(C)$ exactly for caterpillars
or other classes of trees.

## References

  * [1] S. Bessy and D. Rautenbach. Algorithmic aspects of broadcast independence. Disc. Appl. Math. 314 (2022), 142–149.
  * [2] S. Bessy and D. Rautenbach. Girth, minimum degree, independence, and broadcast independence. Commun. Comb. Optim. 4 (2019), 131–139.
  * [3] S. Bessy and D. Rautenbach. Relating broadcast independence and independence. Discrete Math. 342 (2019), article 111589.
  * [4] G. Chartrand, L. Lesniak, and P. Zhang. “Graphs and digraphs”, 6th ed., CRC Press, New York, 2016.
  * [5] J. E. Dunbar, D. J. Erwin, T. W. Haynes, S. M. Hedetniemi and S. T. Hedetniemi. Broadcasts in graphs. Discrete Applied Math, 154 (2006), 59–75.
  * [6] D. Erwin. Cost Domination in Graphs. Doctoral dissertation, Western Michigan University, Kalamazoo, MI, USA, 2001. https://scholarworks.wmich.edu/cgi/viewcontent.cgi?article=2367&context=dissertations&httpsredir=1&referer=.
  * [7] P. Heggernes and D. Lokshtanov. Optimal broadcast domination in polynomial time. Discrete Mathematics, 36 (2006), 3267-3280.
  * [8] M. A. Henning, G. MacGillivray, and F. Yang. Broadcast domination in graphs. In T. W. Haynes, S. T. Hedetniemi, and M. A. Henning, editors, Structures of Domination in Graphs, pages 15–46. Springer International Publishing, Cham, Switzerland, 2021.
  * [9] J. I. Hoepner. Boundary Independent Broadcasts in Graphs. Graduate thesis, University of Victoria, Victoria, BC, Canada, 2022. http://hdl.handle.net/1828/14556.
  * [10] R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of computer computations, pages 85–103. Plenum Press, New York, 1972
  * [11] E. Marchessault and C. M. Mynhardt. Lower boundary independent broadcasts in trees. Discuss. Math. Graph Theory, to appear. Accepted September 12, 2021. https://doi.org/10.7151/dmgt.2434.
  * [12] C. M. Mynhardt and L. Neilson. A sharp upper bound for the boundary independence broadcast number of a tree. arxiv:2104.02266v2, 2021.
  * [13] C. M. Mynhardt and L. Neilson. Boundary independent broadcasts in graphs. J. Combin. Math. Combin. Comput., 116 (2021), 79-100.
  * [14] C. M. Mynhardt and L. Neilson. Comparing Upper Broadcast Domination and Boundary Independence Numbers of Graphs. Trans. Comb., to appear. arxiv:2104.02257, 2021.
  * [15] C. M. Mynhardt and L. Neilson. Lower bound and exact values for the boundary independence broadcast number of a tree. arxiv:2105.02312v1, 2021.
  * [16] L. Neilson. Broadcast Independence in Graphs. Doctoral dissertation, University of Victoria, Victoria, BC, Canada, 2019. https://dspace.library.uvic.ca/bitstream/handle/1828/11084/Neilson_Linda_PhD_2019.pdf.
  * [17] H. N. de Ridder et al. ISGCI: Information System on Graph Classes and their Inclusions - Graph classes listen by hardness of the independent set problem. https://www.graphclasses.org/classes/problem_Independent_set.html.


# Topological insulators in the NaCaBi family with large SOC gaps

Dexi Shao  Beijing National Laboratory for Condensed Matter Physics, and
Institute of Physics, Chinese Academy of Sciences, Beijing 100190, China
Zhaopeng Guo  Beijing National Laboratory for Condensed Matter Physics, and
Institute of Physics, Chinese Academy of Sciences, Beijing 100190, China
National Laboratory of Solid State Microstructures and School of Physics,
Nanjing University, Nanjing 210093, China  Xianxin Wu  Max-Planck-Institut für
Festkörperforschung, Heisenbergstrasse 1, D-70569 Stuttgart, Germany  Beijing
National Laboratory for Condensed Matter Physics, and Institute of Physics,
Chinese Academy of Sciences, Beijing 100190, China  Simin Nie  Department of
Materials Science and Engineering, Stanford University, Stanford, California
94305, USA  Jian Sun  Corresponding author. Email<EMAIL_ADDRESS>National
Laboratory of Solid State Microstructures and School of Physics, Nanjing
University, Nanjing 210093, China  Collaborative Innovation Center of Advanced
Microstructures, Nanjing 210093, China  Hongming Weng  Beijing National
Laboratory for Condensed Matter Physics, and Institute of Physics, Chinese
Academy of Sciences, Beijing 100190, China  University of Chinese Academy of
Sciences, Beijing 100049, China  Zhijun Wang  Corresponding author. Email:
<EMAIL_ADDRESS>Beijing National Laboratory for Condensed Matter Physics, and
Institute of Physics, Chinese Academy of Sciences, Beijing 100190, China
University of Chinese Academy of Sciences, Beijing 100049, China

###### Abstract

By means of first-principles calculations and crystal structure searching
techniques, we predict that a new NaCaBi family crystallized into the ZrBeSi-
type structure (i.e., $P6_{3}/mmc$) are strong topological insulators (STIs).
Taking $P6_{3}/mmc$ NaCaBi as an example, the calculated band structure
indicates that there is a band inversion between two opposite-parity bands at
the $\Gamma$ point. In contrast to the well-known Bi2Se3 family, the band
inversion in the NaCaBi family has already occured even without spin-orbit
coupling (SOC), giving rise to a nodal ring surrounding $\Gamma$ in the
$k_{z}=0$ plane (protected by $M_{z}$ symmetry). With time reversal symmetry
$(\cal T)$ and inversion symmetry $(\cal I)$, the spinless nodal-line metallic
phase protected by $[{\cal TI}]^{2}=1$ is the weak-SOC limit of the spinful
topological insulating phase. Upon including SOC, the nodal ring is gapped,
driving the system into a STI. Besides inversion symmetry, the nontrivial
topology of NaCaBi can also be indicated by $\bar{6}$ symmetry. More
surprisingly, the SOC-induced band gap in NaCaBi is about 0.34 eV, which is
larger than the energy scale of room temperature. Four other compounds (KBaBi,
KSrBi, RbBaBi and RbSrBi) in the family are stable at ambient pressure, both
in thermodynamics and lattice dynamics, even though the gaps of them are
smaller than that of NaCaBi. Thus, they provide good platforms to study
topological states both in theory and experiments.

Figure 1: (a) Calculated enthalpy relative to that of $P6_{3}/mmc$ phase vs.
pressure. (b) Phonon dispersions for the $P6_{3}/mmc$ phase at the ambient
pressure, which justify the lattice dynamical stability of this phase. (c)
Five crystal structures crystallized into the $P6_{3}/mmc$, $P3m1$, $Pnma$,
$F\bar{4}3m$ and $P\bar{4}2m$ phases of stoichiometric NaCaBi near the convex
hull from the formation enthalpies.

##  I INTRODUCTION

Topological insulators (TIs) have been studied broadly and deeply in both
theory and experiments, since the two-dimensional quantum spin Hall effect (2D
TI) was proposed in 2005 Kane2005 . By generalizing the concept of TIs, the
three-dimensional (3D) TIs were predicted in the Bi2Se3 family Bi2X3-zhj2009 ,
which were verified in the experiments later Hsieh2009 ; Bi2X3-Hasan2009 ;
Bi2Te3-Shen2009 . TIs embody a new quantum state characterized by a
topological invariant rather than a spontaneously broken symmetry. The
nontrivial topology of TIs is well defined by the wave functions of occupied
bands, as long as there is a continuous energy gap between the conduction
bands and valence bands in the whole Brillouin zone (BZ). Then, the $\cal
T$-invariant TIs are generalized to topological crystalline insulators (TCIs)
TCI-FuLiang-2011 ; TCI-SG-2013 ; TCI-TSC-2014 ; Wang2016Hourglass ; Ma2017 ,
in which the lattice symmetries play important roles. Generally, symmetry
eigenvalues and irreducible representations (irreps) can indicate topological
property. For example, the well-known Fu-Kane parity indices are widely used
for centrosymmetric TIs Fu-Kane-2007 , and the recently established symmetry
indicators and topological quantum chemistry are very efficient to diagnose
the nontrivial topology of TIs and TCIs wzj2019 ; Bradlyn2018 ; Bradlyn2019 ;
Ashvin-SI-2017 ; Songzd-TCI-2018 ; Bradlyn2017 ; ZhangTT2019 ; TangF2019 ;
Vergniory2019 . Although many candidates for TIs/TCIs have been proposed, the
TIs protected by sixfold rotoinversion symmetry [i.e., the sixfold
rotoinversion $\bar{6}~{}(\equiv{\cal I}C_{6})$ is a sixfold rotation
($C_{6}$) followed by inversion ($\cal I$)] are rarely reported.

The 3D TIs have attracted tremendous attention because their surface states
possess odd spin-momentum locked Dirac cones, thus, the backscattering
channels of the surface states are suppressed, leading to dissipationless
electronic transport Hsieh2009 ; Bi2X3-zhj2009 ; TIs-Hasan2010 ; TIs-
FuLiang2011 . In proximity to an $s$-wave superconductor (SC), the topological
surface states can acquire an effective $p$-wave superconducting paring,
resulting in a 2D topological SC PhysRevLett.100.096407 . In addition, the TIs
can be tuned into many interesting topological states. For instance, the
quantum anomalous Hall (QAH) insulator is found in the Cr-doped Bi2Te3 Yu2010
; Chang2013 . Furthermore, the compound MnBi2Te4 is predicted to be an
antiferromagnetic TI at zero magnetic field and a Weyl semimetal under the
out-of-plane magnetic field xuyong2019 . Recently, the QAH effect has been
observed in few-layer thin films nwaa089 . Moreover, the unconventional SC has
been proposed and some experimental evidences were revealed in Cu-doped Bi2Se3
PhysRevLett.104.057001 ; NP2010 . The strong evidences of Majorana zero-energy
mode within a vortex in the TI/SC heterostructure – Bi2Te3/NbSe2 – have been
proposed recently PhysRevLett.114.017001 . Therefore, the TI candidates are of
great interest, especially those with relatively large band gaps, which not
only benefit the the future applications of spintronics and quantum
computation from the dissipationless surface states, but also provide good
platforms to study the interplay between the topological phase and symmetry-
breaking phases. Though many TI candidates and corresponding interesting
properties have been proposed Bi2X3-zhj2009 ; TIs-Hasan2010 ; TIs-FuLiang2011
; Wu2016 ; Nie2018 , TIs with relatively large band gaps and clear 2D Dirac-
cone surface states as the Bi2Se3 family are rare.

In this work, using crystal structure searching techniques and first-
principles calculations, we predict that NaCaBi can be stable in the space
group (SG) of $P6_{3}/mmc$ at pressures up to 10 GPa from both the thermal
dynamics and the lattice dynamics. Calculations of the band structures
indicate that without SOC, $P6_{3}/mmc$ NaCaBi is a topological semimetal with
a nodal ring surrounding the $\Gamma$ point in the $k_{z}=0$ plane. Upon
including SOC, the crossing points of the nodal line are all gapped and the
system becomes a STI. We find that the nontrivial topology can be indicated
not only by inversion symmetry, but also by the $\bar{6}$ symmetry. Moreover,
it is exciting that the topologically nontrivial band gap is about 0.34 eV due
to strong SOC, which is even larger than the energy scale of room temperature.
At last, four other dynamically stable XYBi compounds with similar electronic
structures and STI natures are proposed in Section 4 of Appendix.

##  II Calculations and Results

###  II.1 The crystal structures of stoichiometric NaCaBi

We used crystal structure prediction techniques integrated in USPEX Oganov2006
; Artem2011 ; Lyakhov2013 and the machine learning accelerated crystal
structure search method Gao2018 to find the best candidates of NaCaBi under
pressure. From the phase diagrams based on convex hull analysis of formation
enthalpies for the Na-Ca-Bi ternary system at 0 GPa and 10 GPa shown in Fig.
5, we find stoichiometric NaCaBi crystallizes in $Pnma$ phase at 0 GPa and
$P6_{3}/mmc$ phase at 10 GPa, respectively. We extract several structures of
stoichiometric NaCaBi near the two stable phases from the formation enthalpy,
which are in SGs of $P6_{3}/mmc$, $P3m1$, $Pnma$, $F\bar{4}3m$ and
$P\bar{4}2m$, respectively. The enthalpy-pressure ($\triangle H-P$) curves
between these phases plotted in Fig. 1(a) exhibit the best ones from our
structural predictions at pressures up to 10 GPa. At ambient pressure, the
most stable structure of NaCaBi is found to be $Pnma$ phase, and the enthalpy
of $P6_{3}/mmc$ phase is just 0.17 eV/$f.u.$ higher than that of $Pnma$ phase.
Our calculations reveal that $P6_{3}/mmc$ phase becomes preferred at pressures
higher than 1 GPa.

As shown in Fig. 1(b) and Fig. 8, there is no phonon mode with negative
frequency in the phonon spectra of $P6_{3}/mmc$ NaCaBi under pressures from 0
GPa to 10 GPa, which indicates that the metastable $P6_{3}/mmc$ phase could be
quenched to ambient pressure if they can be synthesized at higher pressure.
These results are in accordance with the earlier work Zhang2012 ; Peng2018 .
As shown in Fig. 7(c), calculations of the ab initio molecular dynamic (AIMD)
simulations at ambient pressure and T = 600 K indicates that there is no
structural collapse after 10 ps (10000 steps). In addition, motivated by
earlier works Levy2010 ; Shao2017 , how the parameters evolves under pressure,
strain potential and the possible substrates are also discussed in Section 8
of Appendix. As shown in Fig. 8 and Table 6, we also list many other XYBi
compounds in the $P6_{3}/mmc$ phase which are dynamically stable at low
pressures. Besides NaCaBi, other four XYBi compounds (i.e., KBaBi, KSrBi,
RbBaBi, and RbSrBi) have similar band structures, thus the same STI nature
with NaCaBi (see Section 4 of the Appendix). Different from NaCaBi, the
$P6_{3}/mmc$ phase of KBaBi, KSrBi, RbBaBi and RbSrBi are always energetically
preferred from 0 GPa to 10 GPa, as shown in Fig. 6. Moreover, the NaCaBi
system possesses the largest inverted band gap, as shown in Table 1. In the
following, we will focus on NaCaBi with $P6_{3}/mmc$ phase in the main text.

Table 1: Band gaps of the NaCaBi family at 0 GPa. XYBi | NaCaBi | KBaBi | KSrBi | RbBaBi | RbSrBi
---|---|---|---|---|---
Gaps (eV) | 0.34 | 0.22 | 0.26 | 0.20 | 0.25

###  II.2 The band structures of $P6_{3}/mmc$ NaCaBi

From the band structures of $P6_{3}/mmc$ NaCaBi without SOC shown in Fig.
2(a), we can find two band crossings along K–$\Gamma$ and $\Gamma$–M at
$E_{F}$. The orbital-resolved band structures in Fig. 2(a) indicate that the
valence band maximum is contributed by the Bi-$p$ states, while the conduction
band minimum is from the Ca-$s$ states (which also hybridize with the Bi-$s$,
Na-$s$ and Ca-$d$ states). Calculations of the irreps gao2021 indicate that
the two bands belong to GM$1+$ and GM$2-$ irreps respectively [Fig. 2(a)], in
the convention of the Bilbao Crystallographic Server notations at $\Gamma$
(GM). The parities of the occupied bands at eight time-reversal invariant
momenta (TRIMs) are given in Table 2. Thus, we conclude that the band
inversion appears between opposite-parity bands around $\Gamma$ without SOC,
which guarantees the existence of nodal line(s) in the spinless systems with
$\cal T$ and $\cal I$. Furthermore, this nodal ring surrounding $\Gamma$ lies
in the $k_{z}=0$ plane due to the presence of $M_{z}$ symmetry (i.e., the two
inverted bands have different $M_{z}$ eigenvalues).

Figure 2: (a) Orbital-resolved band structures of $P6_{3}/mmc$ NaCaBi at 0 GPa
without SOC. (b) The BZ of $P6_{3}/mmc$ NaCaBi, where the high-symmetry
$\vec{k}$ points are marked out. (c) Band structures of $P6_{3}/mmc$ NaCaBi at
0 GPa with SOC. The red line corresponds to the 0.06 hole doping case (i.e.,
EH-EF=-0.25 eV). (d) The constant-energy contour surface at EH is a torus.

The spinful topological insulating phase can be considered as a (strong-)SOC
limit of the spinless nodal-line metallic phase protected by $[{\cal
TI}]^{2}=1$ wzj2019 . As shown in Fig. 2(c), we can find that SOC induces a
visible band gap between the two inverted bands around $\Gamma$, but it does
not change the ordering of energy bands at $\Gamma$. The nodal ring is fully
gapped, thus, the NaCaBi becomes a STI. More surprisingly, the SOC-induced
band gap is as large as 0.34 eV, which is comparable with thermal energy of
room temperature. The $P6_{3}/mmc$ phase of NaCaBi family compounds provides
good platforms to study topological states both in theory and experiments.
Considering the possible underestimation of the band gap by Perdew-Burke-
Ernzerhof (PBE) method GGA-PBE1996 , the band inversion can be further
confirmed by the calculations using hybrid Heyd-Scuseria-Ernzerhof (HSE)
functional HSE2006 . The results shown in Section 5 of the Appendix indicate
that the SOC-induced band gap is almost unchanged, although the inverted gap
at $\Gamma$ (i.e., $E_{g}\equiv|E_{\text{GM1+}}-E_{\text{GM}2-}|$) becomes
smaller.

Symmetry eigenvalues (or irreps) play key roles in identifying TIs/TCIs in
solids Bradlyn2019 ; Ashvin-SI-2017 ; Songzd-TCI-2018 . As we know, SG 194
belongs to a $\mathbb{Z}_{12}$ classification. Using irvsp gao2021 and Check
Topological Mat Vergniory2019 , all symmetry indicators are calculated to be
$z_{2w,i=1,2,3}=0;~{}z_{4}=3;~{}z_{6m,0}=5;~{}z^{\prime}_{12}=11$. By
performing the symmetry analysis, we find that there are two essential
symmetries indicating the nontrivial topology in this system. One is the
inversion symmetry, while the other is the $\bar{6}$ symmetry. In other words,
even though the inversion is broken when the SG is reduced to SG 174
(P$\bar{6}$), the nontrivial topology can be still indicated by $z_{3m,0}=1$
and $z_{3m,\pi}=0$. With $M_{z}\equiv[\bar{6}]^{3}$, these indicate that the
mirror Chern numbers of $k_{z}=0$ and $k_{z}=\pi$ planes are 1 and 0,
respectively. Thus, this system has to be a 3D STI.

Table 2: The product of the parities for all the occupied bands at the eight TRIMs for the $P6_{3}/mmc$ phase of NaCaBi. TRIM | $\Gamma$ | 3M | A | 3L | Product
---|---|---|---|---|---
Parity | + | \-- | \-- | \-- | \--

###  II.3 The surface states of $P6_{3}/mmc$ NaCaBi

Exotic topological surface states serve as significant fingerprints to
identify various topological phases. Based on the tight-binding model
constructed with the maximally localized Wannier functions (MLWFs) and surface
Green’s function methods Qui-iter-sche ; SurfaceGF ; wu2017wanniertools , we
have calculated the corresponding surface states of this system with SOC to
identify its topological properties (see Section 6 of the Appendix). As shown
in Figs. 3(a) and 3(b), the 2D Dirac cone is obtained on (010) and (001)
surfaces. Thus, the calculated surface states agree well with the analysis of
the symmetry indicators, which confirm the STI nature of NaCaBi.

Figure 3: (a,b) Surface states of NaCaBi terminated in the (010) surface and
(001) surface, respectively. Both (010) and (001) surfaces exhibit a 2D Dirac
cone.

###  II.4 Low-energy effective model

We find that the topologically nontrivial nature is determined by the low-
energy dispersions near $E_{F}$ around $\Gamma$, which motivates us to build
the effective $\mathbf{k}\cdot\mathbf{p}$ Hamiltonian to get further insights
in this system. In the presence of SOC, the irreps for the lower energy bands
at $\Gamma$ are $\Gamma_{7}^{+}$ and $\Gamma_{7}^{-}$, respectively (labeled
in the double point group of $D_{6h}$).

Thus, we can construct the $4\times 4$ Hamiltonian under the bases of the two
irreps (i.e., $|+,\uparrow\rangle;|+,\downarrow\rangle;|-,\uparrow\rangle$ and
$|-,\uparrow\rangle$) with the theory of invariants invariant-theory2003 .
Here the $\pm$ denote the parities of the eigenstates and
$\uparrow~{}(\downarrow)$ denotes $j_{z}=+\frac{1}{2}~{}(-\frac{1}{2})$.
Taking time reversal symmetry and the symmetries of double group $D_{6h}$ into
consideration (see details in Section 7 of the Appendix), we derive the
following ${\bf k}\cdot{\bf p}$ invariant Hamiltonian in the vicinity of
$\Gamma$ (up to the second order of $\vec{k}$),

$\begin{split}H_{0}(\vec{k})&=\epsilon_{0}(\vec{k}){\mathbb{I}}_{4}+\left(\begin{array}[]{cccc}M(\vec{k})&0&A_{1}k_{z}&A_{2}k_{-}\\\
0&M(\vec{k})&A_{2}k_{+}&-A_{1}k_{z}\\\ A_{1}k_{z}&A_{2}k_{-}&-M(\vec{k})&0\\\
A_{2}k_{+}&-A_{1}k_{z}&0&-M(\vec{k})\\\ \end{array}\right)\end{split}$ (1)

where $k_{\pm}=k_{x}\pm ik_{y}$,
$\epsilon_{0}(\vec{k})=C+D_{1}k_{z}^{2}+D_{2}k_{\bot}^{2}$ and
$M(\vec{k})=M-B_{1}k_{z}^{2}-B_{2}k_{\bot}^{2}$ with
$k_{\bot}^{2}=k_{x}^{2}+k_{y}^{2}$. This is nothing but the well-known 3D TI
Hamiltonian in the Bi2Se3 family Bi2X3-zhj2009 in the case of $M\cdot
B_{1,2}>0$, the band inversion happens between the two different-parity bands.
By fitting the energy dispersions, we obtain the parameters: $M$=$-$0.4554 eV,
$A_{1}$=4.0 eVÅ, $A_{2}$= 1.3 eVÅ, $B_{1}$=$-$16.7 eVÅ2, $B_{2}$=18.6 eVÅ2,
$C$=$-$0.0689 eV, $D_{1}$=$-$6.4 eVÅ2, $D_{2}$=8.5 eVÅ2.

As aforementioned, the nontrivial topology of this system can be also
protected/indicated by $\bar{6}$ symmetry. If we introduce the additional
$\delta_{1}$ ($\delta_{2}$) term as shown in Eq. (2), $C_{2x}~{}(C_{2y})$ and
$M_{y}~{}(M_{x})$ will be broken. Therefore, by simply adding the two
additional terms (both of which break $C_{6z}$ and $\cal I$), the
$\bar{6}$-invariant Hamiltonian is obtained below,

$\begin{split}&H(\vec{k})=H_{0}(\vec{k})+H_{1}(\delta_{1}+i\delta_{2},\vec{k})\\\
&H_{1}(z,\vec{k})=\left(\begin{array}[]{cccc}0&0&0&-z^{*}k_{+}^{2}\\\
0&0&zk_{-}^{2}&0\\\ 0&z^{*}k_{+}^{2}&0&0\\\ -zk_{-}^{2}&0&0&0\\\
\end{array}\right)\end{split}$ (2)

In the presence of $\bar{6}$ symmetry, the $C_{3z}$ and $M_{z}$ symmetries are
still preserved. Thus, one can check that in the case of $M\cdot B_{1,2}>0$,
the mirror Chern number of the $k_{z}=0$ plane is 1. On the other hand, one
can also compute the symmetry indicators of SG 174 ($P\bar{6}$), which is
founed to be $z_{3m,0}=1$. This implies that the $\mathbb{Z}_{2}$ invariant
for the $k_{z}=0$ plane is 1. Combined with the trivial $\mathbb{Z}_{2}$
invariant for the $k_{z}=\pi$ plane, one can conclude that $z_{3m,0}=1$ and
$z_{3m,\pi}=0$ yield the STI nature of $P6_{3}/mmc$ NaCaBi. Suppose that we
move the two Na atoms at $2a$ Wyckoff positions reversely along $z$ axis a
little (e.g., two percent of the third lattice vector along $z$ axis), this
distortion preserves $\bar{6}$ symmetry, but breaks inversion symmetry and
$C_{6z}$ symmetry. In this disturbed structure, the $\delta_{1}$ and
$\delta_{2}$ are fitted to be 0.4 eVÅ2 and 0 eVÅ2. The STI phase is indicated
by the symmetry indicators: $z_{3m,0}=1$ and $z_{3m,\pi}=0$, since there is no
band crossing occurring in this process.

##  III DISCUSSION

Figure 4: Electron-phonon coupling calculations of $P6_{3}/mmc$ NaCaBi. (a)
Phonon spectra, phonon density of states (PDOS) and Eliashberg spectral
functions $\alpha^{2}F(\omega)$ together with the electron-phonon integral
$\lambda(\omega)$ in the left, middle and right panels, respectively. (b) The
$B_{2g}$ vibrational mode.

In carrier-doped TIs, odd-parity pairing and nematic pairing have been
theoretically proposed to realize topological superconductivity Fu2010 ;
Fu2014 . Some supporting evidences in Cu-doped Bi2Se3 are revealed in
experiments but the pairing symmetry is still under active debate Sasaki2011 ;
Kirzhner2012 ; Bay2012 ; Levy2013 ; Matano2016 . In analogous to Bi2Se3,
superconductivity and topological paring states may be achieved with electron
doping in NaCaBi. One prominent feature of $P6_{3}/mmc$ NaCaBi is that the
band inversion is kept with SOC and is significantly large, resulting a
double-peak valence band around $\Gamma$, as shown in Fig. 2(c). Within a
relatively large hole doping region, the Fermi surface is a torus around the
$\Gamma$ point rather than spheres in other TIs, as shown in Fig. 2(d). As the
topology of the Fermi surface is distinct from electron-doped case, the
pairing state can be also different and may be unconventional. For example,
for the intra-orbital spin singlet pairing
$c_{+\uparrow}c_{+\downarrow}-c_{-\uparrow}c_{-\downarrow}$, which belongs to
a trivial irrep, two nodal lines of gap functions in band space are expected
on the torus. We leave the question of determining possible pairing states by
solving effective models to future work. Nevertheless, we investigate the
superconducting properties by electron-phonon coupling calculations and the
Allen-Dynes modified McMillian equation Tc-Allen . Considering 0.06 hole
dopping in NaCaBi system at ambient pressure, Tc is estimated to be about 1.5
K with a commonly used screened Coulomb potential $\mu^{*}=0.10$. Most of the
contributions to electron-phonon coupling constant arise from the $B_{2g}$
vibrational mode, i.e., vibrations of Ca atoms and Bi atoms along $z$ axis, as
shown in Fig. 4(b).

In summary, we propose a new NaCaBi family which are STIs with large SOC-
induced band gaps, among which KBaBi, KSrBi, RbBaBi and RbSrBi are stable at
ambient pressure, both in thermodynamics and lattice dynamics. In terms of the
NaCaBi system, the corresponding symmetry analysis indicates that there exists
a clear band inversion between two opposite-parity bands near $E_{F}$. Without
SOC, the band inversion gives rise to a nodal ring around $\Gamma$ in the
$k_{z}=0$ plane. Upon including SOC, it becomes a STI with a SOC-induced band
gap of 0.34 eV, which is larger than the energy scale of room temperature. The
calculated symmetry indicators of SG 194 indicate that the nontrivial topology
of NaCaBi can be revealed by not only the inversion symmetry, but also
$\bar{6}$ symmetry. As expected, 2D Dirac cones are obtained in the
(010)-surface and (001)-surface spectra. Due to the large SOC-induced band gap
in the STI phase, it is promising to expect clear experimental evidences of
the topological surface states from angle-resolved photoemission spectroscopy
(ARPES) and scanning tunnelling microscopy in the future. With hole doping,
the contour surface of the valence band near $E_{F}$ is a torus, which may
bring unconventional superconducting pairing.

##  IV ACKNOWLEDGMENTS

We thank the fruitful discussions with Lu Liu, Tong Chen and Qinyan Gu. This
work is supported by the National Natural Science Foundation of China (Grants
Nos. 11974395, 11974162, 11925408, 11834006 and 11921004). J.S. also
gratefully acknowledges financial support from the National Key R&D Program of
China (Grant Nos. 2016YFA0300404) and the Fundamental Research Funds for the
Central Universities. Part of the calculations were carried out using
supercomputers at the High Performance Computing Center of Collaborative
Innovation Center of Advanced Microstructures, the high-performance
supercomputing center of Nanjing University. Z.W. and H.W. also acknowledge
support from the National Key Research and Development Program of China (Grant
Nos. 2016YFA0300600, 2016YFA0302400, and 2018YFA0305700), the K. C. Wong
Education Foundation (GJTD-2018-01), the Strategic Priority Research Program
of Chinese Academy of Sciences (Grant No. XDB33000000), and the center for
Materials Genome.

## APPENDIX

### 1\. Calculation methods

_Ab initio_ calculations. We performed first-principles calculations based on
the density functional theory (DFT) using projector augmented wave (PAW)
method implemented in the Vienna ab initio simulation package (VASP)
kresse1999 for the calculations of the structure optimization and electronic
structures. The generalized gradient approximation (GGA), as implemented in
the Perdew-Burke-Ernzerhof (PBE) functional GGA-PBE1996 was adopted. The
cutoff parameter for the wave functions was 850 eV. The BZ was sampled by
Monkhorst-Pack method Monkhorst-BZ1976 with a k-spacing of $0.025\times 2\pi$
Å-1 for the 3D periodic boundary conditions. The phonon calculations were
performed by finite displacement method implemented in the PHONOPY code
phonopy , with a $2\times 2\times 2$ supercell. A kmesh of $20\times 20\times
16$ was used to calculate the Fermi surface of the valence band near the Fermi
level. Electron-phonon coupling calculations are performed in the framework of
Density functional perturbation theory, as implemented in the quantum-espresso
code QE2009 .

Figure 5: Phase diagram based on convex hull analysis of formation enthalpies
for the Na-Ca-Bi ternary system at (a) 0 GPa and (b) 10 GPa. The solid red
circles in the figures denote the stable structures, while the hollow red
circles denote the corresponding structures lying above the convex hull which
indicates these structures are metastable candidates. The solid red circle in
the center of the equilateral triangle in figure (a) and (b) denote the $Pnma$
phase at 0 GPa and $P6_{3}/mmc$ phase at 10 GPa.  Table 3: Crystal structures
of NaCaBi after structure optimization.

SG | {$\alpha,\beta,\gamma$} | {a,b,c} | Wyckoff positions
---|---|---|---
$P6_{3}/mmc$ | $\alpha=\beta=90{}^{\circ},\gamma=120{}^{\circ}$ | $\\{a=b=5.566{\AA},c=6.804{\AA}\\}$ |  {$2a,2c,2d$}
$P3m1$ | $\alpha=\beta=90{}^{\circ},\gamma=120{}^{\circ}$ | $\\{a=b=5.3431{\AA},c=7.41{\AA}\\}$ |  {$1a\oplus 1c,1b\oplus 1c,1a\oplus 1b$}
$Pnma$ | $\alpha=\beta=\gamma=90{}^{\circ}$ | $\\{a=8.088{\AA},b=4.784{\AA},c=9.681{\AA}\\}$ |  {$4c,4c,4c$}
$F\bar{4}3m$ | $\alpha=\beta=\gamma=90{}^{\circ}$ | $\\{a=b=c=7.530{\AA}\\}$ |  {$4a,4b,4c$}
$P\bar{4}2m$ | $\alpha=\beta=\gamma=90{}^{\circ}$ | $\\{a=b=7.5706{\AA},c=7.5032{\AA}\\}$ |  {$1a\oplus 1b\oplus 2f,1c\oplus 1d\oplus 2e,4n$}

  * 1

1\. The ‘‘SG’’ column denotes the space group in which NaCaBi crystallises
into.

  * 2

2\. {$\alpha,\beta,\gamma$} and {a,b,c} denote the lattice parameters of the
conventional cell (while not primitive cell) in each phase.

  * 3

3\. The ‘‘Wyckoff positions’’ column gives the Wyckoff positions of Na, Ca and
Bi in each phase. ‘‘$1a\oplus 1c$’’, ‘‘$1b\oplus 1c$’’ and ‘‘$1a\oplus 1b$’’
in $P3m1$ phase indicates that there exist two nonequivalent
‘‘‘Na’’/‘‘‘Ca’’/‘‘‘Bi’’ atoms occupying (1a and 1c)/(1b and 1c)/(1a and 1b)
Wyckoff positions in this phase, respectively.

### 2\. Crystal structure searching

We perform a variable composition calculation to get the phase diagrams of Na-
Ca-Bi ternary system at ambient condition (0 GPa) and 10 GPa. At ambient
condition, we find $Pnma$ NaCaBi is the unique ternary phase lying in the
convex hull (denoted by the solid red circle in the center of the equilateral
triangle), as shown in Fig. 5(a). Meanwhile, there exist three other
metastable ternary candidates, i.e., P4/mmm-NaCaBi2, Cmmm NaCa2Bi3 and R3m
Na4CaBi2, above the convex hull (denoted by the hollow red circles in the the
equilateral triangle). The corresponding enthalpies of these metastable
ternary candidates above convex hull (denoted by $\triangle H$) of $P4/mmm$
NaCaBi2, $Cmmm$ NaCa2Bi3 and $R3m$ Na4CaBi2 are 16.0 meV/atom, 13.3 meV/atom
and 19.7 meV/atom, respectively. We have listed the structure parameters of
these ternary structures in Table. 4.

At 10 GPa, we find $P6_{3}/mmc$ NaCaBi and $Cmmm$ NaCa2Bi3 (denoted by two
solid red circles lying inside the equilateral triangle) are two stable
ternary structures lying in the convex hull, as shown in Fig. 5(b). In
addition, the convex hull analysis indicates that there are three other
structures ($C2/m$ Ca3Bi2, $Cmmm$ NaCaBi2 and $P4/mmm$ NaCa2Bi) lying above
the convex hull, which indicates they are metastable candidates. The
corresponding structure parameters are listed in Table. 5. It should be noted
that $C2/m$ Ca3Bi2 and $Cmmm$ NaCaBi2 are metastable candidates with only 0.64
meV/atom and 1.2 meV/atom above the convex hull. We also remind that binary
Na-Bi and binary Ca-Bi phases in the convex hull are almost in accordance with
earlier works Ca-Bi-2015 ; NaBi-system-2015 .

Table 4: Crystal structures of Na-Ca-Bi ternary system near the convex hull at
ambient condition.

SG | {$\alpha,\beta,\gamma$} | {a,b,c} | Wyckoff positions | $\triangle H$
---|---|---|---|---
$Pnma$-NaCaBi | $\alpha=\beta=\gamma=90{}^{\circ}$ | $\\{a=8.088{\AA},b=4.784{\AA},c=9.681{\AA}\\}$ |  {$4c,4c,4c$} | 0
$P4/mmm$-NaCaBi2 | $\alpha=\beta=\gamma=90{}^{\circ}$ | $\\{a=b=5.2019{\AA},c=9.6268{\AA}\\}$ |  {$1c,1a,2e$} | 16
$Cmmm$-NaCa2Bi3 | $\alpha=\beta=\gamma=90{}^{\circ}$ | $\\{a=15.2393{\AA},b=5.1890{\AA},c=4.5445{\AA}\\}$ |  {$2a,4g,4h\oplus 2c$} | 13.3
$R3m$-Na4CaBi2 | $\alpha=\beta=90{}^{\circ},\gamma=120{}^{\circ}$ | $\\{a=b=5.4382{\AA},c=26.6190{\AA}\\}$ |  {$3a\oplus 3a\oplus 3a\oplus 3a,3a,3a\oplus 3a$} | 19.7

  * 1

1\. $\triangle H$ column is under the unit of meV.

Table 5: Crystal structures of Na-Ca-Bi ternary system near the convex hull at 10 GPa. SG | {$\alpha,\beta,\gamma$} | {a,b,c} | Wyckoff positions | $\triangle H$
---|---|---|---|---
$P6_{3}/mmc$-NaCaBi | $\alpha=\beta=90{}^{\circ},\gamma=120{}^{\circ}$ | $\\{a=b=5.1857{\AA},c=6.2652{\AA}\\}$ |  {$2a,2c,2d$} | 0
$Cmmm$-NaCa2Bi2 | $\alpha=\beta=\gamma=90{}^{\circ}$ | $\\{a=14.6714{\AA},b=4.7828{\AA},c=4.3440{\AA}\\}$ |  {$2a,4g,4h\oplus 2c$} | 0
$Cmmm$-NaCaBi2 | $\alpha=\beta=\gamma=90{}^{\circ}$ | $\\{a=6.7302{\AA},b=8.7712{\AA},c=3.3638{\AA}\\}$ |  {$2c,2d,4e$} | 1.2
$P4/mmm$-NaCa2Bi | $\alpha=\beta=\gamma=90{}^{\circ}$ | $\\{a=b=4.7903{\AA},c=4.3642{\AA}\\}$ |  {$2c,2d,4e$} | 9.5

Figure 6: Calculated enthalpy between the $Pnma$ phase and $P6_{3}/mmc$ phase
vs. pressure for NaCaBi, NaSrBi, KBaBi, KSrBi, RbBaBi and RbSrBi,
respectively.

We do not perform ternary structural searching for the other four XYBi
candidates, because it will be time consuming. But, similar with NaCaBi, the
thermal stability between the $P6_{3}/mmc$ phase and the $Pnma$ phase are
discussed. As shown in Fig. 6, the $Pnma$ phase of NaSrBi is always preferred
under pressures from 0 GPa to 10 GPa, while for cases of KBaBi, KSrBi, RbBaBi
and RbSrBi, the $P6_{3}/mmc$ phase are always preferred. It means the STI
phase can be obtained in the KBaBi, KSrBi, RbBaBi and RbSrBi systems without
any quenched progress.

### 3\. Molecular dynamics

Figure 7: After 10 ps AIMD simulation, the side view (a) along (001) direction
and (b) along (110) direction of the $3\times 3\times 2$ supercell of NaCaBi
at 600 K. (c) The NVT-molecular dynamic (MD) simulations of the NaCaBi at
static pressure and T = 600 K.

To check the thermal stability of $P6_{3}/mmc$ NaCaBi, we have performed ab
initio molecular dynamic (AIMD) simulations with a $3\times 3\times 2$
supercell at ambient pressure and T = 600 K. As shown in Fig. 7(c), no
structural collapse was observed after 10 ps (10000 steps), which indicates
the thermal stability of NaCaBi at ambient pressure.

### 4\. Phonon spectra and band structures of XYBi compounds with $P6_{3}/mmc$
structure under low pressures

Figure 8: Band structures and phonon spectra of $P6_{3}/mmc$ RbHgSb and XYBi
when they are dynamically stable under 0 GPa, 5 GPa and 10 GPa, respectively.
Our calculations reproduce the Dirac point in the $P6_{3}/mmc$ RbMgBi system
Le2017 .  Table 6: Dynamically stable RbHgSb and XYBi systems at 0 GPa, 5 GPa
and 10 GPa, respectively.

Pressure(GPa) | RbHgSb and XYBi systems
---|---
0 GPa | NaCaBi*,KBaBi*,KSrBi*,KZnBi,RbBaBi*,RbCdBi,RbHgSb,RbMgBi,RbSrBi*,RbZnBi
5 GPa | NaCaBi*,NaSrBi*,NaZnBi,KBaBi,KSrBi,RbBaBi,RbCaBi,RbSrBi,RbZnBi
10 GPa | NaCaBi*,NaCdBi,NaSrBi*,NaZnBi,KBaBi,KSrBi,RbBaBi,RbCaBi,RbHgSb,RbSrBi

  * 1

Structures with ‘‘*’’ behind denote those possessing similar band structures
with $P6_{3}/mmc$ NaCaBi.

According to the online Materials Project MaterProject database, the Inorganic
Crystal Structure Database ICSD and the earlier work Zhang2012 , RbHgSb and
several XYBi systems with X = {Na, K,Rb} and Y = {Mg, Ca, Sr, Ba, Zn, Cd, Hg}
can crystallise into the ZrBeSi-type structure of $P6_{3}/mmc$. We performed
calculations in terms of the lattice dynamical stability for them at 0 GPa, 5
GPa and 10 GPa, respectively. Among, only the dynamically stable ones are
listed in Table 6. Their phonon spectra and band structures are giving in Fig
8. From Fig 8, we can find they are mainly classified into three classes: the
KHgSb-type TCI phase Wang2016Hourglass (i.e., KZnBi, RbCdBi, RbHgSb, RbZnBi),
the Na3Bi-type Dirac phase Wang2012 (i.e., NaZnBi, NaCdBi and RbMgBi) and the
STI phase. Since we are focused on the STI phase, several of these dynamically
stable compounds of the STI phase, having the similar band structures with
$P6_{3}/mmc$ NaCaBi in the main text, are denoted by ‘‘*" symbols.

### 5\. HSE calculations

It is known that the PBE functional tends to underestimate the band gap, we
recalculated the band structures of $P6_{3}/mmc$ NaCaBi system with the HSE06
functional HSE2006 , as shown in Fig. 9. We find the energy dispersions for
low energy bands using the HSE06 functional is similar to that using PBE
functional, which indicates that the topological nature is solid.

Figure 9: HSE band structures in comparison with DFT band structures.

### 6\. Wannier-based tight-binging model and surface states

Surface state plays an important role on justifying/characterizing TIs from
the bulk-boundary correspondence. Here we choose Ca-$s$, Ca-$d$ and Bi-$p$ as
the projected orbits to build the Wannier-based tight-binging model, it
reproduces the DFT band structures well, as shown in Fig. 10. Then, we
calculated the surface states based on this Wannier-based tight-binging model
of NaCaBi on the (010) and (001) surfaces, as presented in Fig. 3 in the main
text.

Figure 10: DFT vs Wannier bands.

### 7\. Matrix presentations of symmetry operators

Under the basis of $\Gamma_{7}^{+}$ and $\Gamma_{7}^{-}$, the symmetry
operators (e.g., $\cal T$, $\cal I$, $C_{6z}$, $C_{2x}$, $C_{2y}$) are
represented below:

$\begin{split}&{\cal T}=\tau_{0}\otimes(-i)\sigma_{y}{\cal K};~{}{\cal
I}=\tau_{z}\otimes\sigma_{0};~{}C_{6z}=\tau_{0}\otimes
e^{-i\frac{\pi}{3}\sigma_{z}};\\\
&C_{2x}=\tau_{0}\otimes(-i)\sigma_{x};~{}C_{2y}=\tau_{0}\otimes(-i)\sigma_{y},\end{split}$
(3)

where ${\cal K}$ denotes the complex conjugation,
$\tau_{x,y,z}~{}(\sigma_{x,y,z})$ are Pauli matrices in the orbital (spin)
space. Their (${\cal O}=P,Q,R,\cal T$) representations in momentum space are
given by ${\cal O}[k_{x},k_{y},k_{z}]^{T}=g_{\cal O}[k_{x},k_{y},k_{z}]^{T}$

$\begin{split}&g_{\cal T}=g_{\cal I}=\left(\begin{array}[]{ccc}-1&0&0\\\
0&-1&0\\\ 0&0&1\\\
\end{array}\right),~{}g_{C6z}=\left(\begin{array}[]{ccc}\frac{1}{2}&-\frac{\sqrt{3}}{2}&0\\\
\frac{\sqrt{3}}{2}&\frac{1}{2}&0\\\ 0&0&1\\\ \end{array}\right),\\\
&g_{C2x}=\left(\begin{array}[]{ccc}1&0&0\\\ 0&-1&0\\\ 0&0&-1\\\
\end{array}\right),~{}g_{C2y}=\left(\begin{array}[]{ccc}-1&0&0\\\ 0&1&0\\\
0&0&-1\\\ \end{array}\right).\end{split}$ (4)

The low-energy effective ${\bf k}\cdot{\bf p}$ Hamiltonian satisfies the
condition placed by the symmetry $\cal O$:

${\cal O}{\cal H}(\delta{\bf k}){\cal O}^{-1}={\cal H}(g_{\cal O}\delta{\bf
k})$ (5)

After considering all symmetry restrictions of $D_{6h}$, the low-energy
effective model is derived as given in the main text.

### 8\. Pressure, Strain and substrate candidates

Figure 11: (a) Lattice parameters a(= b) and c vs. Pressure. (b) Strain energy
vs. the linear biaxial strain along the $x$ and $y$ axes.

From the electronic properties of $P6_{3}/mmc$ NaCaBi at 0 GPa, 5 GPa and 10
GPa shown in Fig. 8, we find that there is an electron pocket of the
conductance band around K dropping to the Fermi level quickly under pressure.
And when the applied pressure is as large as 10 GPa, this pocket goes across
the Fermi level, which leads $P6_{3}/mmc$ NaCaBi to be a metal. As shown in
Fig. 11(a), we can find the lattice parameters a(= b) and c decrease under
pressure. Moreover, the lattice parameters a/c decrease about 1%/1.3% at 1
GPa, from which the $P6_{3}/mmc$ phase of NaCaBi becomes preferred. It should
also be noted that though the $P6_{3}/mmc$ NaCaBi changes from an insulator to
a metal from 0 GPa to 10 GPa, the inverted direct gap is always kept. Thus,
the STI nature with topological surface states is kept up to 10 GPa.

Looking along the $c$ axis, the $P6_{3}/mmc$ NaCaBi is a layered hexagonal
structure with its layer lying in the xy plane. Thus, we can introduce
substrates perpendicular to the layer plane. As shown in Table 7, we have
introduced 31 substrates with the lattice mismatch less than 1% along the $x$
and $y$ axes to assist growth teams attempting to synthesize the $P6_{3}/mmc$
phase of NaCaBi. Some commonly used crystals such as KTiO3 and BaNiO3 only
have lattice mismatch with NaCaBi of about -0.1% and 0.3%, which are very
small and can be good substrate candidates. However, it should be noted that,
as theoreticians, our proposal is very rough and more complicated experimental
details should be considered before real experiments.

Similar with applying pressure, imposing various strains are also considered
as convenient methods to tune the electronic properties in the condensed
systems. Here we focus on applying biaxial linear strain along $a$ and $b$
axes which keeps the symmetries of this system unchanged. From Fig. 11(b), we
find the strain energy of this kind of biaxial linear strain increase
parabolically with $-5\%\leq\varepsilon\leq 5\%$, which indicates this kind of
strain can be seen as elastic strain in a very large range. Thus, it offers
the experimental team large degree of freedom to choose potential substrates
candidates.

Table 7:  31 substrate candidates with the lattice mismatch less than 1% with
the $P6_{3}/mmc$ phase of NaCaBi.

Formula | No-MP | No-ICSD |  Band gap(eV) | a(Å) |  Mismatch($\epsilon$)
---|---|---|---|---|---
KAl(MoO4)2 | mp-19352 | 28018 | 3.890 | 5.545 | -0.4%
AlTl(MoO4)2 | mp-18733 | 250339 | 3.871 | 5.544 | -0.4%
CsAl(MoO4)2 | mp-505784 | 280947 | 3.879 | 5.551 | -0.3%
RbFe(MoO4)2 | mp-563010 | 245666 | 2.572 | 5.596 | 0.5%
HfPd3 | mp-11453 | 638769, 104254 | 0 | 5.595 | 0.5%
KTiO3 | mp-1180658 | 94775 | 0 | 5.560 | -0.1%
KAg2 | mp-12735 | 150142 | 0 | 5.589 | 0.4%
Na2LiAu3 | mp-12815 | 152090 | 0 | 5.530 | -0.6%
BaNiO3 | mp-19138 | 175, 30661 | 1.542 | 5.580 | 0.3%
Ce2In | mp-19733 | 621365, 621356, 102186 | 0 | 5.557 | -0.2%
Sm2In | mp-19816 | 59527, 59526, 640547, 640544 | 0 | 5.549 | -0.3%
Pr2In | mp-19854 | 640268, 108555 | 0 | 5.558 | -0.1%
Nd2In | mp-21295 | 59423, 59422, 59421, 640067 | 0 | 5.589 | 0.4%
CaAl12O19 | mp-28234 | 34394 | 4.320 | 5.564 |  $\approx$ 0%
Rb2Te | mp-383 |  55157, 55152, 55160, 55154$\cdots$ | 1.372 | 5.574 | 0.1%
In2Pt3 | mp-510439 | 640295, 59498, 640287 | 0 | 5.575 | 0.2%
SmOs2 | mp-570007 | 150521 | 0 | 5.574 | 0.1%
TaPd3 | mp-582360 | 648968 | 0 | 5.520 | -0.8%
PF5 | mp-8511 | 62554 | 7.109 | 5.563 |  $\approx$0%
Ba3BPO3 | mp-9712 | 402017 | 1.471 | 5.502 | -1.1%
Ba3BAsO3 | mp-9793 | 402682 | 1.529 | 5.528 | -0.7%
LaAl2Ag3 | mp-16766 | 57329 | 0 | 5.565 |  $\approx$0%
Na3OsO5 | mp-555476 | 416999 | 0.113 | 5.553 | -0.2%
Li2Ta2(OF2)3 | mp-561011 | 405777 | 3.835 | 5.581 | 0.3%
Sr2MgH6 | mp-644225 | 88205 | 2.758 | 5.546 | -0.4%
LaBPt2 | mp-31052 | 98425 | 0 | 5.522 | -0.8%
LaB2Ir3 | mp-10112 | 44422 | 0 | 5.543 | -0.4%
BaPd5 | mp-2606 | 58672, 616030 | 0 | 5.540 | -0.5%
NaBPt3 | mp-28614 | 68092 | 0 | 5.547 | -0.3%
CaB2Rh3 | mp-28705 | 66767 | 0 | 5.551 | -0.3%
SrZn5 | mp-638 | 106114, 418615 | 0 | 5.541 | -0.4%

  * 1

1\. No-MP column denotes the materials ID recorded in the Materials Project,
while No-ICSD column denotes the materials ID recorded in the ICSD.

  * 2

2\. $\epsilon>0$ denotes the lattice parameter a of the substrate candidate is
larger than that of $P6_{3}/mmc$ NaCaBi, while $\epsilon<0$ denotes the
lattice parameter a of the substrate candidate is smaller than that of
$P6_{3}/mmc$ NaCaBi.

## References

  * (1) Kane, C. L. & Mele, E. J.  Quantum Spin Hall Effect in Graphene.  _Phys. Rev. Lett._ 95, 226801 (2005).
  * (2) Zhang, H. _et al._ Topological insulators in Bi2Se3, Bi2Te3 and Sb2Te3 with a single Dirac cone on the surface.  _Nat. Phys._ 5, 438--442 (2009).
  * (3) Hsieh, D. _et al._ A tunable topological insulator in the spin helical Dirac transport regime.  _Nature_ 460, 1101--1105 (2009).
  * (4) Xia, Y. _et al._ Observation of a large-gap topological-insulator class with a single Dirac cone on the surface.  _Nat. Phys._ 5, 398 (2009).
  * (5) Chen, Y. L. _et al._ Experimental Realization of a Three-Dimensional Topological Insulator, Bi2Te3.  _Science_ 325, 178 (2009).
  * (6) Fu, L.  Topological Crystalline Insulators.  _Phys. Rev. Lett._ 106, 106802 (2011).
  * (7) Jadaun, P., Xiao, D., Niu, Q. & Banerjee, S. K.  Topological classification of crystalline insulators with space group symmetry.  _Phys. Rev. B_ 88, 085110 (2013).
  * (8) Shiozaki, K. & Sato, M.  Topology of crystalline insulators and superconductors.  _Phys. Rev. B_ 90, 165114 (2014).
  * (9) Wang, Z., Alexandradinata, A., Cava, R. J. & Bernevig, B. A.  Hourglass Fermions.  _Nature_ 532, 189--194 (2016).
  * (10) Ma, J. _et al._ Experimental evidence of hourglass fermion in the candidate nonsymmorphic topological insulator KHgSb.  _Sci. Adv._ 3, e1602415 (2017).
  * (11) Fu, L. & Kane, C. L.  Topological insulators with inversion symmetry.  _Phys. Rev. B_ 76, 045302 (2007).
  * (12) Wang, Z., Wieder, B. J., Li, J., Yan, B. & Bernevig, B. A.  Higher-Order Topology, Monopole Nodal Lines, and the Origin of Large Fermi Arcs in Transition Metal Dichalcogenides $X{\mathrm{Te}}_{2}$ ($X=\mathrm{Mo},\mathrm{W}$).  _Phys. Rev. Lett._ 123, 186401 (2019).
  * (13) Bradlyn, B. _et al._ Band connectivity for topological quantum chemistry: Band structures as a graph theory problem.  _Phys. Rev. B_ 97, 035138 (2018).
  * (14) Bradlyn, B., Wang, Z., Cano, J. & Bernevig, B. A.  Disconnected elementary band representations, fragile topology, and Wilson loops as topological indices: An example on the triangular lattice.  _Phys. Rev. B_ 99, 045140 (2019).
  * (15) Po, H. C., Vishwanath, A. & Watanabe, H.  Symmetry-based Indicators of Band Topology in the 230 Space Groups.  _Nat. Commun._ 8, 50 (2017).
  * (16) Song, Z., Zhang, T., Fang, Z. & Fang, C.  Quantitative mappings between symmetry and topology in solids.  _Nat. Commun._ 9, 3530 (2018).
  * (17) Bradlyn, B. _et al._ Topological quantum chemistry.  _Nature_ 547, 298--305 (2017).
  * (18) Zhang, T. _et al._ Catalogue of topological electronic materials.  _Nature_ 566, 475 (2019).
  * (19) Tang, F., Po, H. C., Vishwanath, A. & Wan, X.  Comprehensive search for topological materials using symmetry indicators.  _Nature_ 566, 486 (2019).
  * (20) Vergniory, M. G. _et al._ A complete catalogue of high-quality topological materials.  _Nature_ 566, 480--485 (2019).
  * (21) Hasan, M. Z. & Kane, C. L.  Colloquium : Topological Insulators.  _Rev. Mod. Phys._ 82, 3045--3067 (2010).
  * (22) Qi, X.-L. & Zhang, S.-C.  Topological insulators and superconductors.  _Rev. Mod. Phys._ 83, 1057--1110 (2011).
  * (23) Fu, L. & Kane, C. L.  Superconducting Proximity Effect and Majorana Fermions at the Surface of a Topological Insulator.  _Phys. Rev. Lett._ 100, 096407 (2008).
  * (24) Yu, R. _et al._ Quantized Anomalous Hall Effect in Magnetic Topological Insulators.  _Science_ 329, 61 (2010).
  * (25) Chang, C.-Z. _et al._ Quantized Anomalous Hall Effect in Magnetic Topological Insulators.  _Science_ 340, 167 (2013).
  * (26) Li, J. _et al._ Intrinsic magnetic topological insulators in van der Waals layered MnBi2Te4-family materials.  _Sci. Adv._ 5, eaaw5685 (2019).
  * (27) Ge, J. _et al._ High-Chern-Number and High-Temperature Quantum Hall Effect without Landau Levels.  _Natl. Sci. Rev._ 7, 1280 (2020).
  * (28) Hor, Y. S. _et al._ Superconductivity in ${\mathrm{Cu}}_{x}{\mathrm{Bi}}_{2}{\mathrm{Se}}_{3}$ and its Implications for Pairing in the Undoped Topological Insulator.  _Phys. Rev. Lett._ 104, 057001 (2010).
  * (29) Wray, L. A. _et al._ Observation of topological order in a superconducting doped topological insulator.  _Nat. Phys._ 6, 855--859 (2010).
  * (30) Xu, J.-P. _et al._ Experimental Detection of a Majorana Mode in the core of a Magnetic Vortex inside a Topological Insulator-Superconductor ${\mathrm{Bi}}_{2}{\mathrm{Te}}_{3}/{\mathrm{NbSe}}_{2}$ Heterostructure.  _Phys. Rev. Lett._ 114, 017001 (2015).
  * (31) Wu, X., Qin, S., Liang, Y., Fan, H. & Hu, J.  Topological characters in $\mathrm{Fe}({\mathrm{Te}}_{1-x}{\mathrm{Se}}_{x})$ thin films.  _Phys. Rev. B_ 93, 115129 (2016).
  * (32) Nie, S. _et al._ Topological phases in the ${\mathrm{TaSe}}_{3}$ compound.  _Phys. Rev. B_ 98, 125143 (2018).
  * (33) Oganov, A. R. & Glass, C. W.  Crystal structure prediction using ab initio evolutionary techniques: Principles and applications.  _J. Chem. Phys._ 124, 244704 (2006).
  * (34) Oganov, A. R., Lyakhov, A. O. & Valle, M.  How Evolutionary Crystal Structure Prediction Works-and Why.  _Acc. Chem. Res._ 44, 227--237 (2011).
  * (35) Lyakhov, A. O., Oganov, A. R., Stokes, H. T. & Zhu, Q.  New Developments in Evolutionary Structure Prediction Algorithm USPEX.  _Comput. Phys. Commun._ 184, 1172 (2013).
  * (36) Xia, K. _et al._ A novel superhard tungsten nitride predicted by machine-learning accelerated crystal structure search.  _Sci. Bull._ 63, 817 (2018).
  * (37) Zhang, X., Yu, L., Zakutayev, A. & Zunger, A.  Sorting Stable versus Unstable Hypothetical Compounds: The Case of Multi-Functional ABX Half-Heusler Filled Tetrahedral Structures.  _Adv. Funct. Mater._ 22, 1425 (2012).
  * (38) Peng, B., Yue, C., Zhang, H., Fang, Z. & Weng, H.  Predicting Dirac semimetals based on sodium ternary compounds.  _npj Comput. Mater._ 4, 68 (2018).
  * (39) Levy, N. _et al._ Strain-Induced Pseudo-Magnetic Fields Greater Than 300 Tesla in Graphene Nanobubbles.  _Science_ 329, 544--547 (2010).
  * (40) Shao, D. _et al._ Strain-induced quantum topological phase transitions in ${\mathrm{Na}}_{3}\mathrm{Bi}$.  _Phys. Rev. B_ 96, 075112 (2017).
  * (41) Gao, J., Wu, Q., Persson, C. & Wang, Z.  Irvsp: To obtain irreducible representations of electronic states in the VASP.  _Comput. Phys. Commun._ 261, 107760 (2021).
  * (42) Perdew, J. P., Burke, K. & Ernzerhof, M.  Generalized Gradient Approximation Made Simple.  _Phys. Rev. Lett._ 77, 3865--3868 (1996).
  * (43) Heyd, J., Scuseria, G. E. & Ernzerhof, M.  Erratum: "hybrid functionals based on a screened coulomb potential" [j. chem. phys. 118, 8207 (2003)].  _J. Chem. Phys._ 124, 219906 (2006).
  * (44) Sancho, M. P. L., Sancho, J. M. L. & Rubio, J.  Quick iterative scheme for the calculation of transfer matrices: application to Mo (100).  _J. Phys. F:Met. Phys._ 14, 1205 (1984).
  * (45) Sancho, M. P. L., Sancho, J. M. L., Sancho, J. M. L. & Rubio, J.  Highly convergent schemes for the calculation of bulk and surface Green functions.  _J. Phys. F:Met. Phys._ 15, 851 (1985).
  * (46) Wu, Q., Zhang, S., Song, H.-F., Troyer, M. & Soluyanov, A. A.  Wanniertools: An open-source software package for novel topological materials.  _Comput. Phys. Commun._ 224, 405 (2018).
  * (47) Winkler, R.  Spin--Orbit Coupling Effects in Two-Dimensional Electron and Hole Systems.  _(Springer Tracts in Modern Physics, Vol. 191, Springer, 2003)_ (2003).
  * (48) Fu, L. & Berg, E.  Odd-Parity Topological Superconductors: Theory and Application to ${\mathrm{Cu}}_{x}{\mathrm{Bi}}_{2}{\mathrm{Se}}_{3}$.  _Phys. Rev. Lett._ 105, 097001 (2010).
  * (49) Fu, L.  Odd-Parity Topological Superconductors: Theory and Application to ${\mathrm{Cu}}_{x}{\mathrm{Bi}}_{2}{\mathrm{Se}}_{3}$.  _Phys. Rev. B_ 90, 100509 (2014).
  * (50) Sasaki, S. _et al._ Topological Superconductivity in ${\mathrm{Cu}}_{x}{\mathrm{Bi}}_{2}{\mathrm{Se}}_{3}$.  _Phys. Rev. Lett._ 107, 217001 (2011).
  * (51) Kirzhner, T., Lahoud, E., Chaska, K. B., Salman, Z. & Kanigel, A.  Point-contact spectroscopy of Cu0.2Bi2Se3 single crystals.  _Phys. Rev. B_ 86, 064517 (2012).
  * (52) Bay, T. V. _et al._ Superconductivity in the Doped Topological Insulator ${\mathrm{Cu}}_{x}{\mathrm{Bi}}_{2}{\mathrm{Se}}_{3}$ under High Pressure.  _Phys. Rev. Lett._ 108, 057001 (2012).
  * (53) Levy, N. _et al._ Experimental Evidence for $s$-Wave Pairing Symmetry in Superconducting ${\mathrm{Cu}}_{x}{\mathrm{Bi}}_{2}{\mathrm{Se}}_{3}$ Single Crystals Using a Scanning Tunneling Microscope.  _Phys. Rev. Lett._ 110, 117001 (2013).
  * (54) Matano, K., Kriener, M., Segawa, K., Ando, Y. & Zheng, G.-q.  Spin-rotation symmetry breaking in the superconducting state of CuxBi2Se3.  _Nat. Phys._ 12, 852 (2016).
  * (55) Allen, P. B. & Dynes, R. C.  Transition temperature of strong-coupled superconductors reanalyzed.  _Phys. Rev. B_ 12, 905--922 (1975).
  * (56) Kresse, G. & Joubert, D.  From ultrasoft pseudopotentials to the projector augmented-wave method.  _Phys. Rev. B_ 59, 1758--1775 (1999).
  * (57) Monkhorst, H. J. & Pack, J. D.  Special points for Brillouin-zone integrations.  _Phys. Rev. B_ 13, 5188--5192 (1976).
  * (58) Togo, A. & Tanaka, I.  First principles phonon calculations in materials science.  _Scr. Mater._ 108, 1 (2015).
  * (59) Giannozzi, P. _et al._ QUANTUM ESPRESSO: a modular and open-source software project for quantum simulations of materials.  _J. Phys. Condens. Matter_ 21, 395502 (2009).
  * (60) Dong, X. & Fan, C.  Rich stoichiometries of stable Ca-Bi system: Structure prediction and superconductivity.  _Sci. Rep._ 5, 9326 (2015).
  * (61) Cheng, X., Li, R., Li, D., Li, Y. & Chen, X.-Q.  Stable compositions and structures in the Na–Bi system.  _Phys. Chem. Chem. Phys._ 17, 6933--6947 (2015).
  * (62) Le, C. _et al._ Three-dimensional topological critical Dirac semimetal in $A\mathrm{MgBi}\phantom{\rule{1.60004pt}{0.0pt}}(A=$ K, Rb, Cs).  _Phys. Rev. B_ 96, 115121 (2017).
  * (63) Jain, A., Ong, S. P., Hautier, G. & Wei, C.  Commentary: The Materials Project: A materials genome approach to accelerating materials innovation.  _APL Mater._ 1, 011002 (2013).
  * (64) Hellenbrandt, M.  The Inorganic Crystal Structure Database (ICSD) Present and Future.  _Crystallogr. Rev._ 10, 17--22 (2004).
  * (65) Wang, Z. _et al._ Dirac semimetal and topological phase transitions in ${A}_{3}$Bi ($A=\text{Na}$, K, Rb).  _Phys. Rev. B_ 85, 195320 (2012).