Well ve-covered graphs

Document Type : Original paper

Authors

1 Faculty of Economic Sciences and Management, University of Boumerdes, Algeria

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

Abstract

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.

Keywords

Main Subjects

References

[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
Communications in Combinatorics and Optimization
Volume 10, Issue 1
March 2025
Pages 69-78

Files

Share

How to cite

Statistics