Coverability of Graphs by Parity Regular Subgraphs

Mirko Petruševski and Riste Škrekovski
Additional contact information
Mirko Petruševski: Faculty of Mechanical Engineering, Ss. Cyril and Methodius University, 1000 Skopje, North Macedonia
Riste Škrekovski: Faculty for Mathematics and Physics, University of Ljubljana, 1000 Ljubljana, Slovenia

Mathematics, 2021, vol. 9, issue 2, 1-15

Abstract: 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.

Keywords: covering; even subgraph; odd subgraph; T -join; spanning tree (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/2/182/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/2/182/ (text/html)

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:gam:jmathe:v:9:y:2021:i:2:p:182-:d:482145

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().