A note on decomposing graphs to locally almost irregular subgraphs

Jakub Przybyło

Applied Mathematics and Computation, 2024, vol. 470, issue C

Abstract: We consider a concept related with decompositions of graphs to locally irregular subgraphs and the notion of almost irregular subgraphs, introduced recently by Alon and Wei. We say that a graph is locally almost irregular if its every vertex has at most one neighbour with the same degree as itself. We conjecture that any graph can be edge decomposed to two locally almost irregular subgraphs, and we prove a relaxation of this supposition, where we admit for every vertex v more than one, yet finitely bounded number of neighbours with the same degree as v. In particular we show it suffices to allow 7 such neighbours in the case of regular graph, and no more than 48 in general.

Keywords: Locally almost irregular graph; Graph decomposition; Edge set partition; Locally irregular graph (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300324000560
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:470:y:2024:i:c:s0096300324000560

DOI: 10.1016/j.amc.2024.128584

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().