Advances and Applications in Discrete Mathematics
Volume 10, Issue 1, Pages 1 - 22
(July 2012)
|
|
PARTITION OF A GRAPH WITH ITS COMPLETE SUB-GRAPHS
K. Manjunatha Prasad, G. Sudhakara and H. S. Sujatha
|
Abstract: A fundamental result regarding the characterization of a bipartite graph is “vertex set V of a graph can be partitioned into two subsets of vertices and such that no two vertices from same set are at distance one (bipartite graph) if and only if given graph has no cycle of odd length”. In this paper, we consider the class of all graphs with a partition for the set vertices, if exists, such that no two vertices from same set are at distance two (call it a (2, 2) bipartite graph) and obtain a characterization for such graphs. This characterization reveals that each set in the partition has sub-partitions such that each set in the sub- partition induces complete sub-graphs and this result has significance in providing a stable network. Also, analogue to the observation that a cycle (whenever exists) is of even length in the case of a bipartite graph, here in the case of (2, 2) bipartite graph, we find that an induced cycle,if exists,is a triangle or of length 4k, for some integer k. |
Keywords and phrases: bipartite graph, bipartition, induced complete sub-graph. |
|
Number of Downloads: 220 | Number of Views: 514 |
|