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

Abstract

Given a graph G = ( V , E ) , not necessarily finite, a graphoidal cover of G means a collection Ψ of non-trivial paths in G called Ψ -edges, which are not necessarily open (not necessarily finite), such that every vertex of G 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 G = ( V , E ) is denoted by G G and for a given Ψ ∈ G G the ordered pair ( G , Ψ ) is called a graphoidally covered graph.Two vertices u and v of G are Ψ -adjacent if they are the ends of an open Ψ -edge. A set D of vertices in ( G , Ψ ) is Ψ -independent if no two vertices in D are Ψ -adjacent and is said to be Ψ -dominating if every vertex of G is either in D or is Ψ -adjacent to a vertex in D ; G is γ Ψ ( G ) -definable ( γ i Ψ ( G ) -definable) if ( G , Ψ ) has a finite Ψ -dominating ( Ψ -independent Ψ -dominating) set. Clearly, if G is γ i Ψ ( G ) -definable, then G is γ Ψ ( G ) -definable and γ Ψ ( G ) ≤ γ i Ψ ( G ) . Further if for any graphoidal cover Ψ of G such that γ Ψ ( G ) = γ i Ψ ( G ) then we call Ψ as a least-kernel graphoidal cover of G (in short, an LKG cover of G ). 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 Δ ≤ 6 possesses an LKG cover, we were able to show that every finite graph with Δ ≤ 3 is indeed an LKG graph. Keywords: Domination, Graphoidal cover, Least-kernel graphoidal cover