An edge e ev-dominates a vertex v which is a vertex of e, as well as every vertex adjacent to v. A subset D ⊆ E is an edge-vertex dominating set (in simply, ev-dominating set) of G, if every vertex of a graph G is ev-dominated by at least one edge of D. The minimum cardinality of an ev-dominating set is named with ev-domination number and denoted by γ$$(G). A subset D ⊆ E is a total edge-vertex dominating set (in simply, total ev-dominating set) of G, if D is an ev-dominating set and every edge of D shares an endpoint with other edge of D. The total ev-domination number of a graph G is denoted with $$ and it is equal to the minimum cardinality of a total ev-dominating set. In this paper, we initiate to study total edge-vertex domination. We first show that calculating the number $$ for bipartite graphs is NP-hard. We also show the upper bound $$ for the total ev-domination number of a tree T, where T has order n, l leaves and s support vertices and we characterize the trees achieving this upper bound. Finally, we obtain total ev-domination number of paths and cycles.
Mots-clés : Domination, edge-vertex domination, total edge-vertex domination
@article{ITA_2020__54_1_A1_0, author = {Sahin, Abdulgani and Sahin, B\"unyamin}, title = {Total edge{\textendash}vertex domination}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, publisher = {EDP-Sciences}, volume = {54}, year = {2020}, doi = {10.1051/ita/2020001}, mrnumber = {4077201}, zbl = {1444.05109}, language = {en}, url = {https://www.numdam.org/articles/10.1051/ita/2020001/} }
TY - JOUR AU - Sahin, Abdulgani AU - Sahin, Bünyamin TI - Total edge–vertex domination JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2020 VL - 54 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ita/2020001/ DO - 10.1051/ita/2020001 LA - en ID - ITA_2020__54_1_A1_0 ER -
%0 Journal Article %A Sahin, Abdulgani %A Sahin, Bünyamin %T Total edge–vertex domination %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2020 %V 54 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ita/2020001/ %R 10.1051/ita/2020001 %G en %F ITA_2020__54_1_A1_0
Sahin, Abdulgani; Sahin, Bünyamin. Total edge–vertex domination. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 54 (2020), article no. 1. doi : 10.1051/ita/2020001. https://www.numdam.org/articles/10.1051/ita/2020001/
[1] Total vertex-edge domination. Int. J. Comput. Math. 95 (2018) 1820–1828. | DOI | MR | Zbl
and ,[2] Total domination in graphs. Networks 10 (1980) 211–219. | DOI | MR | Zbl
, and ,[3] Fundamentals of Domination in Graphs. Marcel Dekker, New York (1998). | MR
, , and ,[4] On trees with total domination number equal to edge-vertex domination number plus one. Proc. Indian Acad. Sci 126 (2016) 153–157. | MR | Zbl
, and ,[5] Vertex-edge and edge-vertex domination in graphs. Ph.D. thesis, Clemson University, United States (2007).
,[6] Theoretical and algorithmic results on domination and connectivity. Ph.D. thesis, Clemson University, United States (1986). | MR
,[7] An improved upper bound of edge-vertex domination of a tree. Inf. Process. Lett. 134 (2018) 14–17. | DOI | MR | Zbl
and ,- Edge-vertex domination on interval graphs, Discrete Mathematics, Algorithms and Applications, Volume 16 (2024) no. 02 | DOI:10.1142/s1793830923500155
- Edge-vertex domination in trees, Discrete Mathematics, Algorithms and Applications, Volume 14 (2022) no. 08 | DOI:10.1142/s1793830922500434
- New network entropy: The domination entropy of graphs, Information Processing Letters, Volume 174 (2022), p. 106195 | DOI:10.1016/j.ipl.2021.106195
- Further Results on Total Edge‐Vertex Domination, Journal of Mathematics, Volume 2022 (2022) no. 1 | DOI:10.1155/2022/5439610
- Double Edge–Vertex Domination, Intelligent and Fuzzy Techniques: Smart and Innovative Solutions, Volume 1197 (2021), p. 1564 | DOI:10.1007/978-3-030-51156-2_182
- On double edge-domination and total domination of trees, Journal of Intelligent Fuzzy Systems, Volume 42 (2021) no. 1, p. 121 | DOI:10.3233/jifs-219180
Cité par 6 documents. Sources : Crossref