تعداد نشریات | 50 |
تعداد شمارهها | 2,045 |
تعداد مقالات | 19,140 |
تعداد مشاهده مقاله | 22,398,071 |
تعداد دریافت فایل اصل مقاله | 20,915,807 |
Improvment Upper Bound of the Independence Nnmber of Maximum Independent Set in Unit Disk Graph | ||
Journal of New Researches in Mathematics | ||
مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 11 مهر 1401 | ||
نوع مقاله: research paper | ||
شناسه دیجیتال (DOI): 10.30495/jnrm.2022.58031.2028 | ||
نویسندگان | ||
Gholam Hassan Shirdel ![]() ![]() | ||
1Associate Professor at University of Qom | ||
2teacher | ||
چکیده | ||
In a unit disk graph two vertices are adjacent if the distance between them is less than or equal to one with a two-dimensional Euclidean meter. The size of the maximal independent set in a graph G is called the independent number denoted by α(G). The size of the minimal connected dominating set in a graph G is called the connected domination number denoted by γ_c^((G)). A subset S of vertices in a graph is called a dominating set if every vertex is either in the subset or adjacent to a vertex in the S. A dominating set is connected if it induces a connected subgraph. A connected dominating set is often used as a virtual backbone in wireless sensor networks to improve communication and storage performance. Clearly the smaller virtual backbone gives the better performance. However computing a minimal connected dominating set is NP-hard. In other hand relation between the size of the minimal connected dominating set in a graph G is very important. The aim of this paper is to determine two better upper bounds of the independence number dependent on the connected domination number for a unit disk graph. Further we improve the upper bound to obtain the best bound with respect to the upper bounds obtained thus far. | ||
کلیدواژهها | ||
Connected dominating set؛ Independent number؛ Unit disk graph؛ Maximal independent set؛ Connected domination number | ||
آمار تعداد مشاهده مقاله: 81 |