IJPAM: Volume 87, No. 6 (2013)

ON THE ACHROMATIC NUMBER OF SILICATE NETWORKS

Sharmila Mary Arul
Department of Mathematics
Jeppiaar Engineering College
Chennai, 600119, INDIA


Abstract. The silicates are the largest, the most interesting and the most complicated class of minerals by far. The basic chemical unit of silicates is the $(SiO_{4})$ tetrahedron. A silicate sheet is a ring of tetrahedrons which are linked by shared oxygen nodes to other rings in a two dimensional plane that produces a sheet-like structure. We consider the silicate sheet as a fixed interconnection parallel architecture and call it a silicate network. The achromatic number for a graph $G $= $(V, E)$ is the largest integer $m$ such that there is a partition of $V$ into disjoint independent sets $(V_{1},...,V_{m})$ satisfying the condition that for each pair of distinct sets $V_{i}$ , $V_{j}$ , $V_{i}$ $\cup$ $V_{j}$ is not an independent set in $G $. In this paper, we determine an approximation algorithm for the achromatic number of Silicate Network which is $NP$ complete even for trees.

Received: September 6, 2013

AMS Subject Classification: 05C15, 05C85

Key Words and Phrases: silicate networks, achromatic number, approximation algorithms, $NP$-completeness, graph algorithms

Download paper from here.



DOI: 10.12732/ijpam.v87i6.6 How to cite this paper?
Source:
International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2013
Volume: 87
Issue: 6