| Naslov: | On balanceable and simply balanceable regular graphs |
|---|
| Avtorji: | ID Ahanjideh, Milad (Avtor)
ID Milanič, Martin (Avtor)
ID Milanič, Mary Agnes (Avtor) |
|---|
| Datoteke: |  RAZ_Ahanjideh_Milad_2025.pdf (530,38 KB)
MD5: 17134BC39DD01C6322A17CC89008D45E
 https://doi.org/10.1016/j.ejc.2024.104045
|
|---|
| Jezik: | Angleški jezik |
|---|
| Vrsta gradiva: | Članek v reviji |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: | FAMNIT - Fakulteta za matematiko, naravoslovje in informacijske tehnologije
|
|---|
| Opis: | 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. |
|---|
| Ključne besede: | balanceable graph, simply balanceable graph, cubic graph, 4-regular graph, regular graph, independent set |
|---|
| Datum objave: | 24.08.2024 |
|---|
| Leto izida: | 2025 |
|---|
| Št. strani: | str. 1-14 |
|---|
| Številčenje: | Vol. 124, [article no.] ǂ104045 |
|---|
| PID: | 20.500.12556/RUP-21526  |
|---|
| UDK: | 519.17 |
|---|
| ISSN pri članku: | 0195-6698 |
|---|
| DOI: | 10.1016/j.ejc.2024.104045 |
|---|
| COBISS.SI-ID: | 207809283 |
|---|
| Datum objave v RUP: | 06.08.2025 |
|---|
| Število ogledov: | 527 |
|---|
| Število prenosov: | 7 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
