آمار
| تعداد نشریات | 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   1؛ mehdi G jalinousi2
| ||
| 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 |
||
