Laplacian spectral characterization of roses

Changxiang He, Edwin van Dam

Research output: Contribution to journalArticleScientificpeer-review

Abstract

A rose graph is a graph consisting of cycles that all meet in one vertex. We show that except for two specific examples, these rose graphs are determined by the Laplacian spectrum, thus proving a conjecture posed by Liu and Huang (2013) [8]. We also show that if two rose graphs have a so-called universal Laplacian matrix with the same spectrum, then they must be isomorphic. In memory of Horst Sachs (1927–2016), we show the specific case of the latter result for the adjacency matrix by using Sachs' theorem and a new result on the number of matchings in the disjoint union of paths.
Original languageEnglish
Pages (from-to)19-30
JournalLinear Algebra and its Applications
Volume536
DOIs
Publication statusPublished - 1 Jan 2018

Fingerprint

Graph in graph theory
Laplacian Spectrum
Laplacian Matrix
Adjacency Matrix
Disjoint
Union
Isomorphic
Cycle
Path
Vertex of a graph
Theorem

Keywords

  • Rose graphs
  • Laplacian spectrum
  • Closed walks
  • Sachs' theorem
  • Matchings

Cite this

@article{0a498ef306b14d6a804ffe97d3402793,
title = "Laplacian spectral characterization of roses",
abstract = "A rose graph is a graph consisting of cycles that all meet in one vertex. We show that except for two specific examples, these rose graphs are determined by the Laplacian spectrum, thus proving a conjecture posed by Liu and Huang (2013) [8]. We also show that if two rose graphs have a so-called universal Laplacian matrix with the same spectrum, then they must be isomorphic. In memory of Horst Sachs (1927–2016), we show the specific case of the latter result for the adjacency matrix by using Sachs' theorem and a new result on the number of matchings in the disjoint union of paths.",
keywords = "Rose graphs, Laplacian spectrum, Closed walks, Sachs' theorem, Matchings",
author = "Changxiang He and {van Dam}, Edwin",
year = "2018",
month = "1",
day = "1",
doi = "10.1016/j.laa.2017.08.012",
language = "English",
volume = "536",
pages = "19--30",
journal = "Linear Algebra and its Applications",
issn = "0024-3795",
publisher = "Elsevier Inc.",

}

Laplacian spectral characterization of roses. / He, Changxiang; van Dam, Edwin.

In: Linear Algebra and its Applications, Vol. 536, 01.01.2018, p. 19-30.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Laplacian spectral characterization of roses

AU - He, Changxiang

AU - van Dam, Edwin

PY - 2018/1/1

Y1 - 2018/1/1

N2 - A rose graph is a graph consisting of cycles that all meet in one vertex. We show that except for two specific examples, these rose graphs are determined by the Laplacian spectrum, thus proving a conjecture posed by Liu and Huang (2013) [8]. We also show that if two rose graphs have a so-called universal Laplacian matrix with the same spectrum, then they must be isomorphic. In memory of Horst Sachs (1927–2016), we show the specific case of the latter result for the adjacency matrix by using Sachs' theorem and a new result on the number of matchings in the disjoint union of paths.

AB - A rose graph is a graph consisting of cycles that all meet in one vertex. We show that except for two specific examples, these rose graphs are determined by the Laplacian spectrum, thus proving a conjecture posed by Liu and Huang (2013) [8]. We also show that if two rose graphs have a so-called universal Laplacian matrix with the same spectrum, then they must be isomorphic. In memory of Horst Sachs (1927–2016), we show the specific case of the latter result for the adjacency matrix by using Sachs' theorem and a new result on the number of matchings in the disjoint union of paths.

KW - Rose graphs

KW - Laplacian spectrum

KW - Closed walks

KW - Sachs' theorem

KW - Matchings

U2 - 10.1016/j.laa.2017.08.012

DO - 10.1016/j.laa.2017.08.012

M3 - Article

VL - 536

SP - 19

EP - 30

JO - Linear Algebra and its Applications

JF - Linear Algebra and its Applications

SN - 0024-3795

ER -