On The Outer-connected Domination,Paired Domination And Domination Of Orientations In Graphs

Domination in graphs has always been one of the most active topics in graphtheory. Based on the need of reality, numerous kinds of dominations have been raised.And they can be divided into two main parts: dominations in undirected graphs anddominations in directed graphs. Research in this paper also comes from the thinking ofreality. We discusse the influence of deleting an edge on the outer-connected dominationnumber, some kinds of variations of the paired domination, and directed graphs whichhave the same domination number with its reverse.Let G=(V, E), a set S of vertices of a graph G is an outer-connected dominatingset if every vertex in V\S is adjacent to some vertex in S and the subgraph G[V\S] isconnected. The outer-connected domination number γc(G) is the minimum size of sucha set. In this paper, we firstly establish a sharp lower bound for the outer-connecteddomination number of trees, then we give the definitions of γc-critical graphs and γc-stable graphs upon edge removal and study their relevant properties.Let G be a graph. A vertex set S V is a neighborhood paired dominating set ifthe subgraph induced by N(S), denoted as G[N(S)] has a perfect matching. A domi-nating set S is named a weakly near-paired dominating set of G if the subgraph Gw[S]weakly induced by S has a maximum matching of G. In this paper, some upper andlower bounds of the domination numbers for these dominations are given. Relationshipsbetween neighborhood paired domination and other kinds of domination such as paireddomination are raised. Moreover, an algorithm is given to find a neighborhood paireddominating set in any trees.Letâ†'G be an orientation of G obtained by replacing each edge by a directed arcwith the same ends.â†'G is denoted as its reverse obtained by reversing all the arcs ofâ†'G. γ(â†'G) is the domination number ofâ†'G. In this paper, sharp bounds for orientationâ†'G that satisfies γ(â†'G)=γ(â†'G) are given and classes of undirected graphs that admitsuch orientations are discussed. It’s claimed for paths or cycles that the diferencesof domination numbers between their orientations and corresponding reverses can bearbitrarily large.