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
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] R. Boutrig and M. Chellali, Total vertex-edge domination. Int. J. Comput. Math. 95 (2018) 1820–1828. | DOI | MR | Zbl

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

[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. | DOI | MR | Zbl

  • Samanta Adhya, Amita; Mondal, Sukumar; Charan Barman, Sambhu Edge-vertex domination on interval graphs, Discrete Mathematics, Algorithms and Applications, Volume 16 (2024) no. 02 | DOI:10.1142/s1793830923500155
  • Kim, Kijung Edge-vertex domination in trees, Discrete Mathematics, Algorithms and Applications, Volume 14 (2022) no. 08 | DOI:10.1142/s1793830922500434
  • Şahin, Bünyamin New network entropy: The domination entropy of graphs, Information Processing Letters, Volume 174 (2022), p. 106195 | DOI:10.1016/j.ipl.2021.106195
  • Şahin, Abdulgani; Ali, Gohar Further Results on Total Edge‐Vertex Domination, Journal of Mathematics, Volume 2022 (2022) no. 1 | DOI:10.1155/2022/5439610
  • Şahin, Bünyamin; Şahin, Abdulgani 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
  • Şahin, Bünyamin; Şahin, Abdulgani 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