Bounds on the vertex-edge domination number of a tree

Balakrishna Krishnakumari; Yanamandram B. Venkatakrishnan; Marcin Krzywkowski

Bounds on the vertex-edge domination number of a tree

Abstract

A vertex-edge dominating set of a graph $G$ is a set $D$ of vertices of $G$ such that every edge of $G$ is incident with a vertex of $D$ or a vertex adjacent to a vertex of $D$. The vertex-edge domination number of a graph $G$, denoted by $\gamma_{ve}(T)$, is the minimum cardinality of a vertex-edge dominating set of $G$. We prove that for every tree $T$ of order $n \ge 3$ with $l$ leaves and $s$ support vertices we have $(n-l-s+3)/4 \le \gamma_{ve}(T) \le n/3$, and we characterize the trees attaining each of the bounds.

Authors (3)

Balakrishna Krishnakumari
- SASTRA University Department of Mathematics
Yanamandram B. Venkatakrishnan
- SASTRA University Department of Mathematics
Marcin Krzywkowski dr inż.

Cite as

Full text

download paper

downloaded 24 times

Publication version: Accepted or Published Version
License: Copyright (2014 Académie des sciences)

full content of the article see on external site open in new tab

Keywords

VERTEX-EDGE DOMINATION

Details

Category:: Articles
Type:: artykuł w czasopiśmie wyróżnionym w JCR
Published in:: COMPTES RENDUS MATHEMATIQUE pages 363 - 366,
ISSN: 1631-073X
Language:: English
Publication year:: 2014
Bibliographic description:: Krishnakumari B., Venkatakrishnan Y., Krzywkowski M.: Bounds on the vertex-edge domination number of a tree// COMPTES RENDUS MATHEMATIQUE. -, nr. 352 (2014), s.363-366
Verified by:: Gdańsk University of Technology