International Journal of Advanced Networking and Applications

A. Ashok Kumar ¹, S. Athisayanathan ², A. Antonysamy ³

Affiliations
1 Department of Computer Science, Alagappa Government Arts College, Karaikudi - 630003, IN
2 Research Department of Mathematics, St. Xavier’s College (Autonomous), Palayamkottai − 627002, IN
3 Ananda College, Devakottai, IN

Abstract

In this paper, we introduce algorithms to find the vertex-to-clique (or (V, ζ ))-distance d(v, C ) between a vertex v and a clique C in a graph G, (V, ζ )-eccentricity e1 (v) of a vertex v, and (V, ζ )-center Z1(G) of a graph G usingBC - representation. Moreover, the algorithms are proved for their correctness and analyzed for their time complexity.

Keywords

Clique, Distance, Eccentricity, Radius, Center, Binary Count.

Full Text

   

A. Ashok Kumar ¹, S. Athisayanathan ², A. Antonysamy ³

Affiliations
1 Department of Computer Science, Alagappa Government Arts College, Karaikudi – 630003, IN
2 Research Department of Mathematics, St. Xavier’s College(Autonomous), Palayamkottai – 627002, IN
3 Ananda College, Devakottai, IN

Abstract

Let V = {1, 2, 3, …, n} be the vertex set of a graph G, ℘ (V) the powerset of V and A ∈ ℘ (V ). Then A can be represented as an ordered n-tuple (x₁x₂x₃…x_n) where x_i = 1 if i ∈ A, otherwise x_i = 0 (1≤ i ≤ n). This representation is called binary count (or BC) representation of a set A and denoted as BC(A). Given a graph G of order n, every integer m in S = {0, 1, 2, …, 2ⁿ-1} corresponds to a subset A of V and vice versa. In this paper we introduce and discuss a sequential algorithm to find the clique graph K(G) of a graph G using the BC representation.

Keywords

Binary Count, Clique, Clique Graph, Powerset.

Full Text

   

A. Ashok Kumar ¹, S. Athisayanathan ², A. Antonysamy ²

Affiliations
1 Department of Computer Science, St. Xavier’s College (Autonomous), Palayamkottai-627002, IN
2 Research Department of Mathematics, St. Xavier’s College (Autonomous), Palayamkottai-627002, IN

Abstract

Let V={1, 2, 3, . . . , n} be the vertex set of a graph G, P(V) the powerset of V and A∈P(V). Then A can be represented as an ordered n-tuple (x₁x₂x₃ . . .x_n) where x_i=1 if i∈A, otherwise x_i=0 (1≤i≤n). This representation is called binary count (or BC) representation of a set A and denoted as BC(A). Given a graph G of order n, it is shown that every integer m in S={0, 1, 2, . . . , 2ⁿ-1} corresponds to a subset A of V and vice versa. We introduce algorithms to find a subset A of the vertex set V={1, 2, 3, . . . , n} of a graph G that corresponds to an integer m in S={0, 1, 2, . . . , 2ⁿ-1}, verify whether A is a subset of any other subset B of V and also verify whether the sub graph <A> induced by the set A is a clique or not using BC representation. Also a general algorithm to find all the cliques in a graph G using BC representation is introduced. Moreover we have proved the correctness of the algorithms and analyzed their time complexities.

Keywords

Adjacency Matrix, Binary Count, Clique, Powerset, Subset.

Full Text