Feedback numbers of Kautz digraphs (Q879335): Difference between revisions

The authors consider Kautz digraphs \(K(d,n)\) for \(d\geq 2,n\geq 1\). The vertex set of \(K(d,n)\) is defined as the set \(V(d,n)=\{x_1x_2\cdots x_n\mid x_i\in\{1,2\dots,d+1\}\text{ for }i=1,2,\dots,n\text{ and }x_i\neq x_{i+1}\text{ for }i=1,2,\dots,n-1\}\). A subset of vertices (arcs) of a graph \(G\) is called a feedback vertex (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 (arc) sets of the Kautz digraph \(K(d,n)\). The authors prove that for any integers \(d\geq 2\) and \(n\geq 1\) \[ \begin{aligned} & f(d,n)=\begin{cases} d\quad & \text{for }n=1,\\ \frac{(\varphi\odot\theta)(n)}{n}+\frac{(\varphi\odot\theta)(n-1)}{n-1}& \text{for }2\leq n\leq7,\\ \frac{d^n}{n}+\frac{d^{n-1}}{n-1}& \text{for }n\geq 8, \end{cases}\\ & f_a(d,n)=f(d,n+1)\quad \text{for }n\geq 1, \end{aligned} \] where \((\varphi\odot\theta)(n)=\sum_{i| n}\varphi(i)\theta(n/i)\), \(\theta(i)=d^i+(-1)^id\), \(\varphi(1)=1\) and \(\varphi(i)=i\cdot\prod_{j=1}^{r}(1-1/p_j)\) for \(i\geq 2\), where \(p_1,\dots,p_r\) are the distinct prime factors of \(i\).