21-05-2014, 04:37 PM
SUPER STRONGLY PERFECT NESS OF SOME INTERCONNECTION NETWORKS
SUPER STRONGLY PERFECT .pdf (Size: 125.94 KB / Downloads: 31)
Abstract
A Graph G is Super Strongly Perfect Graph if every induced sub graph H of G possesses a minimal
dominating set that meets all the maximal complete sub graphs of H. In this paper we have analyzed the
structure of super strongly perfect graphs in some Interconnection Networks, like Mesh, Torus, Hyper cubes and
Grid Networks. Along with this investigation, we have characterized the Super Strongly Perfect ness in Mesh,
Torus, Hyper cubes and Grid Networks. Also we have given the relationship between diameter, domination and
co - domination numbers of Mesh, Torus, Hyper cubes and Grid Networks.
Introduction
Graph theoretical concepts are widely used to study and model various applications, in different areas.
They include, study of molecules, construction of bonds in chemistry and the study of atoms, sociology, biology
and conservation efforts (where a vertex represents regions where certain species exist and the edges represent
migration path or movement between the regions). The major role of graph theory in computer applications is
the development of graph algorithms. Numerous algorithms are used to solve problems that are modeled in the
form of graphs [Shrinivas, et. al. (2010)]. Also, graph theory is used in research areas of computer science such
as data mining, image segmentation, clustering, image capturing, networking etc., Graph theoretical concepts
are widely used in Operations Research (the travelling salesman problem, problems of scheduling, etc.,),
Networks (PERT - Project Evaluation Review Technique, CPM - Critical Path Method).
An interconnection network plays a central role in determining the overall performance of a multicomputer
system. If the network cannot provide adequate performance, for a particular application, nodes will frequently
be forced to wait for data to arrive. Some of the most important networks include Mesh, Rings, Hypercube,
Butterfly, Benes and Cube Connected Cycles etc., [Xiao and Parhami (2005)]. The interconnection network
connects the processors of a parallel and distributed system. The topology of an interconnection network for a
parallel and distributed system can always be represented by a graph, where each vertex represents a processor
and each edge represents a vertex - to - vertex communication link. Communication is a critical issue in the
design of a parallel and distributed system [Huang, et. al. (2008)].
Basic Concepts
In this paper, graphs are finite and simple, that is, they have no loops or multiple edges. Let G = (V, E) be a
graph where V is the vertex set and E is the edge set. A maximal complete sub graph (i.e., clique) is a set of
vertices every pair of which are adjacent. A subset D of V (G) is called a dominating set if every vertex in V - D
is adjacent to at least one vertex in D. A subset S of V is said to be a minimal dominating set if S - {u} is not a
dominating set for any u ∈ S. The domination number γ (G) of G is the smallest size of a dominating set of G.
The domination number of its complement G is called the co - domination number of G and is denoted by γ (G)
or simply γ. A shortest u - v path of a connected graph G is often called a geodesic. The diameter denoted by
diam (G) is the length of any longest geodesic. A vertex v of degree zero in G is called an isolated vertex of G.
Conclusion
We have analyzed the structure of Super Strongly Perfect Graph in Mesh, Torus, Hyper cubes and Grid
Networks. We have presented the characterization of Super Strongly Perfect graphs in Mesh, Torus, Hyper
cubes and Grid Networks. Also we have investigated the relationship between diameter, domination and co -
domination numbers of Mesh, Torus, Hyper cubes and Grid Networks. In future, these investigations will be
extended to the remaining well known architectures.