Feedback numbers of Kautz digraphs

Jun Ming Xu, Ye Zhou Wu, Jia Huang, Chao Yang

Research output: Contribution to journalArticle

14 Scopus citations

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) (fa (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) = di + (- 1)i d, φ{symbol} (1) = 1 and φ{symbol} (i) = i · ∏j = 1r (1 - 1 / pj) for i ≥ 2, where p1, ..., pr are the distinct prime factors of i, not equal to 1.

Original languageEnglish (US)
Pages (from-to)1589-1599
Number of pages11
JournalDiscrete Mathematics
Volume307
Issue number13
DOIs
StatePublished - 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