Minimum Feedback Vertex Sets in Distance Graphs and Circulant Graphs
Hamamache Kheddouci, Olivier Togni
Abstract
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.
Full Text: PDF PostScript