On some subclasses of interval catch digraphs

Electronic Journal of Graph Theory and Applications

Sanchita Paul¹  Shamik Ghosh¹ 

[1] Department of Mathematics, Jadavpur University, Kolkata - 700032, India.;

关键词: interval catch digraph, interval graph, proper interval graph, oriented graph, tournament;   

DOI  :  10.5614/ejgta.2022.10.1.10

来源: DOAJ

【 摘 要 】

A digraph G = (V, E) is an interval catch digraph if for each vertex v ∈ V, one can associate an interval on real line and a point within it (say (I_v, p_v)) in such a way that uv ∈ E if and only if p_v ∈ I_u. It was introduced by Maehara in 1984. It has many applications in real world situations like networking and telecommunication. In his introducing paper Maehara proposed a conjecture for the characterization of central interval catch digraph (where p_v is the mid-point I_v for each v ∈ V) in terms of forbidden subdigraphs. In this paper, we disprove the conjecture by showing counter examples. Also we characterize this digraph by defining a suitable mapping from the vertex set to the real line. We study oriented interval catch digraphs and characterize an interval catch digraph when it is a tournament. Finally, we characterize a proper interval catch digraph and establish relationships between these digraph classes.

【 授权许可】

Unknown