The signed maximum-clique transversal number of regular graphs

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.

Keywords:

• maximum-clique transversal set
• signed maximum-clique transversal number
• regular graph
• claw-free

2010 AMS Subject Classification :

• 05C65
• 05C69
• 05C75

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).