Find in Library

Given a graph G=(V,E), a set ψ of non-trivial paths, which are not necessarily open, called ψ-edges, is called a graphoidal cover of G if it satisfies the following conditions: (GC−1) Every vertex of G is an internal vertex of at most one path in ψ, and (GC−2) every edge of G is in exactly one path in ψ; 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 ψ-dominating (in short ψ-dom set) if every vertex of G is either in D or is ψ-adjacent to a vertex in D. Let γψ(G)=inf{|D|:Disaψ−domsetofG}. A ψ-dom set D with |D|=γψ(G) is called a γψ(G)-set. The graphoidal domination number of a graph G denoted by γψ0(G) is defined as   inf{γψ(G):ψ∈GG}. Let G be 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)=1 and l(P)>1 for each P∈ψ and in this process we prove that the only such graphoidal covers are such that l(P)=2 for each P∈ψ.