Abstract
A function f: V→<texlscub>−1,+1</texlscub>, defined on the vertices of a graph G, is a signed maximum-clique transversal function if ∑
u∈V(Q)
f(u)≥1 for each maximum clique Q of G. The weight of a signed maximum-clique transversal function is w(f)=∑
v∈V(G)
f(v). The signed maximum-clique transversal number of G, denoted by , is the minimum weight of a signed maximum-clique transversal function of G. In this paper, we establish a tight lower bound on
for an arbitrary graph G and an upper bound on
for a k-regular graph G with ω(G)=k, and we characterize the extremal graphs achieving the upper bound. Meanwhile, we establish a lower bound on
for a connected claw-free cubic graph, and characterize the extremal graphs achieving the lower bound. For a connected claw-free 4-regular graph G with ω(G)=3, we present sharp bounds on
and characterize the extremal graphs achieving the lower bound.
Acknowledgements
The authors would like to thank the anonymous referees for valuable comments. This research was partially supported by the National Nature Science Foundation of China (Nos. 10971131, 11171207) and Shanghai Leading Academic Discipline Project (No. S30104).