کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4648831 1342432 2007 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Feedback numbers of Kautz digraphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Feedback numbers of Kautz digraphs
چکیده انگلیسی

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(d,n) (fa(d,n)fa(d,n)) denote the minimum cardinality over all feedback vertex (resp. arc) sets of the Kautz digraph K(d,n)K(d,n). This paper proves that for any integers d⩾2d⩾2 and n⩾1n⩾1f(d,n)=dforn=1,(ϕ⊙θ)(n)n+(ϕ⊙θ)(n-1)n-1for2⩽n⩽7,dnn+dn-1n-1+O(ndn-4)forn⩾8,fa(d,n)=f(d,n+1)forn⩾1,where (ϕ⊙θ)(n)=∑i|nϕ(i)θ(n/i)(ϕ⊙θ)(n)=∑i|nϕ(i)θ(n/i), i|ni|n means i divides n  , θ(i)=di+(-1)idθ(i)=di+(-1)id, ϕ(1)=1ϕ(1)=1 and ϕ(i)=i·∏j=1r(1-1/pj) for i⩾2i⩾2, where p1,…,prp1,…,pr are the distinct prime factors of i, not equal to 1.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 307, Issue 13, 6 June 2007, Pages 1589–1599
نویسندگان
, , , ,