zbMATH — the first resource for mathematics

The algorithmic complexity of the minus clique-transversal problem. (English) Zbl 1125.05076
A minus clique-transversal function, MCTF for short, of a graph \(G=(V,E)\) is a function \(f:V\rightarrow \{-1,0,1\}\) such that \(\sum_{u\in V(C)}f(u)\geq 1\) for every clique \(C\) in \(G\). The weight of an MCTF \(f\) is \(\sum_{v\in V}f(v)\). The minus clique-transversal number of a graph \(G\) equals the minimum weight of an MCTF of \(G\). The upper minus clique-transversal number of a graph \(G\) equals to the maximum weight of a minimal MCTF of \(G\).

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI
[1] Aho, A.V.; Hopcropt, J.E.; Ullman, J.D., The design and analysis of computer algorithms, (1974), Addison-Wesley Reading, MA
[2] M. Aigner, T. Andreae, Vertex-sets that meet all maximal cliques of a graph, 1986.
[3] Andreae, T., On the clique-transversal number of chordal graphs, Discrete math., 191, 3-11, (1998) · Zbl 0955.05058
[4] Andreae, T.; Schughart, M.; Tuza, Z., Clique-transversal sets of line graphs and complements of line graphs, Discrete math., 88, 11-20, (1991) · Zbl 0734.05077
[5] Balachandhran, V.; Nagavamsi, P.; Pandu Ragan, C., Clique transversal and clique independence on comparability graphs, Inform. process. lett., 58, 181-184, (1996)
[6] Bondy, J.A.; Murty, U.S.R., Graph theory with applications, (1976), Elsevier North Holland · Zbl 1134.05001
[7] Chang, M.S.; Chen, Y.H.; Chang, G.J.; Yan, J.H., Algorithmic aspects of the generalized clique-transversal problem on chordal graphs, Discrete appl. math., 66, 189-203, (1996) · Zbl 0854.68072
[8] Dahlhaus, E.; Mannuel, P.D.; Miller, M., Maximum h-colourable subgraph problem in balanced graphs, Inform. process. lett., 65, 301-303, (1998) · Zbl 1338.68098
[9] Dunbar, J.; Goddard, W.; Hedetniemi, S.; McRae, A.; Henning, M.A., The algorithmic complexity of minus domination in graphs, Discrete appl. math., 68, 73-84, (1996) · Zbl 0848.05041
[10] Durán, G.; Lin, M.C., On clique-transversals and clique-independent sets, Ann. oper. res., 116, 71-77, (2002) · Zbl 1013.90107
[11] Erdős, P.; Galli, T.; Tuza, T., Covering the cliques of a graph with vertices, Discrete math., 108, 279-289, (1992) · Zbl 0766.05063
[12] Garey, M.R.; Johnson, D.S., Computers and intractability—A guide to the theory of NP-completeness, (1979), Freeman San Francisco, CA · Zbl 0411.68039
[13] Guruswami, V.; Rangan, C.P., Algorithmic aspects of clique-transversal and clique-independent sets, Discrete appl. math., 100, 183-202, (2000) · Zbl 0948.68135
[14] Henning, M.A., Dominating function in graphs, Domination in graphs: advanced topics, vol. II, (1998), Marcel Dekker Inc. New York
[15] Kang, Liying; Qiao, Hong; Shan, Erfang; Du, Dingzhu, Lower bounds on the minus domination and k-subdomination numbers, Theor. comput. sci., 296, 89-98, (2003) · Zbl 1046.68078
[16] Lai, F.; Chang, G.J., An upper bound for the transversal numbers of 4-uniform hypergraphs, J. combin. theory ser. B, 50, 129-133, (1990) · Zbl 0739.05068
[17] Lee, C.M.; Chang, M.S., Distance-hereditary graphs are clique-perfect, Discrete appl. math., 154, 525-536, (2006) · Zbl 1110.68108
[18] Poljak, S., A note on stable sets and colourings of graphs, Comment. math. univ. carolin, 15, 307-309, (1974) · Zbl 0284.05105
[19] Prisner, E., Graphs with few cliques, (), 945-956 · Zbl 0844.05062
[20] Tuza, Z., Covering all cliques of a graph, Discrete math., 86, 117-126, (1990) · Zbl 0744.05040
[21] G. Xu, E. Shan, M. Zhao, Clique domination in graphs, ARS Combin, in press. · Zbl 1249.05301
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.