CATALOGO DEI PRODOTTI DELLA RICERCA
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishAn r-graph is any graph that can be obtained as a conic combination of its own 1-factors. An r-graph G(V, E) is said to be indecomposable when its edge set E cannot be partitioned as E = E1 ∪ E2 so that Gi (V, Ei ) is an ri-graph for i = 1, 2 and, for some r1 , r2 . We give an indecomposable r-graph for every integer r ≥ 4. This answers a question raised in [Seymour, Proc London Math Soc 38 (1979, 423–460], and has interesting consequences for the Schrijver System of the T-cut polyhedron to be given in [Rizzi, 1997, to appear]. A graph in which every two 1-factors intersect is said to be poorly matchable. Every poorly matchable r-graph is indecomposable. We show that for every r ≥ 4 that "being indecomposable" does not imply "being poorly matchable." Next we give a poorly matchable r-graph for every r ≥ 4. The article provides counterexamples to some conjectures of Seymour.
| Titolo: | Indecomposable r-graphs and some other counterexamples |
| Autori: | |
| Data di pubblicazione: | 1999 |
| Rivista: | |
| Citazione: | Indecomposable r-graphs and some other counterexamples / Rizzi R.. - In: JOURNAL OF ALGORITHMS. - ISSN 0196-6774. - STAMPA. - 32:1(1999), pp. 1-15. |
| Abstract: | An r-graph is any graph that can be obtained as a conic combination of its own 1-factors. An r-graph G(V, E) is said to be indecomposable when its edge set E cannot be partitioned as E = E1 ∪ E2 so that Gi (V, Ei ) is an ri-graph for i = 1, 2 and, for some r1 , r2 . We give an indecomposable r-graph for every integer r ≥ 4. This answers a question raised in [Seymour, Proc London Math Soc 38 (1979, 423–460], and has interesting consequences for the Schrijver System of the T-cut polyhedron to be given in [Rizzi, 1997, to appear]. A graph in which every two 1-factors intersect is said to be poorly matchable. Every poorly matchable r-graph is indecomposable. We show that for every r ≥ 4 that "being indecomposable" does not imply "being poorly matchable." Next we give a poorly matchable r-graph for every r ≥ 4. The article provides counterexamples to some conjectures of Seymour. |
| Handle: | http://hdl.handle.net/11562/409601 |
| Appare nelle tipologie: | 01.01 Articolo in Rivista |
File in questo prodotto:
http://hdl.handle.net/11562/409601
Copyright © 2019