DIKUL - logo
E-viri
Celotno besedilo
Recenzirano Odprti dostop
  • On some subclasses of inter...
    Paul, Sanchita; Ghosh, Shamik

    Electronic journal of graph theory and applications, 01/2022, Letnik: 10, Številka: 1
    Journal Article

    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  (Iv, pv) ) in such a way that  uv ∈ E  if and only if  pv ∈ Iu . 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  pv  is the mid-point  Iv  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.