Total edge–vertex domination
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 54 (2020), article no. 1

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.

DOI : 10.1051/ita/2020001
Classification : 05C69
Keywords: 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},
     year = {2020},
     publisher = {EDP Sciences},
     volume = {54},
     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

[1] R. Boutrig and M. Chellali, Total vertex-edge domination. Int. J. Comput. Math. 95 (2018) 1820–1828. | MR | Zbl | DOI

[2] E. J. Cockayne, R. M. Dawes and S. T. Hedetniemi, Total domination in graphs. Networks 10 (1980) 211–219. | MR | Zbl | DOI

[3] T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Fundamentals of Domination in Graphs. Marcel Dekker, New York (1998). | MR

[4] B. Krishnakumari, Y. B. Venkatakrishnan and M. Krzywkowski, On trees with total domination number equal to edge-vertex domination number plus one. Proc. Indian Acad. Sci 126 (2016) 153–157. | MR | Zbl

[5] J. R. Lewis, Vertex-edge and edge-vertex domination in graphs. Ph.D. thesis, Clemson University, United States (2007).

[6] J. W. Peters, Theoretical and algorithmic results on domination and connectivity. Ph.D. thesis, Clemson University, United States (1986). | MR

[7] Y. B. Venkatakrishnan and B. Krishnakumari, An improved upper bound of edge-vertex domination of a tree. Inf. Process. Lett. 134 (2018) 14–17. | MR | Zbl | DOI

Cité par Sources :