Matching number, Hamiltonian graphs and magnetic Laplacian matrices

John Stewart Fabila-Carrasco; Fernando Lledó; Olaf Post

doi:10.1016/j.laa.2022.02.006

Matching number, Hamiltonian graphs and magnetic Laplacian matrices

John Stewart Fabila-Carrasco, Fernando Lledó^*, Olaf Post

^*Corresponding author for this work

School of Engineering

Research output: Contribution to journal › Article › peer-review

Abstract

In this article, we relate the spectrum of the discrete magnetic Laplacian (DML) on a finite simple graph with two structural properties of the graph: the existence of a perfect matching and the existence of a Hamiltonian cycle of the underlying graph. In particular, we give a family of spectral obstructions parametrised by the magnetic potential for the graph to be matchable (i.e., having a perfect matching) or for the existence of a Hamiltonian cycle. We base our analysis on a special case of the spectral preorder introduced in [8], and we use the magnetic potential as a spectral control parameter.

Original language	English
Pages (from-to)	86-100
Number of pages	15
Journal	Linear algebra and its applications
Volume	642
Early online date	9 Feb 2022
DOIs	https://doi.org/10.1016/j.laa.2022.02.006
Publication status	Published - 1 Jun 2022

Keywords

Discrete magnetic Laplacian
Hamiltonian graph
Matching number
Spectral graph theory

Access to Document

10.1016/j.laa.2022.02.006

https://arxiv.org/abs/2010.08828Licence: Other

Cite this

@article{6bc30563cf9a4662a52576edef2da087,

title = "Matching number, Hamiltonian graphs and magnetic Laplacian matrices",

abstract = "In this article, we relate the spectrum of the discrete magnetic Laplacian (DML) on a finite simple graph with two structural properties of the graph: the existence of a perfect matching and the existence of a Hamiltonian cycle of the underlying graph. In particular, we give a family of spectral obstructions parametrised by the magnetic potential for the graph to be matchable (i.e., having a perfect matching) or for the existence of a Hamiltonian cycle. We base our analysis on a special case of the spectral preorder introduced in [8], and we use the magnetic potential as a spectral control parameter.",

keywords = "Discrete magnetic Laplacian, Hamiltonian graph, Matching number, Spectral graph theory",

author = "Fabila-Carrasco, {John Stewart} and Fernando Lled{\'o} and Olaf Post",

note = "Funding Information: JSFC and FLl were supported by Spanish Ministry of Economy and Competitiveness through project DGI MTM2017-84098-P , from the Severo Ochoa Programme for Centres of Excellence in R&D and from the Spanish National Research Council , through the Ayuda extraordinaria a Centros de Excelencia Severo Ochoa ( CEX2019-000904-S ). Publisher Copyright: {\textcopyright} 2022 Elsevier Inc.",

year = "2022",

month = jun,

day = "1",

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

language = "English",

volume = "642",

pages = "86--100",

journal = "Linear algebra and its applications",

issn = "0024-3795",

publisher = "Elsevier Inc.",

}

TY - JOUR

T1 - Matching number, Hamiltonian graphs and magnetic Laplacian matrices

AU - Fabila-Carrasco, John Stewart

AU - Lledó, Fernando

AU - Post, Olaf

N1 - Funding Information: JSFC and FLl were supported by Spanish Ministry of Economy and Competitiveness through project DGI MTM2017-84098-P , from the Severo Ochoa Programme for Centres of Excellence in R&D and from the Spanish National Research Council , through the Ayuda extraordinaria a Centros de Excelencia Severo Ochoa ( CEX2019-000904-S ). Publisher Copyright: © 2022 Elsevier Inc.

PY - 2022/6/1

Y1 - 2022/6/1

N2 - In this article, we relate the spectrum of the discrete magnetic Laplacian (DML) on a finite simple graph with two structural properties of the graph: the existence of a perfect matching and the existence of a Hamiltonian cycle of the underlying graph. In particular, we give a family of spectral obstructions parametrised by the magnetic potential for the graph to be matchable (i.e., having a perfect matching) or for the existence of a Hamiltonian cycle. We base our analysis on a special case of the spectral preorder introduced in [8], and we use the magnetic potential as a spectral control parameter.

AB - In this article, we relate the spectrum of the discrete magnetic Laplacian (DML) on a finite simple graph with two structural properties of the graph: the existence of a perfect matching and the existence of a Hamiltonian cycle of the underlying graph. In particular, we give a family of spectral obstructions parametrised by the magnetic potential for the graph to be matchable (i.e., having a perfect matching) or for the existence of a Hamiltonian cycle. We base our analysis on a special case of the spectral preorder introduced in [8], and we use the magnetic potential as a spectral control parameter.

KW - Discrete magnetic Laplacian

KW - Hamiltonian graph

KW - Matching number

KW - Spectral graph theory

UR - http://www.scopus.com/inward/record.url?scp=85124506003&partnerID=8YFLogxK

U2 - 10.1016/j.laa.2022.02.006

DO - 10.1016/j.laa.2022.02.006

M3 - Article

AN - SCOPUS:85124506003

VL - 642

SP - 86

EP - 100

JO - Linear algebra and its applications

JF - Linear algebra and its applications

SN - 0024-3795

ER -

Matching number, Hamiltonian graphs and magnetic Laplacian matrices

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this