IJPAM: Volume 91, No. 1 (2014)

$\tau_c$-SETS IN A TREE

P. Jayaprakash$^1$, V. Swaminathan$^2$
$^1$Research and Development Centre
Bharathiyar University
Coimbatore, 641046, Tamilnadu, INDIA
$^2$Ramanujan Research Centre in Mathematics
Saraswathi Narayanan College
Madurai-625018, Tamilnadu, INDIA

Abstract. Let $G$ be a simple graph. A subset $S$ of $V(G)$ is called a clique transversal set of $G$ if $S$ intersects every clique of $G$. (That is every maximal complete subgraph of $G$). The minimum cardinality of a clique transversal set of $G$ is called the clique traversal number of $G$ and is denoted by $\tau_c(G)$. Any clique transversal set of $G$ is a dominating set of $G$. Also $\gamma(G) \leq \tau_c(G)$. In this paper we characterize trees $T$ those $\tau_c(T)=\gamma(T)$ and for which $\tau_c(T)=\gamma(T)+1$. We also prove that $\tau_c(T)=n-\Delta(T)$ if and only if $T$ is a wounded spider.

Received: October 24, 2013

AMS Subject Classification: 05C69

Key Words and Phrases: clique transversal sets, clique transversal number

Download paper from here.

DOI: 10.12732/ijpam.v91i1.5 How to cite this paper?
International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2014
Volume: 91
Issue: 1