Domination in Graphoidally Covered Graphs: Least-Kernel Graphoidal Covers

Given a graph G=(V,E)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)G=(V,E) is denoted by GGGG and for a given Ψ∈GGΨ∈GG 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)γΨ(G)-definable (γiΨ(G)γiΨ(G)-definable) if (G, Ψ) has a finite Ψ-dominating (Ψ-independent Ψ-dominating) set. Clearly, if G   is γiΨ(G)γiΨ(G)-definable, then G   is γΨ(G)γΨ(G)-definable and γΨ(G)≤γiΨ(G)γΨ(G)≤γiΨ(G). Further if for a graphoidal cover Ψ of G  , γΨ(G)=γiΨ(G)γΨ(G)=γiΨ(G) then we call Ψ as a least-kernel graphoidal cover of G (in short, an LKG cover of G  ). A natural question arises: “Does every graph possess an LKG cover?” We firstly exhibit that not every graph possesses an LKG cover and thereafter, in the quest to find graphs possessing an LKG cover, we proved that every finite tree and every finite unicyclic graph admits an LKG cover. We further extend Allan Laskar theorem to infinite graphs by showing every γ(G)γ(G)-definable infinite claw free graph has an LKG cover.