### Abstract

A subset of vertices (resp. arcs) of a graph G is called a feedback vertex (resp. arc) set of G if its removal results in an acyclic subgraph. Let f (d, n) (f_{a} (d, n)) denote the minimum cardinality over all feedback vertex (resp. arc) sets of the Kautz digraph K (d, n). This paper proves that for any integers d ≥ 2 and n ≥ 1{Mathematical expression}where (φ{symbol} ȯ θ) (n) = ∑_{i | n} φ{symbol} (i) θ (n / i), i | n means i divides n, θ (i) = d^{i} + (- 1)^{i} d, φ{symbol} (1) = 1 and φ{symbol} (i) = i · ∏_{j = 1}^{r} (1 - 1 / p_{j}) for i ≥ 2, where p_{1}, ..., p_{r} are the distinct prime factors of i, not equal to 1.

Original language | English (US) |
---|---|

Pages (from-to) | 1589-1599 |

Number of pages | 11 |

Journal | Discrete Mathematics |

Volume | 307 |

Issue number | 13 |

DOIs | |

State | Published - Jun 6 2007 |

### Keywords

- Acyclic subgraph
- Cycles
- Feedback number
- Feedback vertex set
- Kautz digraphs

### ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics

## Fingerprint Dive into the research topics of 'Feedback numbers of Kautz digraphs'. Together they form a unique fingerprint.

## Cite this

Xu, J. M., Wu, Y. Z., Huang, J., & Yang, C. (2007). Feedback numbers of Kautz digraphs.

*Discrete Mathematics*,*307*(13), 1589-1599. https://doi.org/10.1016/j.disc.2006.09.010