Coverability of graphs by parity regular subgraphs

Petruševski, Mirko (avtor), Škrekovski, Riste (avtor)

A graph is even (resp. odd) if all its vertex degrees are even (resp. odd). We consider edge coverings by prescribed number of even and/or odd subgraphs. In view of the 8-Flow Theorem, a graph admits a covering by three even subgraphs if and only if it is bridgeless. Coverability by three odd subgraphs has been characterized recently [Petruševski, M.; Škrekovski, R. Coverability of graph by three odd subgraphs. J. Graph Theory 2019, 92, 304–321]. It is not hard to argue that every acyclic graph can be decomposed into two odd subgraphs, which implies that every graph admits a decomposition into two odd subgraphs and one even subgraph. Here, we prove that every 3-edge-connected graph is coverable by two even subgraphs and one odd subgraph. The result is sharp in terms of edge-connectivity. We also discuss coverability by more than three parity regular subgraphs, and prove that it can be efficiently decided whether a given instance of such covering exists. Moreover, we deduce here a polynomial time algorithm which determines whether a given set of edges extends to an odd subgraph. Finally, we share some thoughts on coverability by two subgraphs and conclude with two conjectures.

• Jezik: Angleški jezik
• Ključne besede: covering, even subgraph, odd subgraph, T-join, spanning tree
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Leto izida: 2021
• Št. strani: 15 str.
• Številčenje: Vol. 9, iss. 2, art. 182
• PID: 20.500.12556/RUL-134886
• UDK: 519.17
• ISSN pri članku: 2227-7390
• DOI: 10.3390/math9020182
• COBISS.SI-ID: 47971331
• Datum objave v RUL: 10.02.2022

Gradivo je del revije

• Naslov: Mathematics
• Skrajšan naslov: Mathematics
• Založnik: MDPI AG
• ISSN: 2227-7390
• COBISS.SI-ID: 523267865

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.
• Začetek licenciranja: 18.01.2021

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: pokritje, sodi podgraf, lihi podgraf, T-spoj, vpeto drevo

Projekti

• Financer: ARRS - Agencija za raziskovalno dejavnost Republike Slovenije
• Številka projekta: P1-0383
• Naslov: Kompleksna omrežja

• Financer: ARRS - Agencija za raziskovalno dejavnost Republike Slovenije
• Številka projekta: J1-1692
• Naslov: Barvanja, dekompozicije in pokritja grafov