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

چکیده انگلیسی
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
Journal: Discrete Mathematics - Volume 307, Issue 13, 6 June 2007, Pages 1589–1599
نویسندگان
Jun-Ming Xu, Ye-Zhou Wu, Jia Huang, Chao Yang,