Minimum Feedback Vertex Sets in Distance Graphs and Circulant Graphs
| Autor: | Hamamache Kheddouci, Olivier Togni |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2008 |
| Předmět: | |
| Zdroj: | Discrete Mathematics & Theoretical Computer Science, Vol 10, Iss 1 (2008) |
| Druh dokumentu: | article |
| ISSN: | 1462-7264 1365-8050 |
| Popis: | For a set D⊂ Z n, the distance graph P n (D) has Z n as its vertex set and the edges are between vertices i and j with |i-j|∈D. The circulant graph C n (D) is defined analogously by considering operations modulo n. The minimum feedback vertex set problem consists in finding the smallest number of vertices to be removed in order to cut all cycles in the graph. This paper studies the minimum feedback vertex set problem for some families of distance graphs and circulant graphs depending on the value of D. |
| Databáze: | Directory of Open Access Journals |
| Externí odkaz: |
|