On some subclasses of interval catch digraphs
Abstract
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.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2022.10.1.10
References
J. Bang-Jensen and G. Z.Gutin, Digraphs, Springer Monographs in Mathematics, 2008.
A. Basu, S. Das, S. Ghosh and M. Sen, Circular-arc bigraphs and its subclasses, J. Graph Theory 73 (2013), 361–376. https://doi.org/10.1002/jgt.21681
K. P. Bogart and D. B. West, A Short Proof that Proper = Unit, Discrete Mathematics 201 (1999), 21–23. https://arxiv.org/pdf/math/9811036.pdf
E. Ceyhan, Domination number of an interval catch digraph family and its use for testing uniformity, Statistics 54 (2020), 310–339. https://doi.org/10.1080/02331888.2020.1720020
E. Ceyhan, Density of a random interval catch digraph family and its use for testing uniformity, REVSTAT 14 (2016), 349-–394.
E. Ceyhan, The distribution of the relative arc density of a family of interval catch digraph based on uniform data, Metrika 75 (2012), 761-–793. https://doi.org/10.1007/s00184-011-
-y
A. Das, S. Das, and M. Sen, Forbidden substructure for interval digraphs/bigraphs, Discrete Math. 339 (2016), 1028-–1051. https://doi.org/10.1016/j.disc.2015.10.010
M. C. Golumbic, Algorithmic graph theory and perfect graphs, Annals of Disc. Math. 57, Elsevier Sci., USA, 2004.
P. Hell, R. Shamir, and R. Sharan, A fully dynamic algorithm for recognizing and representing proper interval graphs, SIAM J. Comput. 31 (2001), 289—305. https://doi.org/10.1137/S0097539700372216
P. Looges and S. Olariu, Optimal greedy algorithms for indifference graphs, Comput. Math. Appl. 25 (1993), 15-–25. https://doi.org/10.1016/0898-1221(93)90308-I
H. Maehara, A Digraph Represented by a Family of Boxes or Spheres, J. Graph Theory 8 (1984), 431–439. https://doi.org/10.1002/jgt.3190080312
D. S. Malik, M. K. Sen, and S. Ghosh, Introduction to Graph Theory, Cengage Learning Asia Pte Ltd, Singapore, 2014. 172
C. Priebe, D. J. Marchette, J. G. DeVinney and D. A. Socolinsky, Classification using class cover catch digraphs, Journal of Classification 20 (2003), 3-–23. https://doi.org/10.1007/s00357-003-0003-7
E. Prisner, A Characterization of Interval Catch Digraphs, Discrete Mathematics 73 (1989), 285-289. https://doi.org/10.1016/0012-365X(89)90271-9
M. Sen, S. Das, A. B. Roy and D. B. West, Interval digraphs: An analogue of interval graphs, J Graph Theory 13 (1989), 189–202. https://doi.org/10.1002/jgt.3190130206
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.