On two consequences of Berge–Fulkerson conjecture
The classical Berge–Fulkerson conjecture states that any bridgeless cubic graph admits a list of six perfect matchings such that each edge of belongs to two of the perfect matchings from the list. In this short note, we discuss two statements that are consequences of this conjecture. The first of th...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Taylor & Francis Group
2020-01-01
|
| Series: | AKCE International Journal of Graphs and Combinatorics |
| Subjects: | |
| Online Access: | http://dx.doi.org/10.1016/j.akcej.2019.03.018 |
| _version_ | 1818392171523342336 |
|---|---|
| author | Vahan V. Mkrtchyan Gagik N. Vardanyan |
| author_facet | Vahan V. Mkrtchyan Gagik N. Vardanyan |
| author_sort | Vahan V. Mkrtchyan |
| collection | DOAJ |
| description | The classical Berge–Fulkerson conjecture states that any bridgeless cubic graph admits a list of six perfect matchings such that each edge of belongs to two of the perfect matchings from the list. In this short note, we discuss two statements that are consequences of this conjecture. The first of them states that for any bridgeless cubic graph , edge and with , there are three perfect matchings of such that and belongs to exactly of these perfect matchings. The second one states that for any bridgeless cubic graph and its vertex , there are three perfect matchings of such that and the edges incident to belong to , and of these perfect matchings, where the numbers , and satisfy the obvious necessary conditions. In the paper, we show that the first statement is equivalent to Fan–Raspaud conjecture. We also show that the smallest counter-example to the second one is a cyclically 4-edge-connected cubic graph. |
| first_indexed | 2024-12-14T05:25:11Z |
| format | Article |
| id | doaj.art-6195c2eb23934c29abbcc6459b715e4d |
| institution | Directory Open Access Journal |
| issn | 0972-8600 2543-3474 |
| language | English |
| last_indexed | 2024-12-14T05:25:11Z |
| publishDate | 2020-01-01 |
| publisher | Taylor & Francis Group |
| record_format | Article |
| series | AKCE International Journal of Graphs and Combinatorics |
| spelling | doaj.art-6195c2eb23934c29abbcc6459b715e4d2022-12-21T23:15:32ZengTaylor & Francis GroupAKCE International Journal of Graphs and Combinatorics0972-86002543-34742020-01-0117158458610.1016/j.akcej.2019.03.0181760677On two consequences of Berge–Fulkerson conjectureVahan V. Mkrtchyan0Gagik N. Vardanyan1Dipartimento di Informatica, Universita degli Studi di VeronaDepartment of Informatics and Applied Mathematics, Yerevan State UniversityThe classical Berge–Fulkerson conjecture states that any bridgeless cubic graph admits a list of six perfect matchings such that each edge of belongs to two of the perfect matchings from the list. In this short note, we discuss two statements that are consequences of this conjecture. The first of them states that for any bridgeless cubic graph , edge and with , there are three perfect matchings of such that and belongs to exactly of these perfect matchings. The second one states that for any bridgeless cubic graph and its vertex , there are three perfect matchings of such that and the edges incident to belong to , and of these perfect matchings, where the numbers , and satisfy the obvious necessary conditions. In the paper, we show that the first statement is equivalent to Fan–Raspaud conjecture. We also show that the smallest counter-example to the second one is a cyclically 4-edge-connected cubic graph.http://dx.doi.org/10.1016/j.akcej.2019.03.018cubic graphperfect matchingberge–fulkerson conjecturefan–raspaud conjecture |
| spellingShingle | Vahan V. Mkrtchyan Gagik N. Vardanyan On two consequences of Berge–Fulkerson conjecture AKCE International Journal of Graphs and Combinatorics cubic graph perfect matching berge–fulkerson conjecture fan–raspaud conjecture |
| title | On two consequences of Berge–Fulkerson conjecture |
| title_full | On two consequences of Berge–Fulkerson conjecture |
| title_fullStr | On two consequences of Berge–Fulkerson conjecture |
| title_full_unstemmed | On two consequences of Berge–Fulkerson conjecture |
| title_short | On two consequences of Berge–Fulkerson conjecture |
| title_sort | on two consequences of berge fulkerson conjecture |
| topic | cubic graph perfect matching berge–fulkerson conjecture fan–raspaud conjecture |
| url | http://dx.doi.org/10.1016/j.akcej.2019.03.018 |
| work_keys_str_mv | AT vahanvmkrtchyan ontwoconsequencesofbergefulkersonconjecture AT gagiknvardanyan ontwoconsequencesofbergefulkersonconjecture |