id: 05722015
dt: j
an: 05722015
au: Lee, Chuan-Min; Chang, Maw-Shang
ti: Signed and minus clique-transversal functions on graphs.
so: Inf. Process. Lett. 109, No. 8, 414-417 (2009).
py: 2009
pu: Elsevier Sciences Publishers (North-Holland), Amsterdam
la: EN
cc: 
ut: graph algorithms; minus clique-transversal functions; strongly chordal
    graphs; planar graphs
ci: 
li: doi:10.1016/j.ipl.2008.12.019
ab: Summary: A minus (respectively, signed) clique-transversal function of a
    graph $G=(V,E)$ is a function $f: V \to \{-1, 0. 1\}$ (respectively,
    $\{-1,1\}$) such that $\sum _{u \in C}f(u) \geqslant 1$ for every
    maximal clique $C$ of $G$. The weight of a minus (respectively, signed)
    clique-transversal function of $G$ is $f(V)=\sum _{v \in V}f(v)$. The
    minus (respectively, signed) clique-transversal problem is to find a
    minus (respectively, signed) clique-transversal function of $G$ of
    minimum weight. In this paper, we present a unified approach to these
    two problems on strongly chordal graphs. Notice that trees, block
    graphs, interval graphs, and directed path graphs are subclasses of
    strongly chordal graphs. We also prove that the signed
    clique-transversal problem is NP-complete for chordal graphs and planar
    graphs.
rv: