آمار
| تعداد نشریات | 5 |
| تعداد شماره‌ها | 111 |
| تعداد مقالات | 1,254 |
| تعداد مشاهده مقاله | 1,203,690 |
| تعداد دریافت فایل اصل مقاله | 1,064,389 |
k-Efficient partitions of graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 4، دوره 4، شماره 2، اسفند 2019، صفحه 109-122 اصل مقاله (419.76 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2019.26446.1112 | ||
| نویسندگان | ||
| M Chellali1؛ Teresa W. Haynes* 2؛ Stephen T. Hedetniemi3 | ||
| 1LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria | ||
| 2Department of Mathematics and Statistics, East Tennessee State University, Johnson City, TN 37614-0002 USA | ||
| 3Professor Emeritus, School of Computing, Clemson University, Clemson, SC 29634 USA | ||
| چکیده | ||
| A set $S = \{u_1,u_2, \ldots, u_t\}$ of vertices of $G$ is an efficient dominating set if every vertex of $G$ is dominated exactly once by the vertices of $S$. Letting $U_i$ denote the set of vertices dominated by $u_i$, we note that $\{U_1, U_2, \ldots U_t\}$ is a partition of the vertex set of $G$ and that each $U_i$ contains the vertex $u_i$ and all the vertices at distance~1 from it in $G$. In this paper, we generalize the concept of efficient domination by considering $k$-efficient domination partitions of the vertex set of $G$, where each element of the partition is a set consisting of a vertex $u_i$ and all the vertices at distance~$d_i$ from it, where $d_i \in \{0,1, \ldots, k\}$. For any integer $k \geq 0$, the $k$-efficient domination number of $G$ equals the minimum order of a $k$-efficient partition of $G$. We determine bounds on the $k$-efficient domination number for general graphs, and for $k \in \{1,2\}$, we give exact values for some graph families. Complexity results are also obtained. | ||
| کلیدواژه‌ها | ||
| domination؛ Efficient Domination؛ Distance-$k$ domination | ||
| مراجع | ||
|
[1] D.W. Bange, A.E. Barkauskas, and P.J. Slater, Efficient dominating sets in graphs, Applications of Discrete Math. , R. D. Ringeisen and F. S. Roberts, eds., SIAM, Philadelphia (1988), 189–199.
[2] J.E. Dunbar, D.J. Erwin, T.W. Haynes, S.M. Hedetniemi, and S.T. Hedetniemi, Broadcasts in graphs, Discrete Appl. Math. 154 (2006), no. 1, 59–75.
[3] D.J. Erwin, Dominating broadcasts in graphs, Bull. Inst. Comb. Appl. 42 (2004), 89–105.
[4] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York, 1998.
[5] M.S. Jacobson and L.F. Kinch, On the domination number of products of graphs: I, Ars Combin. 18 (1983), 33–44.
[6] A. Meir and J. Moon, Relations between packing and covering numbers of a tree, Pacific J. Math. 61 (1975), no. 1, 225–233.
| ||
|
آمار تعداد مشاهده مقاله: 1,019 تعداد دریافت فایل اصل مقاله: 751 |
||