| Title: | On balanceable and simply balanceable regular graphs |
|---|
| Authors: | ID Ahanjideh, Milad (Author)
ID Milanič, Martin (Author)
ID Milanič, Mary Agnes (Author) |
|---|
| Files: |  RAZ_Ahanjideh_Milad_2025.pdf (530,38 KB)
MD5: 17134BC39DD01C6322A17CC89008D45E
 https://doi.org/10.1016/j.ejc.2024.104045
|
|---|
| Language: | English |
|---|
| Work type: | Article |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: | FAMNIT - Faculty of Mathematics, Science and Information Technologies
|
|---|
| Abstract: | We continue the study of balanceable graphs, defined by Caro, Hansberg, and Montejano in 2021 as graphs G such that any 2-coloring of the edges of a sufficiently large complete graph containing sufficiently many edges of each color contains a balanced copy of G (that is, a copy with half the edges of each color). While the problem of recognizing balanceable graphs was conjectured to be NP-complete by Dailly, Hansberg, and Ventura in 2021, balanceable graphs admit an elegant combinatorial characterization: a graph is balanceable if and only there exist two vertex subsets, one containing half of all the graph’s edges and another one such that the corresponding cut contains half of all the graph’s edges. We consider a special case of this property, namely when one of the two sets is a vertex cover, and call the corresponding graphs simply balanceable. We prove a number of results on balanceable and simply balanceable regular graphs. First, we characterize simply balanceable regular graphs via a condition involving the independence number of the graph. Second, we address a question of Dailly, Hansberg, and Ventura from 2021 and show that every cubic graph is balanceable. Third, using Brooks’ theorem, we show that every 4-regular graph with order divisible by 4 is balanceable. Finally, we show that it is NP-complete to determine if a 9-regular graph is simply balanceable. |
|---|
| Keywords: | balanceable graph, simply balanceable graph, cubic graph, 4-regular graph, regular graph, independent set |
|---|
| Publication date: | 24.08.2024 |
|---|
| Year of publishing: | 2025 |
|---|
| Number of pages: | str. 1-14 |
|---|
| Numbering: | Vol. 124, [article no.] ǂ104045 |
|---|
| PID: | 20.500.12556/RUP-21526  |
|---|
| UDC: | 519.17 |
|---|
| ISSN on article: | 0195-6698 |
|---|
| DOI: | 10.1016/j.ejc.2024.104045 |
|---|
| COBISS.SI-ID: | 207809283 |
|---|
| Publication date in RUP: | 06.08.2025 |
|---|
| Views: | 528 |
|---|
| Downloads: | 7 |
|---|
| Metadata: |    |
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
