Convex Bipartite Graphs and Bipartite Circle Graphs

Takashi KIZU; Yasuchika HARUTA; Toshiro ARAKI; Toshinobu KASHIWABARA

Convex Bipartite Graphs and Bipartite Circle Graphs

Takashi KIZU, Yasuchika HARUTA, Toshiro ARAKI, Toshinobu KASHIWABARA

Full Text Views

0

Share
Cite this

Summary :

Let G = (A, B, E) be a bipartite graph with bipartition (A:B) of vertex set and edge set E. For each vertex v, Γ(v) denotes the set of adjacent vertices to v. 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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E81-A No.5 pp.789-795

Publication Date: 1998/05/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Takashi KIZU, Yasuchika HARUTA, Toshiro ARAKI, Toshinobu KASHIWABARA, "Convex Bipartite Graphs and Bipartite Circle Graphs" in IEICE TRANSACTIONS on Fundamentals, vol. E81-A, no. 5, pp. 789-795, May 1998, doi: .
Abstract: Let G = (A, B, E) be a bipartite graph with bipartition (A:B) of vertex set and edge set E. For each vertex v, Γ(v) denotes the set of adjacent vertices to v. 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.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/e81-a_5_789/_p

Copy

@ARTICLE{e81-a_5_789,
author={Takashi KIZU, Yasuchika HARUTA, Toshiro ARAKI, Toshinobu KASHIWABARA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Convex Bipartite Graphs and Bipartite Circle Graphs},
year={1998},
volume={E81-A},
number={5},
pages={789-795},
abstract={Let G = (A, B, E) be a bipartite graph with bipartition (A:B) of vertex set and edge set E. For each vertex v, Γ(v) denotes the set of adjacent vertices to v. 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.},
keywords={},
doi={},
ISSN={},
month={May},}

Copy

TY - JOUR
TI - Convex Bipartite Graphs and Bipartite Circle Graphs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 789
EP - 795
AU - Takashi KIZU
AU - Yasuchika HARUTA
AU - Toshiro ARAKI
AU - Toshinobu KASHIWABARA
PY - 1998
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E81-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 1998
AB - Let G = (A, B, E) be a bipartite graph with bipartition (A:B) of vertex set and edge set E. For each vertex v, Γ(v) denotes the set of adjacent vertices to v. 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.
ER -