Convex Bipartite Graphs and Bipartite Circle Grphs

摘要

Let G = (A, B, E) be a bipartite graph with bi- partition (A : B) of vertex set and edge set E. For each vertex υ, Γ(υ) denotes the set of adjacent vertices toυ. G is said to be t-convex on the vertex set A if there is a tree and a one-to-one correspondence between vertices in A and edges of the tree such that for each vertex b ∈ B the edges of the tree corresponding to vertices in Γ(b) form a path on the tree. G is doubly t-convex if it is convex both on vertex set A and on B. In this paper, we show that, the class of doubly t-convex graphs is exactly the class of bipartite circle graphs.