Hamamache Kheddouci ; Olivier Togni - Bounds for minimum feedback vertex sets in distance graphs and circulant graphs

dmtcs:417 - Discrete Mathematics & Theoretical Computer Science, January 1, 2008, Vol. 10 no. 1 - https://doi.org/10.46298/dmtcs.417
Bounds for minimum feedback vertex sets in distance graphs and circulant graphsArticle

Authors: Hamamache Kheddouci 1; Olivier Togni ORCID2

  • 1 Laboratoire d'Informatique pour l'Entreprise et les Systèmes de Production
  • 2 Laboratoire Electronique, Informatique et Image [UMR6306]

For a set D ⊂ Zn, the distance graph Pn(D) has Zn as its vertex set and the edges are between vertices i and j with |i − j| ∈ D. The circulant graph Cn(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.


Volume: Vol. 10 no. 1
Section: Graph and Algorithms
Published on: January 1, 2008
Imported on: March 26, 2015
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]

1 Document citing this article

Consultation statistics

This page has been seen 331 times.
This article's PDF has been downloaded 205 times.