期刊名称：AKCE International Journal of Graphs and Combinatorics
印刷版ISSN：0972-8600
出版年度：2018
卷号：15
期号：1
页码：63-71
DOI：10.1016/j.akcej.2018.01.002
语种：English
出版社：Elsevier
摘要：AbstractGiven a graphG=(V,E), not necessarily finite, agraphoidal coverofGmeans a collectionΨof non-trivial paths inGcalledΨ-edges, which are not necessarily open (not necessarily finite), such that every vertex ofGis 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 graphG=(V,E)is denoted byGGand for a givenΨ∈GGthe ordered pair(G,Ψ)is called a graphoidally covered graph.Two verticesuandvofGareΨ-adjacentif they are the ends of an openΨ-edge. A setDof vertices in(G,Ψ)isΨ-independentif no two vertices inDareΨ-adjacent and is said to beΨ-dominatingif every vertex ofGis either inDor isΨ-adjacent to a vertex inD;GisγΨ(G)-definable (γiΨ(G)-definable) if(G,Ψ)has a finiteΨ-dominating (Ψ-independentΨ-dominating) set. Clearly, ifGisγiΨ(G)-definable, thenGisγΨ(G)-definable andγΨ(G)≤γiΨ(G). Further if for any graphoidal coverΨofGsuch thatγΨ(G)=γiΨ(G)then we callΨas aleast-kernel graphoidal coverofG(in short, anLKG coverofG). A graph is said to be aleast kernel graphoidal graphor simply anLKG graphif 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Δ≤6possesses an LKG cover, we were able to show that every finite graph withΔ≤3is indeed an LKG graph.
