MIXED GRAPH REPRESENTATION AND MIXED GRAPH ISOMORPHISM

Abstract

Mixed graph is a graph containing oriented as well as un-oriented set of edges. The structural information conveyed by mixed graph is basically information where the edges of the graph are representations of roads, cables, telephone lines and other structures while the vertices are representations of high way intersections/squares, computers, telephone outlet and others. In this paper results related to degreesof vertices, numbers of edges, adjacency matrix representation of mixed graphshave been introduced and illustrated. These results and notations have alsobeen used to formulate a relationship between degrees of vertices and number of edges in a mixed graph as well as to prove that a set of isomorphic mixedgraphs is an equivalence relation. It is, therefore, hoped that these results are helpful for further studies of graph theory, and specifically in the studyof mixed graph.

Keywords

• Directed graphs,Undirected graphs,Mixed graph,Degree of vertex,Number of edges,Graph representation,Graph isomorphism.