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.
Original language | English |
---|---|
Pages (from-to) | 1410-1418 |
Number of pages | 9 |
Journal | Applied Mathematics and Computation |
Volume | 189 |
Issue number | 2 |
DOIs | |
Publication status | Published - 15 Jun 2007 |
Keywords
- Algorithm
- Block graph
- Clique-transversal set
- Minus clique-transversal function
ASJC Scopus subject areas
- Applied Mathematics
- Computational Mathematics
- Numerical Analysis