| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4635528 | Applied Mathematics and Computation | 2007 | 9 Pages |
Abstract
A minus clique-transversal function of a graph G=(V,E) is a function f:Vâ{-1,0,1} such that âuâV(C)f(u)⩾1 for every clique C of G. The weight of a minus clique-transversal function is f(V)=âf(v), over all vertices vâV. The minus clique-transversal number of a graph G, denoted Ïc-(G), equals the minimum weight of a minus clique-transversal function of G. The upper minus clique-transversal number of a graph G, denoted Tc-(G), equals the maximum weight of a minimal minus clique-transversal function of G. In this paper, we show that the minus clique-transversal problem (respectively, upper minus clique-transversal problem) is NP-complete even when restricted to chordal graphs. On the other hand, we give a linear algorithm to solve the minus clique-transversal problem for block graphs.
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Guangjun Xu, Erfang Shan, Liying Kang, T.C.E. Cheng,