期刊名称：AKCE International Journal of Graphs and Combinatorics
印刷版ISSN：0972-8600
出版年度：2015
卷号：12
期号：2-3
页码：133-140
DOI：10.1016/j.akcej.2015.11.007
语种：English
出版社：Elsevier
摘要：AbstractGiven a graphG=(V,E), a setψof non-trivial paths, which are not necessarily open, calledψ-edges, is called agraphoidal cover ofGif it satisfies the following conditions:(GC−1)Every vertex ofGis an internal vertex of at most one path inψ, and(GC−2)every edge ofGis in exactly one path inψ; the ordered pair(G,ψ)is called agraphoidally covered graph. Two verticesuandvofGareψ-adjacentif they are the ends of an openψ-edge. A setDof vertices in(G,ψ)isψ-dominating (in shortψ-dom set)if every vertex ofGis either inDor isψ-adjacent to a vertex inD. Letγψ(G)=inf{|D|:Disaψ−domsetofG}. Aψ-dom setDwith|D|=γψ(G)is called aγψ(G)-set. Thegraphoidal domination number of a graphGdenoted byγψ0(G)is defined as inf{γψ(G):ψ∈GG}. LetGbe a connected graph with cyclomatic numberμ(G)=(q−p+1). In this paper, we characterize graphs for which there exists a non-trivial graphoidal coverψsuch thatγψ(G)=1andl(P)>1for eachP∈ψand in this process we prove that the only such graphoidal covers are such thatl(P)=2for eachP∈ψ.
