New results in vertex sedentariness

The concept of sedentariness was introduced by Godsil to study the ‘stay-at-home’ behaviour of vertices in families of graphs as their number of vertices tend to infinity [SedQW]. In particular, Godsil showed that complete graphs and large classes of strongly regular graphs are sedentary families. Recently, Monterde formalized the notion of a sedentary vertex and systematically studied both sedentary families and sedentary vertices [Monterde2023]. She proved that Cartesian products preserve vertex sedentariness, and provided examples of strongly cospectral vertices that are sedentary. She also showed that a vertex with at least two twins is sedentary and established lower bounds on their sedentariness. Her results allowed for the construction of new graphs with sedentary vertices using joins, blow-ups and attachment of pendent paths.

In this paper, we continue the investigation of vertex sedentariness. In Section 2, we introduce some graph theory, matrix theory and quantum walks background. Section 3 is devoted to a summary of known results about sedentariness that are useful throughout the paper. We highlight the fact that pretty good state transfer and sedentariness are mutually exclusive types of state transfer. We also provide infinite families of graphs containing vertices that are neither sedentary nor involved in pretty good state transfer (Example 3 and Remark 36). In Section 4, we prove an interesting result which states that a vertex with a twin only exhibits either sedentariness or pretty good state transfer (Corollary 12). This allows us to characterize twin vertices that are sedentary (Theorem 14) and provide an improved bound on their sedentariness (Theorem 15). We then apply our results to characterize pretty good state transfer and sedentariness in complete multipartite graphs in Section 5 and threshold graphs in Section 6. In particular, we show that a huge fraction of complete multipartite graphs are Laplacian sedentary at every vertex (Corollary 22). In fact, the only complete multipartite graphs that do not contain a Laplacian sedentary vertex are cocktail party graphs on twice an even number of vertices (Corollary 23). For threshold graphs, we characterize Laplacian sedentary vertices (Theorem 27), and provide tight lower bounds on sedentariness, which vary depending on the cell containing the vertex and the form of the threshold graph in question (Theorem 28). We also establish that almost all complete multipartite graphs and threshold graphs contain a sedentary vertex (Corollary 31). Section 7 explores sedentariness in direct products. We give sufficient conditions such that the direct product of a complete graph with another graph yields sedentary vertices (Theorem 32(1)). This yields new families of graphs with sedentary vertices, such as the direct product of complete graphs under mild conditions (Theorem 34). We also characterize sedentariness in bipartite doubles (Theorem 32(2)). In particular, we show that the bipartite double of a complete graph does not exhibit sedentariness (Corollary 35(1)). This prompts us to provide an infinite family of connected bipartite doubles containing sedentary vertices (Theorem 37). Section 8 is dedicated to characterizing adjacency sedentariness in blow-up graphs. Prior to this work, Monterde showed that the blow-ups of $m\geq 3$ copies of a graph are sedentary at every vertex. Here, we resolve the case $m=2$ (Corollary 41) and provide sharper bounds for sedentariness in blow-ups (Theorem 40). In Section 9, we prove that the join operation preserves adjacency and Laplacian sedentariness under mild conditions (Theorem 45). This provides yet another method for constructing new graphs with sedentary vertices. Finally, we present open questions in Section 10.

Throughout, we let $X$ be a weighted and undirected graph with possible loops, no multiple edges, all positive edge weights and vertex set $V(X)$. The adjacency matrix $A(X)$ of $X$ is defined entrywise as

where $\omega_{u,v}$ is the weight of the edge $(u,v)$. The degree matrix $D(X)$ of $X$ is the diagonal matrix of vertex degrees of $X$, where $\operatorname{deg}(u)=2\omega_{u,u}+\sum_{j\neq u}\omega_{u,j}$ for each $u\in V(X)$. For each $q\in\mathbb{R}$, we call the matrix $M_{q}(X)=qD(X)+A(X)$ a generalized adjacency matrix for $X$. Note that $M_{0}(X)=A(X)$ and $M_{-1}(X)=-L(X)$, where $L(X)$ is the Laplacian matrix of $X$. We say that $X$ is weighted $k$-regular if $\operatorname{deg}(u)-\omega_{u,u}$ is a constant $k$ for each $u\in V(X)$. Equivalently, each row sum of $A(X)$ is a constant $k$. If $X$ is simple (i.e., loopless), then $X$ is weighted $k$-regular if and only if $D(X)=kI$. If the context is clear, then we write $M_{q}(X)$, $A(X)$, and $L(X)$ resp. as $M_{q}$, $A$, and $L$. We also write $M_{q}$ as $M$ when $q$ is not needed. We represent the transpose of $M$ by $M^{T}$, and the characteristic polynomial of $M$ in the variable $t$ by $\phi(M,t)$. We denote the simple unweighted empty, complete, cycle and path graphs on $n$ vertices resp. by $O_{n}$, $K_{n}$, $C_{n}$ and $P_{n}$. The all-ones vector of order $n$, the zero vector of order $n$, the $m\times n$ all-ones matrix, and the $n\times n$ identity matrix are denoted by $\textbf{1}_{n}$, $\textbf{0}_{n}$, $\textbf{J}_{m,n}$ and $I_{n}$, respectively. If $m=n$, then we write $\textbf{J}_{m,n}$ as $\textbf{J}_{n}$. If the context is clear, then we simply write these matrices resp. as 1, 0, J and $I$.

Let $H$ be a Hermitian matrix whose rows and columns are indexed by the vertices of $X$ satisfying the property $H_{u,v}=0$ if and only if no edge exists between $u$ and $v$ in $X$. A (continuous-time) quantum walk on $X$ with respect to $H$ is determined by the unitary matrix

In this work, we focus on the case $H=M_{q}$. If $q$ is not important, then we simply write $U_{M_{q}}(t)$ as $U_{M}(t)$. Unless otherwise specified, the results in this paper apply to $M_{q}=M$ for all $q\in\mathbb{R}$ Since $M$ is real symmetric, it admits a spectral decomposition

where the $\lambda_{j}$’s are the distinct real eigenvalues of $M$ and each $E_{j}$ is the orthogonal projection matrix onto the eigenspace associated with $\lambda_{j}$. The eigenvalue support of $u\in V(X)$ is the set

$\sigma_{u}(M)=\{\lambda_{j}:E_{j}\textbf{e}_{u}\neq\textbf{0}\},$

where $\textbf{e}_{u}$ denotes the characteristic vector of vertex $u$. From (2), we may write (1) as

$U_{M}(t)=\sum_{j}e^{it\lambda_{j}}E_{j}$.

We say that two vertices $u$ and $v$ are cospectral if $(E_{j})_{u,u}=(E_{j})_{v,v}$ for each $j$, and strongly cospectral if $E_{j}\textbf{e}_{u}=\pm E_{j}\textbf{e}_{v}$ for each $j$. Note that if $u$ and $v$ are cospectral, then $U_{M}(t)_{u,u}=U_{M}(t)_{v,v}$ for all $t$.

With respect to the matrix $M$, we say that perfect state transfer (PST) occurs between two vertices $u$ and $v$ at time $\tau$ if $|U(\tau)_{u,v}|=1$. The minimum $\tau>0$ such that $|U(\tau)_{u,v}|=1$ is called the minimum PST time between $u$ and $v$. We say that $u$ is periodic at time $\tau$ if $|U(\tau)_{u,u}|=1$. The minimum $\tau>0$ such that $|U(\tau)_{u,u}|=1$ is called the minimum period of $u$, which we denote by $\rho$. We say that pretty good state transfer (PGST) occurs between $u$ and $v$ if $\lim_{\tau_{k}\rightarrow\infty}|U(\tau_{k})_{u,v}|=1$ for some $\{\tau_{k}\}\subseteq\mathbb{R}$. Further, if $X$ is a simple weighted $k$-regular graph, then $U_{M}(t)=e^{it(qkI+A)}=e^{it(qk)}U_{A}(t)$, and so for all $q\in\mathbb{R}$,

$\left|U_{M}(t)_{u,v}\right|^{2}=\left|U_{A}(t)_{u,v}\right|^{2}.$

holds for all $t$ and for all $u,v\in V(X)$. That is, the quantum walks with respect to $A$ and $M$ are equivalent for all $q\in\mathbb{R}$, i.e., they exhibit the same types of state transfer.

The join of weighted graphs $X$ and $Y$, denoted $X\vee Y$, is the resulting graph obtained by joining every vertex of $X$ with every vertex of $Y$ with an edge of weight one. In particular, the graph $O_{1}\vee Y$ is called a cone on $Y$ and the lone vertex of $O_{1}$ is called the apex. If $X\in\{O_{2},K_{2}\}$, then $X\vee Y$ is called a double cone on $Y$ and the two vertices of $X$ are called the apexes. We denote the cocktail party graph on $2k$ vertices by $CP(2k)$, and the complete graph on $n$ vertices minus an edge by $K_{n}\backslash e$.

In this section, we gather some known results on sedentariness that will be useful throughout the paper.

If $C$ is not important, then we respectively say sedentary, sharply sedentary, and tightly sedentary. Sedentariness of a vertex $u$ implies that $\lvert U_{M}(t)_{u,u}\rvert$ is bounded away from $0$, and so physically speaking, the quantum state initially at vertex $u$ tends to stay at $u$.

We now state an important property of sedentary vertices [Monterde2023, Proposition 2c].

Proposition 2 implies that sedentarines and PGST are mutually exclusive types of quantum state transfer, although it is possible that a given vertex in a graph exhibits neither sedentarines nor PGST. We illustrate the latter statement by providing an infinite family of graphs that satisfy this property.

In Remark 36, we provide an infinite family of graphs containing periodic and strongly cospectral vertices that are neither sedentary nor involved in PST with respect to the adjacency and Laplacian matrix.

The following result is due to Monterde [Monterde2023, Theorem 11].

We also have the following result, which characterizes the occurrence of (6). In what follows, we denote the largest power of two that divides an integer $a$ by $\nu_{2}(a)$.

We also state Lemmas 9 and 12 in [Monterde2023], respectively.

We close this section with a remark that Lemmas 6 and 9 are equivalent for periodic vertices.

Denote the neighbourhood of a vertex $u$ in $X$ by $N_{X}(u)$. Two vertices $u$ and $v$ of $X$ are twins if

1. 1.

   $N_{X}(u)\backslash\{u,v\}=N_{X}(v)\backslash\{u,v\}$,

2. 2.

   the edges $(u,w)$ and $(v,w)$ have the same weight for each $w\in N_{X}(u)\backslash\{u,v\}$, and

3. 3.

   the loops on $u$ and $v$ have the same weight, and this weight is zero if those loops are absent.

We allow twins to be adjacent. A maximal subset $T=T(\omega,\eta)$ of $V(X)$ with at least two elements is a twin set in $X$ if the vertices in $T$ are pairwise twins, each $u\in T$ has a loop of weight $\omega$, and every pair of vertices in $T$ are connected by an edge with weight $\eta$. In particular, if $X$ is a simple unweighted graph, then $\omega=0$ and $\eta\in\{0,1\}$. As an example, the apexes of a double cone form a twin set of size two. Note that the vertices in a twin set $T$ are pairwise cospectral [Monterde2022, Corollary 2.11]. Thus, if $u,v\in T$, then $U_{M}(t)_{u,u}=U_{M}(t)_{v,v}$ for all $t$, and so a vertex in $T$ is sedentary if and only if each vertex in $T$ is sedentary.

The following fact is due to Monterde [Monterde2022, Lemma 2.9].

Our next result is due to Kirkland et al. [Kirkland2023, Corollary 1].

Since strong cospectrality is a necessary condition for PGST, Corollary 12 yields the next result.

We now prove one of our main results, which characterizes sedentariness in twin vertices.

We now prove another main result in this paper, which is an improvement of [Monterde2023, Theorem 16].

Monterde first established Theorem 15(2) in [Monterde2023, Theorem 16], and she used this result provide infinite families of join graphs, blow-up graphs and graphs with tails that contain sedentary vertices. In the next examples, we provide infinite families of graphs that satisfy Theorem 15(3).

A complete bipartite graph $K_{n_{1},\ldots,n_{k}}$ is the graph $K_{n_{1},\ldots,n_{k}}=\bigvee_{j=1}^{k}O_{n_{j}}$. If $n_{\ell}=1$ (resp., $n_{\ell}=2$) for some $\ell\in\{1,\ldots,k\}$, then we may write $K_{n_{1},\ldots,n_{k}}=O_{1}\vee\bigvee_{j\neq\ell}O_{n_{j}}$ (resp., $K_{n_{1},\ldots,n_{k}}=O_{2}\vee\bigvee_{j\neq\ell}O_{n_{j}}$), and so we may view $K_{n_{1},\ldots,n_{k}}$ as a cone (resp., double cone) on $Y=\bigvee_{j\neq\ell}O_{n_{j}}$. Our goal in this section to characterize PGST and sedentariness in complete multipartite graphs with respect to $M\in\{A,L\}$.