Graphs with unique minimum edge-vertex dominating sets

Document Type : Original paper

Authors

1 Department of Mathematics, SASTRA Deemed to be University, Thanjavur, Tamil Nadu, India

2 LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria

Abstract

An edge $e$ of a simple graph $G=(V_{G},E_{G})$ is said to ev-dominate a vertex $v\in V_{G}$ if $e$ is incident with $v$ or $e$ is incident with a vertex adjacent to $v$. A subset $D\subseteq E_{G}$ is an edge-vertex dominating set (or an evd-set for short) of $G$ if every vertex of $G$ is ev-dominated by an edge of $D$. The edge-vertex domination number of $G$ is the minimum cardinality of an evd-set of $G$. In this paper, we initiate the study of the graphs with unique minimum evd-sets that we will call UEVD-graphs. We first present some basic properties of UEVD-graphs, and then we characterize UEVD-trees by equivalent conditions as well as by a constructive method.

Keywords

Main Subjects

References

[1] M. Chellali and T.W. Haynes, Trees with unique minimum paired-dominating sets, Ars Combin. 73 (2004), 3–12.
[2] M. Chellali and T.W. Haynes, A characterization of trees with unique minimum double dominating sets, Util. Math. 83 (2010), 233–242.
[3] M. Fischermann and L. Volkmann, Unique minimum domination in trees, Australas. J. Combin. 25 (2002), 117–124.
[4] G. Gunther, B. Hartnell, L.R. Markus, and D. Rall, Trees with unique minimum paired-dominating sets, Congr. Numer. 101 (1994), 55–63.
[5] T.W. Haynes and M.A. Henning, Trees with unique minimum total dominating sets, Discuss. Math. Graph Theory 22 (2002), no. 2, 233–246.  https://doi.org/10.7151/dmgt.2349
[6] T.W. Haynes and M.A. Henning, Trees with unique minimum semitotal dominating sets, Graphs Combin. 36 (2020), no. 3, 689–702.  https://doi.org/10.1007/s00373-020-02145-0
[7] T.W. Haynes and M.A. Henning, Unique minimum semipaired dominating sets in trees, Discuss. Math. Graph Theory 43 (2023), no. 1, 35–53.  https://doi.org/10.7151/dmgt.2349
[8] B. Krishnakumari, Y.B. Venkatakrishnan, and M. Krzywkowski, On trees with total domination number equal to edge-vertex domination number plus one, Proc. Math. Sci. 126 (2016), 153–157.  https://doi.org/10.1007/s12044-016-0267-6
[9] J.R. Lewis, Vertex-edge and edge-vertex domination in graphs, Ph.D. thesis, Clemson University, Clemson, 2007.
[10] J.W. Peters, Theoretical and algorithmic results on domination and connectivity, Ph.D. thesis, Clemson University, Clemson, 1986.
[11] Y.B. Venkatakrishnan and B. Krishnakumari, An improved upper bound of edge–vertex domination number of a tree, Information Processing Letters 134 (2018), 14–17.  https://doi.org/10.1016/j.ipl.2018.01.012
[12] W. Zhao, F. Wang, and H. Zhang, Construction for trees with unique minimum dominating sets, Int. J. Comput. Math. Comput. Sys. Theory 3 (2018), no. 3, 204–213.  https://doi.org/10.1080/23799927.2018.1531930
Communications in Combinatorics and Optimization
Volume 10, Issue 1
March 2025
Pages 99-109

Files

Share

How to cite

Statistics