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)

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic › peer review

134 Downloads (Pure)

Samenvatting

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.

Originele taal-2	Engels
Pagina's (van-tot)	30-51
Aantal pagina's	22
Tijdschrift	Linear Algebra and Its Applications
Volume	645
DOI's	https://doi.org/10.1016/j.laa.2022.03.003
Status	Gepubliceerd - 15 jul. 2022

Financiering

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.

Financiers	Financiernummer
Fonds Wetenschappelijk Onderzoek	1285921N

Toegang tot document

10.1016/j.laa.2022.03.003

pdfDefinitieve gepubliceerde versie, 482 KBLicentie: CC BY

Andere bestanden en links

Link naar publicatie in Scopus

Citeer dit

@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 - http://www.scopus.com/inward/record.url?scp=85126526884&partnerID=8YFLogxK

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

Samenvatting

Financiering

Toegang tot document

Andere bestanden en links

Vingerafdruk

Citeer dit