Sedentary quantum walks on bipartite graphs

• URL: http://arxiv.org/abs/2601.18964v1
• Date: Mon, 26 Jan 2026 21:04:14 GMT
• Title: Sedentary quantum walks on bipartite graphs
• Authors: Karen Meagher, Hermie Monterde,
• Abstract summary: We prove that almost all planar graphs and almost all trees contain at least two sedentary vertices for any assignment of edge weights.<n>For weighted bipartite graphs, we show that a vertices is not sedentary whenever 0 does not belong to its eigenvalue support.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: If a quantum walk starting on a vertex tends to stay at home, then that vertex is said to be sedentary. We prove that almost all planar graphs and almost all trees contain at least two sedentary vertices for any assignment of edge weights -- a result that suggests vertex sedentariness is a common phenomenon in trees and planar graphs. For weighted bipartite graphs, we show that a vertex is not sedentary whenever 0 does not belong to its eigenvalue support. Consequently, each vertex in a nonsingular weighted bipartite graph is not sedentary, a stark contrast to weighted trees and weighted planar graphs. A corollary of this result is that every vertex in a bipartite graph with a unique perfect matching is not sedentary for any assignment of edge weights. We also construct new families of weighted bipartite graphs with sedentary vertices using the bipartite double and subdivision operations. Finally, we show that unweighted paths and unweighted even cycles contain no sedentary vertices.

Related papers

• New results in vertex sedentariness [0.0]
  We show that the direct product and join operations preserve the sedentary state of a graph. We also completely characterize sedentariness in blow-up graphs. As an application, we determine the conditions in which perfect state transfer, pretty good state transfer and sedentariness occur in complete bipartite graphs and threshold graphs of any order.
  arXiv  Detail & Related papers  (2023-12-31T01:22:06Z)
• Finding the Missing-half: Graph Complementary Learning for Homophily-prone and Heterophily-prone Graphs [48.79929516665371]
  Graphs with homophily-prone edges tend to connect nodes with the same class. Heterophily-prone edges tend to build relationships between nodes with different classes. Existing GNNs only take the original graph during training.
  arXiv  Detail & Related papers  (2023-06-13T08:06:10Z)
• Sedentariness in quantum walks [0.0]
  We prove that there are infinitely many graphs containing strongly cospectral vertices that are sedentary. We derive results about sedentariness in products of graphs which allow us to construct new sedentary families, such as Cartesian powers of complete graphs and stars.
  arXiv  Detail & Related papers  (2023-03-11T03:44:04Z)
• Graph Spectral Embedding using the Geodesic Betweeness Centrality [76.27138343125985]
  We introduce the Graph Sylvester Embedding (GSE), an unsupervised graph representation of local similarity, connectivity, and global structure. GSE uses the solution of the Sylvester equation to capture both network structure and neighborhood proximity in a single representation.
  arXiv  Detail & Related papers  (2022-05-07T04:11:23Z)
• Quantum walks do not like bridges [0.0]
  We consider graphs with two cut vertices joined by a path with one or two edges, and prove that there can be no quantum perfect state transfer between these, unless the graph has no other edges. We see our result as an intermediate step to broaden the understanding of how connectivity plays a key role in quantum walks.
  arXiv  Detail & Related papers  (2021-12-06T21:58:37Z)
• Edge but not Least: Cross-View Graph Pooling [76.71497833616024]
  This paper presents a cross-view graph pooling (Co-Pooling) method to better exploit crucial graph structure information. Through cross-view interaction, edge-view pooling and node-view pooling seamlessly reinforce each other to learn more informative graph-level representations.
  arXiv  Detail & Related papers  (2021-09-24T08:01:23Z)
• Laplacian State Transfer on Graphs with an Edge Perturbation Between Twin Vertices [0.0]
  We consider quantum state transfer relative to the Laplacian matrix of a graph. We investigate the existence of quantum state transfer between a pair of twin vertices in a graph when the edge between the vertices is perturbed.
  arXiv  Detail & Related papers  (2021-09-11T15:48:18Z)
• Spectral Embedding of Graph Networks [76.27138343125985]
  We introduce an unsupervised graph embedding that trades off local node similarity and connectivity, and global structure. The embedding is based on a generalized graph Laplacian, whose eigenvectors compactly capture both network structure and neighborhood proximity in a single representation.
  arXiv  Detail & Related papers  (2020-09-30T04:59:10Z)
• Hamiltonian systems, Toda lattices, Solitons, Lax Pairs on weighted Z-graded graphs [62.997667081978825]
  We identify conditions which allow one to lift one dimensional solutions to solutions on graphs. We show that even for a simple example of a topologically interesting graph the corresponding non-trivial Lax pairs and associated unitary transformations do not lift to a Lax pair on the Z-graded graph.
  arXiv  Detail & Related papers  (2020-08-11T17:58:13Z)
• Interpretable Deep Graph Generation with Node-Edge Co-Disentanglement [55.2456981313287]
  We propose a new disentanglement enhancement framework for deep generative models for attributed graphs. A novel variational objective is proposed to disentangle the above three types of latent factors, with novel architecture for node and edge deconvolutions. Within each type, individual-factor-wise disentanglement is further enhanced, which is shown to be a generalization of the existing framework for images.
  arXiv  Detail & Related papers  (2020-06-09T16:33:49Z)
• Search on Vertex-Transitive Graphs by Lackadaisical Quantum Walk [0.0]
  The lackadaisical quantum walk is a discrete-time, coined quantum walk on a graph. It can improve spatial search on the complete graph, discrete torus, cycle, and regular complete bipartite graph. We present a number of numerical simulations supporting this hypothesis.
  arXiv  Detail & Related papers  (2020-02-26T00:10:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.