Coverability of graphs by parity regular subgraphs

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

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.

• Language: English
• Keywords: covering, even subgraph, odd subgraph, T-join, spanning tree
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Year: 2021
• Number of pages: 15 str.
• Numbering: Vol. 9, iss. 2, art. 182
• PID: 20.500.12556/RUL-134886
• UDC: 519.17
• ISSN on article: 2227-7390
• DOI: 10.3390/math9020182
• COBISS.SI-ID: 47971331
• Publication date in RUL: 10.02.2022

Record is a part of a journal

• Title: Mathematics
• Shortened title: Mathematics
• Publisher: MDPI AG
• ISSN: 2227-7390
• COBISS.SI-ID: 523267865

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.
• Licensing start date: 18.01.2021

Secondary language

• Language: Slovenian
• Keywords: pokritje, sodi podgraf, lihi podgraf, T-spoj, vpeto drevo

Projects

• Funder: ARRS - Slovenian Research Agency
• Project number: P1-0383
• Name: Kompleksna omrežja

• Funder: ARRS - Slovenian Research Agency
• Project number: J1-1692
• Name: Barvanja, dekompozicije in pokritja grafov