Domination in graphoidally covered graphs: Least-kernel graphoidal graphs-II

Abstract

Given a graph , not necessarily finite, a graphoidal cover of means a collection of non-trivial paths in called -edges, which are not necessarily open (not necessarily finite), such that every vertex of is an internal vertex of at most one path in and every edge of G is in exactly one path in . The set of all graphoidal covers of a graph is denoted by and for a given the ordered pair is called a graphoidally covered graph. Two vertices and of are -adjacent if they are the ends of an open -edge. A set of vertices in is -independent if no two vertices in are -adjacent and is said to be -dominating if every vertex of is either in or is -adjacent to a vertex in ; is -definable (-definable) if has a finite -dominating (-independent -dominating) set. Clearly, if is -definable, then is -definable and . Further if for any graphoidal cover of such that then we call as a least-kernel graphoidal cover of (in short, an LKG cover of ). A graph is said to be a least kernel graphoidal graph or simply an LKG graph if it possesses an LKG cover. This paper is based on a conjecture by Dr. B.D Acharya, “Every graph possesses an LKG cover”. After finding an example of a graph which does not possess an LKG cover, we obtain a necessary condition in the form of forbidden subgraph for a graph to be a least kernel graphoidal graph. We further prove that the condition is sufficient for a block graph with a unique nontrivial block. Thereafter we identify certain classes of graphs in which every graph possesses an LKG cover. Moreover, following our surmise that every graph with possesses an LKG cover, we were able to show that every finite graph with is indeed an LKG graph.

Keywords

• domination
• graphoidal cover
• least-kernel graphoidal cover