Artykuł w czasopiśmie
Brak miniatury
Licencja
Dostęp zamkniętyOn Supereulerian 2-Edge-Coloured Graphs
| dc.abstract.en | A 2-edge-coloured graph G is supereulerian if G contains a spanning closed trail in which the edges alternate in colours. We show that for general 2-edge-coloured graphs it is NP-complete to decide whether the graph is supereulerian. An eulerian factor of a 2-edge-coloured graph is a collection of vertex-disjoint induced subgraphs which cover all the vertices of G such that each of these subgraphs is supereulerian. We give a polynomial algorithm to test whether a 2-edge-coloured graph has an eulerian factor and to produce one when it exists. A 2-edge-coloured graph is (trail-)colour-connected if it contains a pair of alternating (u, v)-paths ((u, v)-trails) whose union is an alternating closed walk for every pair of distinct vertices u, v. We prove that a 2-edge-coloured complete bipartite graph is supereulerian if and only if it is colour-connected and has an eulerian factor. A 2-edge-coloured graph is M-closed if xz is an edge of G whenever some vertex u is joined to both x and z by edges of the same colour. M-closed 2-edge-coloured graphs, introduced in Contreras-Balbuena et al. (Discret Math Theoret Comput Sci 21:1, 2019), form a rich generalization of 2-edge-coloured complete graphs. We show that if G is obtained from an M-closed 2-edge-coloured graph H by substituting independent sets for the vertices of H, then G is supereulerian if and only if G is trail-colour-connected and has an eulerian factor. Finally we discuss 2-edge-coloured complete multipartite graphs and show that such a graph may not be supereulerian even if it is trail-colour-connected and has an eulerian factor. |
| dc.affiliation | Uniwersytet Warszawski |
| dc.contributor.author | Bang-Jensen, Jørgen |
| dc.contributor.author | Yeo, Anders |
| dc.contributor.author | Bellitto, Thomas |
| dc.date.accessioned | 2024-01-25T15:45:47Z |
| dc.date.available | 2024-01-25T15:45:47Z |
| dc.date.issued | 2021 |
| dc.description.finance | Publikacja bezkosztowa |
| dc.description.number | 6 |
| dc.description.volume | 37 |
| dc.identifier.doi | 10.1007/S00373-021-02377-8 |
| dc.identifier.issn | 0911-0119 |
| dc.identifier.uri | https://repozytorium.uw.edu.pl//handle/item/114759 |
| dc.identifier.weblink | https://link.springer.com/content/pdf/10.1007/s00373-021-02377-8.pdf |
| dc.language | eng |
| dc.pbn.affiliation | computer and information sciences |
| dc.relation.ispartof | Graphs and Combinatorics |
| dc.relation.pages | 2601-2620 |
| dc.rights | ClosedAccess |
| dc.sciencecloud | nosend |
| dc.subject.en | 2-edge-coloured graph |
| dc.subject.en | Alternating hamiltonian cycle |
| dc.subject.en | Supereulerian |
| dc.subject.en | Alternating cycle |
| dc.subject.en | Eulerian factor |
| dc.subject.en | Extension of a 2-edge-coloured graph |
| dc.title | On Supereulerian 2-Edge-Coloured Graphs |
| dc.type | JournalArticle |
| dspace.entity.type | Publication |