Mathematics – General Mathematics
Scientific paper
2005-04-27
Mathematics
General Mathematics
17 pages. A full rivision is carried out. Typos corrected
Scientific paper
In this paper we develop two characterizations for the isomorphism of graphs. The first characterization is obtained by associating certain bitableaux with the graphs, which are the usual adjacency and incidence matrices used in the matrix representation of graphs expressed in a bi-tabular form. We order these bitableaux by suitably defined lexicographic order and denote the bitableau that is least in this order as the standard representation for the associated graph. The standard representation characterizes the graph uniquely. The second characterization is obtained in terms of associated rooted, unordered, pseudo trees. We show that the isomorphism of two given graphs is implied by the isomorphism of their associated pseudo trees. We discuss in brief the complexity of these characterizations described in this paper for deciding isomorphism of graphs. Finally, we discuss the k-clique problem in the light of these characterizations towards the end of the paper.
No associations
LandOfFree
On Isomorphism of Graphs and the k-clique Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Isomorphism of Graphs and the k-clique Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Isomorphism of Graphs and the k-clique Problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-613224