20.500.12556/ReVIS-11692 Degree-balanced decompositions of cubic graphs Po stopnjah uravnotežene dekompozicije kubičnih grafov We show that every cubic graph on ▫$n$▫ vertices contains a spanning subgraph, in which the number of vertices of each degree deviates from ▫$\frac{n}{4}$▫ by at most ▫$\frac{1}{2}$▫, up to three exceptions. This resolves the conjecture of Alon and Wei ({\em Irregular subgraphs, Combin. Probab. Comput. 32(2) (2023), 269--283}) for cubic graphs. Pokažemo, da vsak kubični graf z ▫$n$▫ vozlišči vsebuje vpet podgraf, v katerem število vozlišč vsake stopnje odstopa od ▫$\frac{n}{4}$▫ za največ ▫$\frac{1}{2}$▫, razen pri treh izjemah. S tem rešimo domnevo Alona in Wei ({\em Irregular subgraphs, Combin. Probab. Comput. 32(2) (2023), 269--283}) za kubične grafe. irregular subgraph repeated degrees degree-balanced decomposition neregularen podgraf ponavljajoče stopnje po stopnjah uravnotežena dekompozicija true true true Angleški jezik Slovenski jezik Neznano 2025-05-23 10:22:00 2025-05-23 10:22:00 2025-05-24 03:05:11 0000-00-00 00:00:00 2025 0 0 Naslov z nasl. zaslona; Opis vira z dne 23. 5. 2025; str. 1-10 art. no. ǂ104169 Vol. 128 2025 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 2024-08-28 2025-04-25 519.17 1095-9971 236916739 10.1016/j.ejc.2025.104169 RAZ_Luzar_Borut_2025.pdf RAZ_Luzar_Borut_2025.pdf 1 A8402C71668AFEEE4271984B3F6B3C9A dc61cc38704e7ae35d1d88a8999c9517919fd40ef2ac33610f270ef4af130c7b ee9b986a-37b0-11f0-963a-001a4af901a5 https://revis.openscience.si/Dokument.php?lang=slv&id=13496 Fakulteta za informacijske študije v Novem mestu 0 0 0