Szczegóły publikacji
Opis bibliograficzny
A note on decomposing graphs to locally almost irregular subgraphs / Jakub PRZYBYŁO // Applied Mathematics and Computation ; ISSN 0096-3003. — 2024 — vol. 470 art. no. 128584, s. 1–6. — Bibliogr. s. 5–6, Abstr. — Publikacja dostępna online od: 2024-01-31
Autor
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 152161 |
|---|---|
| Data dodania do BaDAP | 2024-04-09 |
| Tekst źródłowy | URL |
| DOI | 10.1016/j.amc.2024.128584 |
| Rok publikacji | 2024 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Applied Mathematics and Computation |
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.