# دانلود رایگان مقاله برخی از ویژگی های نمودارهای دونات

عنوان فارسی
برخی از ویژگی های نمودارهای دونات
عنوان انگلیسی
On some properties of doughnut graphs
صفحات مقاله فارسی
0
صفحات مقاله انگلیسی
10
سال انتشار
2016
نشریه
الزویر - Elsevier
فرمت مقاله انگلیسی
PDF
کد محصول
E2081
رشته های مرتبط با این مقاله
ریاضی
گرایش های مرتبط با این مقاله
ریاضی کاربردی
مجله
مجله بین المللی نمودار ها و ترکیبیات - International Journal of Graphs and Combinatorics
دانشگاه
وزارت علوم کامپیوتر و مهندسی، دانشگاه داکا، بنگلادش
کلمات کلیدی
نمودار مسطح، ساختار بازگشتی، هامیلتونی، تحمل خطا، اتصال
۰.۰ (بدون امتیاز)
امتیاز دهید
چکیده

Abstract

The class of doughnut graphs is a subclass of 5-connected planar graphs. It is known that a doughnut graph admits a straight-line grid drawing with linear area, the outerplanarity of a doughnut graph is 3, and a doughnut graph is k-partitionable. In this paper we show that a doughnut graph exhibits a recursive structure. We also give an efficient algorithm for finding a shortest path between any pair of vertices in a doughnut graph. We also propose a nice application of a doughnut graph based on its properties.

نتیجه گیری

6. Conclusion

In this paper, we have studied recursive structure of doughnut graphs. We have proposed an efficient algorithm to find shortest path between any pair of vertices which exploit the structure of the graph. We have also found that doughnut graph has smaller diameter, higher degree and connectivity, maximal fault tolerance and ring embedding. There are several parameters like connectivity, degree, diameter, symmetry and fault tolerance which are considered for building interconnection networks [9]. Table 1 presents the topological comparison of various Cayley graphs, which are widely used as interconnection networks, with doughnut graphs. The table shows that topological properties of doughnut graphs are very much similar to interconnection networks. One of the limitation is the diameter which is linear but the coefficient is 1/8. We may have an efficient routing scheme using shortest path finding algorithm. We can have a scalable interconnection network using doughnut graphs since the degree of a vertex of a doughnut graph does not change with the size of the graph. This is also important for VLSI implementation point of view as well as applications where the computing nodes in an interconnection networks only have fixed number of I/O ports. Thus doughnut graphs may find nice applications as interconnection networks.

بدون دیدگاه