- Title
- On chromatic transversal domination in graphs
- Creator
- Arumugam, S.; Raja Chandrasekar, K.
- Relation
- Journal of Combinatorial Mathematics and Combinatorial Computing Vol. 83, p. 13-21
- Relation
- http://www.combinatorialmath.ca/jcmcc/jcmcc83.html
- Publisher
- Charles Babbage Research Centre
- Resource Type
- journal article
- Date
- 2012
- Description
- Let G = (V, E) be a graph with chromatic number k. A dominating set D of G is called a chromatic transversal dominating set (ctdset) if D intersects every color class of any k-coloring of G. The minimum cardinality of a ctd-set of G is called the chromatic transversal domination number of G and is denoted by γct(G). In this paper we obtain sharp upper and lower bounds for γct for the Mycielskian μ(G) and the shadow graph Sh(G) of any graph G. We also prove that for any c ≥ 2, the decision problem corresponding to 7ct is NP-hard for graphs with x(G) = c.
- Subject
- domination; coloring; chromatic transversal domination
- Identifier
- http://hdl.handle.net/1959.13/1336000
- Identifier
- uon:27527
- Identifier
- ISSN:0835-3026
- Language
- eng
- Reviewed
- Hits: 808
- Visitors: 783
- Downloads: 0
Thumbnail | File | Description | Size | Format |
---|