Signed clique-transversal functions in graphs
Haichao Wang, Liying Kang, Erfang Shan · International Journal of Computer Mathematics · 2010
A function f: V→{−1,+1}, defined on the vertices of a graph G, is a signed clique-transversal function (SCTF) if ∑ u∈V(C) f(u)≥1 for every clique C of G. The weight of an SCTF is w(f)=∑ v∈V(G) f(v). The signed clique-transversal number, denoted , is the minimum weight of an SCTF of G. The signed clique-transversal problem is to find an SCTF of minimum weight for G. In this paper, we establish a tight lower bound on the signed clique-transversal number for a regular graph with clique number at most 4. Furthermore, we show that the decision problem corresponding to the problem of computing is NP-complete even when restricted to doubly chordal graphs. Also, we prove that the signed clique-transversal problem can be solved in linear time for a strongly chordal graph if its strong elimination ordering is given.