Vertices Belonging to all or to no Minimum Vertex-Edge Dominating Sets in Trees
- PDF / 235,692 Bytes
- 6 Pages / 439.642 x 666.49 pts Page_size
- 60 Downloads / 177 Views
Vertices Belonging to all or to no Minimum Vertex-Edge Dominating Sets in Trees Hari Naresh Kumar1 · Yanamandram B. Venkatakrishnan1 Received: 23 March 2019 / Accepted: 25 May 2020 / © Vietnam Academy of Science and Technology (VAST) and Springer Nature Singapore Pte Ltd. 2020
Abstract Let G be a simple graph with vertex set V (G) and edge set E(G). A vertex v ∈ V (G) vertex-edge dominates every edge uv incident to v, as well as every edge adjacent to these incident edges. A set D ⊆ V (G) is a vertex-edge dominating set if every edge of E(G) is vertex-edge dominated by a vertex of D. The vertex-edge dominating set of a minimum cardinality is called minimum vertex-edge dominating set. In this paper, we characterize the set of vertices that are in all or in no minimum vertex-edge dominating sets in trees. Keywords Vertex-edge domination · Vertex-edge domination number · Trees Mathematics Subject Classification (2010) 05C69
1 Introduction Let G = (V , E) be a simple connected graph. For every vertex v ∈ V , the open neighborhood NG (v) is the set {u ∈ V (G) : uv ∈ E}, and the degree of v is deg(v) = |NG (v)|. The closed neighborhood of v is denoted by NG [v], defined as NG [v] = NG (v) ∪ {v}. We denote by Pn , a path of order n. The distance dist(u, v) between two vertices u and v in a connected graph is the number of edges in a shortest path between them. A closed path is a cycle. A tree is a connected graph that contains no cycle. For a set S ⊆ V , the subgraph of G induced by S is defined as G[S] = (S, ES ), where ES = {xy : xy ∈ E(G), x, y ∈ S}. An edge e ∈ E(G) is vertex-edge dominated by a vertex v ∈ V (G) if e is incident with v, or e is incident with a vertex adjacent to v. A subset D ⊆ V (G) is an vertex-edge dominating set, abbreviated VEDS, of G if every edge of G is vertex-edge dominated by an edge of D. The vertex-edge domination number of G, denoted by γve (G), is the minimum cardinality of a vertex-edge dominating set of G. A vertex-edge dominating set of G of Yanamandram B. Venkatakrishnan
[email protected] Hari Naresh Kumar [email protected] 1
Department of Mathematics, School of Arts, Science, Humanities, SASTRA Deemed University, Thanjavur, Tamil Nadu, 613 401, India
H.N. Kumar, Y.B. Venkatakrishnan
minimum cardinality is called a γve (G)-set. The concept of vertex-edge domination was introduced by Peters [6] and further studied by [2, 4, 5]. Bilida et al. [1] (Henning et al. [3]) have characterized the vertices belonging to all or to no minimum double(semi-total) dominating set in a tree. In this paper, we investigate vertices belonging to all or to no minimum vertex-edge dominating set in a tree. For a tree T , we define the sets Ave (T ) and Nve (T ) as follows:
Ave (T ) = {v ∈ V (T ) | v is in every γve (T )-set}, Nve (T ) = {v ∈ V (T ) | v is in no γve (T )-set}. The vertex with degree at least three is called branch vertex. The set B(T ) denotes the set of all branch vertices of tree T . A leaf is a vertex with degree one and the set L(T ) denotes set of all leaves
Data Loading...
