There is no going back: Properties of the non-backtracking Laplacian

Raffaella Mulas; Dong Zhang; Giulio Zucal

doi:10.1016/j.laa.2023.10.014

There is no going back: Properties of the non-backtracking Laplacian

Raffaella Mulas^*
, Dong Zhang
, Giulio Zucal

^*Corresponding author for this work

Mathematics

Research output: Contribution to Journal › Article › Academic › peer-review

Abstract

We prove new properties of the non-backtracking graph and the non-backtracking Laplacian for graphs. In particular, among other results, we prove that two simple graphs are isomorphic if and only if their corresponding non-backtracking graphs are isomorphic, and we investigate properties of various classes of non-backtracking Laplacian eigenfunctions, such as symmetric and antisymmetric eigenfunctions. Moreover, we introduce and study circularly partite graphs as a generalization of bipartite graphs, and we use this notion to state a sharp upper bound for the spectral gap from 1. We also investigate the singular values of the non-backtracking Laplacian in relation to independence numbers, and we use them to bound the moduli of the eigenvalues.

Original language	English
Pages (from-to)	341-370
Number of pages	30
Journal	Linear Algebra and its Applications
Volume	680
Early online date	20 Oct 2023
DOIs	https://doi.org/10.1016/j.laa.2023.10.014
Publication status	Published - 1 Jan 2024

Bibliographical note

Funding Information:
In 2022, Raffaella Mulas and Leo Torres gave a course on non-backtracking operators of graphs at the Max Planck Institute for Mathematics in the Sciences. As part of the course material, and as a follow-up to their first joint article, they prepared a list of open questions on the non-backtracking Laplacian that led to many discussions and exchanging of ideas with some of the course attendees, and eventually to this paper. As such, we would particularly like to express our gratitude to Leo Torres for his indirect contribution to this work. We would also like to thank Florentin Münch, Jiaxi Nie and, in particular, Janis Keck for the helpful comments and interesting discussions. Last (and least), we are grateful to Conor Finn for helping us choosing a suggestive title which we hope will not be rejected.

Publisher Copyright:
© 2023 The Author(s)

Funding

In 2022, Raffaella Mulas and Leo Torres gave a course on non-backtracking operators of graphs at the Max Planck Institute for Mathematics in the Sciences. As part of the course material, and as a follow-up to their first joint article, they prepared a list of open questions on the non-backtracking Laplacian that led to many discussions and exchanging of ideas with some of the course attendees, and eventually to this paper. As such, we would particularly like to express our gratitude to Leo Torres for his indirect contribution to this work. We would also like to thank Florentin Münch, Jiaxi Nie and, in particular, Janis Keck for the helpful comments and interesting discussions. Last (and least), we are grateful to Conor Finn for helping us choosing a suggestive title which we hope will not be rejected.

Keywords

Eigenfunctions
Eigenvalues
Non-backtracking graph
Non-backtracking Laplacian
Singular values

Access to Document

10.1016/j.laa.2023.10.014

Persistent URL (handle)

Persistent link

Cite this

@article{07dbc451fdfd4779a21141386f4a1ac5,

title = "There is no going back: Properties of the non-backtracking Laplacian",

abstract = "We prove new properties of the non-backtracking graph and the non-backtracking Laplacian for graphs. In particular, among other results, we prove that two simple graphs are isomorphic if and only if their corresponding non-backtracking graphs are isomorphic, and we investigate properties of various classes of non-backtracking Laplacian eigenfunctions, such as symmetric and antisymmetric eigenfunctions. Moreover, we introduce and study circularly partite graphs as a generalization of bipartite graphs, and we use this notion to state a sharp upper bound for the spectral gap from 1. We also investigate the singular values of the non-backtracking Laplacian in relation to independence numbers, and we use them to bound the moduli of the eigenvalues.",

keywords = "Eigenfunctions, Eigenvalues, Non-backtracking graph, Non-backtracking Laplacian, Singular values",

author = "Raffaella Mulas and Dong Zhang and Giulio Zucal",

note = "Funding Information: In 2022, Raffaella Mulas and Leo Torres gave a course on non-backtracking operators of graphs at the Max Planck Institute for Mathematics in the Sciences. As part of the course material, and as a follow-up to their first joint article, they prepared a list of open questions on the non-backtracking Laplacian that led to many discussions and exchanging of ideas with some of the course attendees, and eventually to this paper. As such, we would particularly like to express our gratitude to Leo Torres for his indirect contribution to this work. We would also like to thank Florentin M{\"u}nch, Jiaxi Nie and, in particular, Janis Keck for the helpful comments and interesting discussions. Last (and least), we are grateful to Conor Finn for helping us choosing a suggestive title which we hope will not be rejected. Publisher Copyright: {\textcopyright} 2023 The Author(s)",

year = "2024",

month = jan,

day = "1",

doi = "10.1016/j.laa.2023.10.014",

language = "English",

volume = "680",

pages = "341--370",

journal = "Linear Algebra and its Applications",

issn = "0024-3795",

publisher = "Elsevier Inc.",

}

TY - JOUR

T1 - There is no going back

T2 - Properties of the non-backtracking Laplacian

AU - Mulas, Raffaella

AU - Zhang, Dong

AU - Zucal, Giulio

N1 - Funding Information: In 2022, Raffaella Mulas and Leo Torres gave a course on non-backtracking operators of graphs at the Max Planck Institute for Mathematics in the Sciences. As part of the course material, and as a follow-up to their first joint article, they prepared a list of open questions on the non-backtracking Laplacian that led to many discussions and exchanging of ideas with some of the course attendees, and eventually to this paper. As such, we would particularly like to express our gratitude to Leo Torres for his indirect contribution to this work. We would also like to thank Florentin Münch, Jiaxi Nie and, in particular, Janis Keck for the helpful comments and interesting discussions. Last (and least), we are grateful to Conor Finn for helping us choosing a suggestive title which we hope will not be rejected. Publisher Copyright: © 2023 The Author(s)

PY - 2024/1/1

Y1 - 2024/1/1

N2 - We prove new properties of the non-backtracking graph and the non-backtracking Laplacian for graphs. In particular, among other results, we prove that two simple graphs are isomorphic if and only if their corresponding non-backtracking graphs are isomorphic, and we investigate properties of various classes of non-backtracking Laplacian eigenfunctions, such as symmetric and antisymmetric eigenfunctions. Moreover, we introduce and study circularly partite graphs as a generalization of bipartite graphs, and we use this notion to state a sharp upper bound for the spectral gap from 1. We also investigate the singular values of the non-backtracking Laplacian in relation to independence numbers, and we use them to bound the moduli of the eigenvalues.

AB - We prove new properties of the non-backtracking graph and the non-backtracking Laplacian for graphs. In particular, among other results, we prove that two simple graphs are isomorphic if and only if their corresponding non-backtracking graphs are isomorphic, and we investigate properties of various classes of non-backtracking Laplacian eigenfunctions, such as symmetric and antisymmetric eigenfunctions. Moreover, we introduce and study circularly partite graphs as a generalization of bipartite graphs, and we use this notion to state a sharp upper bound for the spectral gap from 1. We also investigate the singular values of the non-backtracking Laplacian in relation to independence numbers, and we use them to bound the moduli of the eigenvalues.

KW - Eigenfunctions

KW - Eigenvalues

KW - Non-backtracking graph

KW - Non-backtracking Laplacian

KW - Singular values

UR - https://www.scopus.com/pages/publications/85174566080

UR - https://www.scopus.com/pages/publications/85174566080#tab=citedBy

U2 - 10.1016/j.laa.2023.10.014

DO - 10.1016/j.laa.2023.10.014

M3 - Article

AN - SCOPUS:85174566080

SN - 0024-3795

VL - 680

SP - 341

EP - 370

JO - Linear Algebra and its Applications

JF - Linear Algebra and its Applications

ER -

There is no going back: Properties of the non-backtracking Laplacian

Abstract

Bibliographical note

Funding

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this