Domination in graphoidally covered graphs: Least-kernel graphoidal graphs-II. Issue 1 (1st April 2018)

• Record Type: Journal Article
• Authors: Gupta, Purnima; Singh, Rajesh
• Is Part Of: AKCE International Journal of Graphs and Combinatorics. Volume 15:Issue 1(2018)
• Page Start: 63
• Page End: 71
• Publication Date: 2018-04-01
• Subjects: Domination -- Graphoidal cover -- Least-kernel graphoidal cover
• DOI: 10.1016/j.akcej.2018.01.002
• Languages: English
• ISSNs: 0972-8600

Abstract

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.