Characterizing and computing weight-equitable partitions of graphs

Aida Abiad Monge; Christopher Hojny; Sjanne Zeijlemaker

doi:10.1016/j.laa.2022.03.003

Characterizing and computing weight-equitable partitions of graphs

Aida Abiad Monge
, Christopher Hojny
, Sjanne Zeijlemaker (Corresponding author)

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

2 Citations (Scopus)

187 Downloads (Pure)

Abstract

Weight-equitable partitions of graphs, which are a natural extension of the well-known equitable partitions, have been shown to be a powerful tool to weaken the regularity assumption in several classic eigenvalue bounds. In this work we aim to further our algebraic and computational understanding of weight-equitable partitions. We do so by showing several spectral properties and algebraic characterizations, and by providing a method to find coarse weight-equitable partitions.

Original language	English
Pages (from-to)	30-51
Number of pages	22
Journal	Linear Algebra and Its Applications
Volume	645
DOIs	https://doi.org/10.1016/j.laa.2022.03.003
Publication status	Published - 15 Jul 2022

Funding

The research of the first author is partially supported by the FWO grant 1285921N . The authors are very grateful to an anonymous referee for pointing out the characterization and implications of cographs by twins from Lemma 23 and Theorem 24 , which simplified the previous proofs in Section 5.2 . We also thank Frits Spieksma for carefully reading the article.

Funders	Funder number
Fonds Wetenschappelijk Onderzoek	1285921N

Keywords

Cograph
Eigenvalue
Weight-equitable partition

Access to Document

10.1016/j.laa.2022.03.003

pdfFinal published version, 482 KBLicence: CC BY

Cite this

@article{b8ab87d6bfbb40cf80ab62c26f106e01,

title = "Characterizing and computing weight-equitable partitions of graphs",

abstract = "Weight-equitable partitions of graphs, which are a natural extension of the well-known equitable partitions, have been shown to be a powerful tool to weaken the regularity assumption in several classic eigenvalue bounds. In this work we aim to further our algebraic and computational understanding of weight-equitable partitions. We do so by showing several spectral properties and algebraic characterizations, and by providing a method to find coarse weight-equitable partitions.",

keywords = "Cograph, Eigenvalue, Weight-equitable partition",

author = "\{Abiad Monge\}, Aida and Christopher Hojny and Sjanne Zeijlemaker",

year = "2022",

month = jul,

day = "15",

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

language = "English",

volume = "645",

pages = "30--51",

journal = "Linear Algebra and Its Applications",

issn = "0024-3795",

publisher = "Elsevier",

}

TY - JOUR

T1 - Characterizing and computing weight-equitable partitions of graphs

AU - Abiad Monge, Aida

AU - Hojny, Christopher

AU - Zeijlemaker, Sjanne

PY - 2022/7/15

Y1 - 2022/7/15

N2 - Weight-equitable partitions of graphs, which are a natural extension of the well-known equitable partitions, have been shown to be a powerful tool to weaken the regularity assumption in several classic eigenvalue bounds. In this work we aim to further our algebraic and computational understanding of weight-equitable partitions. We do so by showing several spectral properties and algebraic characterizations, and by providing a method to find coarse weight-equitable partitions.

AB - Weight-equitable partitions of graphs, which are a natural extension of the well-known equitable partitions, have been shown to be a powerful tool to weaken the regularity assumption in several classic eigenvalue bounds. In this work we aim to further our algebraic and computational understanding of weight-equitable partitions. We do so by showing several spectral properties and algebraic characterizations, and by providing a method to find coarse weight-equitable partitions.

KW - Cograph

KW - Eigenvalue

KW - Weight-equitable partition

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

U2 - 10.1016/j.laa.2022.03.003

DO - 10.1016/j.laa.2022.03.003

M3 - Article

SN - 0024-3795

VL - 645

SP - 30

EP - 51

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

ER -

Characterizing and computing weight-equitable partitions of graphs

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this