آمار
| تعداد نشریات | 5 |
| تعداد شماره‌ها | 111 |
| تعداد مقالات | 1,247 |
| تعداد مشاهده مقاله | 1,199,503 |
| تعداد دریافت فایل اصل مقاله | 1,060,203 |
Well ve-covered graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 4، دوره 10، شماره 1، خرداد 2025، صفحه 69-78 اصل مقاله (393.88 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2023.28186.1469 | ||
| نویسندگان | ||
| Razika Boutrig1؛ Mustapha Chellali* 2؛ Nacéra Meddah2 | ||
| 1Faculty of Economic Sciences and Management, University of Boumerdes, Algeria | ||
| 2LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria | ||
| چکیده | ||
| A vertex $u$ of a graph $G=(V,E)$ ve-dominates every edge incident to $u$ as well as every edge adjacent to these incident edges. A set $S\subseteq V$ is a vertex-edge dominating set (or a ved-set for short) if every edge of $E$ is ve-dominated by at least one vertex in $S$. A ved-set is independent if its vertices are pairwise non-adjacent. The independent ve-domination number $i_{ve}(G)$ is the minimum cardinality of an independent ved-set and the upper independent ve-domination number $\beta_{ve}(G)$ is the maximum cardinality of a minimal independent ved-set of $G$. In this paper, we are interesting in graphs $G$ such that $i_{ve}(G)=\beta_{ve}(G)$, which we call well ve-covered graphs. We show that recognizing well ve-covered graphs is co-NP-complete, and we present a constructive characterization of well ve-covered trees. | ||
| کلیدواژه‌ها | ||
| vertex-edge domination؛ independent vertex-edge domination؛ well ve-covered graphs؛ trees | ||
| مراجع | ||
|
[1] D. 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, pp. 189–199.
[2] R. Boutrig, M. Chellali, T.W. Haynes, and S.T. Hedetniemi, Vertex-edge domination in graphs, Aequat. Math. 90 (2016), 355–366. https://doi.org/10.1007/s00010-015-0354-2
[3] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York, 1979.
[4] B. Krishnakumari, Y.B. Venkatakrishnan, and M. Krzywkowski, Bounds on the vertex–edge domination number of a tree, Comptes Rendus Mathematique 352 (2014), no. 5, 363–366. https://doi.org/10.1016/j.crma.2014.03.017
[5] J. Lewis, S.T. Hedetniemi, T.W. Haynes, and G.H. Fricke, Vertex-edge domination, Util. Math. 81 (2010), 193–213.
[6] J.R. Lewis, Vertex-edge and edge-vertex domination in graphs, Ph.D. thesis, Clemson University, Clemson, 2007.
[7] J.W. Peters, Theoretical and algorithmic results on domination and connectivity, Ph.D. thesis, Clemson University, Clemson, 1986.
[8] M.D. Plummer, Some covering concepts in graphs, J. Comb. Theory 8 (1970), no. 1, 91–98. https://doi.org/10.1016/S0021-9800(70)80011-4
[9] M.D. Plummer, Well-covered graphs: a survey, Quaest. Math. 16 (1993), no. 3, 253–287. https://doi.org/10.1080/16073606.1993.9631737
[10] P. Żyliński, Vertex-edge domination in graphs, Aequat. Math. 93 (2019), no. 4, 735–742. https://doi.org/10.1007/s00010-018-0609-9 | ||
|
آمار تعداد مشاهده مقاله: 304 تعداد دریافت فایل اصل مقاله: 1,156 |
||