Feedback numbers of Kautz digraphs
type: Item
instance of: scholarly article
title: Feedback numbers of Kautz digraphs
zbMATH Open document ID: 1119.05052
author: Jun-Ming Xu
author: Yezhou Wu
author: Jia Huang
author: Chao Yang
published in: Discrete Mathematics
publication date: 2007-05-11T00:00:00Z
review text: 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\).
reviewed by: Vladimír Lacko
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 5151758
zbMATH Keywords: feedback vertex set
zbMATH Keywords: feedback number
zbMATH Keywords: Kautz digraphs
zbMATH Keywords: cycles
zbMATH Keywords: acyclic subgraph
MaRDI profile type: Publication
full work available at URL: j.disc.2006.09.010
OpenAlex ID: W2124463034
cites work: A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
cites work: Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
cites work: Decycling cubes and grids
cites work: Q3145802
cites work: Feedback vertex set in hypercubes
cites work: Q4198056
cites work: Minimum feedback vertex sets in shuffle-based interconnection networks
cites work: On the feedback vertex set problem in permutation graphs
cites work: Almost exact minimum feedback vertex set in meshes and butterflies
cites work: The Lattice Point Covering Theorem for Rectangles
cites work: Feedback vertex sets and cyclically reducible graphs
cites work: Minimal feedback vertex sets in directed split‐stars
cites work: Q4435203
DOI: 10.1016/J.DISC.2006.09.010
description: scientific article; zbMATH DE number 5151758