Double vertex-edge domination in trees
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
A vertex $v$ of a graph $G=(V,E)$ is said to $ve$-dominate every edge incident to $v$, as well as every edge adjacent to these incident edges. A set $S\subseteq V$ is called a double vertex-edge dominating set if every edge of $E$ is $ve$-dominated by at least two vertices of $S$. The minimum cardinality of a double vertex-edge dominating set of $G$ is the double vertex-edge domination number $\gamma_{dve}(G)$. In this paper, we provide an upper bound on the double vertex-edge domination number of trees in terms of the order $n$, the number of leaves and support vertices, and we characterize the trees attaining the upper bound. Finally, we design a polynomial time algorithm for computing the value of $\gamma_{dve}(T)$ for any trees. This gives an answer of an open problem posed in \cite{kri}.
Abstract
A vertex $v$ of a graph $G=(V,E)$ is said to $ve$-dominate every edge incident to $v$, as well as every edge adjacent to these incident edges. A set $S\subseteq V$ is called a double vertex-edge dominating set if every edge of $E$ is $ve$-dominated by at least two vertices of $S$. The minimum cardinality of a double vertex-edge dominating set of $G$ is the double vertex-edge domination number $\gamma_{dve}(G)$. In this paper, we provide an upper bound on the double vertex-edge domination number of trees in terms of the order $n$, the number of leaves and support vertices, and we characterize the trees attaining the upper bound. Finally, we design a polynomial time algorithm for computing the value of $\gamma_{dve}(T)$ for any trees. This gives an answer of an open problem posed in \cite{kri}.
참고문헌 (8)
- R. Boutrig, "Vertex-edge domination in graphs", Aequationes Math, 90(2), pp.355~366 (2016)[DOI]
- E. J. Cockayne, "A linear algorithm for the domination number of a tree", Inform. Process. Lett, 4, pp.41~44 (1975)
- S. T. Hedetniemi, "A linear algorithm for finding a minimum dominating set in a cactus", Discrete Appl. Math, 13(2-3), pp.287~292 (1986)[DOI]
- Balakrishna Krishnakumari, "Double vertex-edge domination", Discrete Mathematics, Algorithms and Applications, 09(04), pp.1750045~ (2017), World Scientific Pub Co Pte Lt[DOI]
- B. Krishnakumari, "Bounds on the vertex"edge domination number of a tree", C. R. Math. Acad. Sci. Paris, 352(5), pp.363~366 (2014)[DOI]
- J. Lewis, "Vertex-edge domination", Util. Math, 81, pp.193~213 (2010)
- J. W. Peters, "Theoretical and algorithmic results on domination and connectivity", Ph. D., pp.1986
- Y. Zhao, "On the algorithmic complexity of edge total domination", Theoret. Comput. Sci, 557, pp.28~33 (2014)[DOI]