The Diameter of an Interval Graph is Twice of its Radius

Authors: Tarasankar Pramanik, Sukumar Mondal, Madhumangal Pal

Abstract:

In an interval graph G = (V,E) the distance between two vertices u, v is de£ned as the smallest number of edges in a path joining u and v. The eccentricity of a vertex v is the maximum among distances from all other vertices of V . The diameter (δ) and radius (ρ) of the graph G is respectively the maximum and minimum among all the eccentricities of G. The center of the graph G is the set C(G) of vertices with eccentricity ρ. In this context our aim is to establish the relation ρ = δ 2  for an interval graph and to determine the center of it.

Keywords: Interval graph, interval tree, radius, center.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1330323

References:

[1] M. C. Carlisle and E. L. Loyd, On the k-coloring of intervals, LNCS, ICCI, 497 (1991) 90-101.
[2] J. Fabri, Automatic Storage Optimization, (UMI Press Ann Arbor, MI), 1982.
[3] A. Farley and A. Proskurowski, Computation of the center and diameter of Outerplanar graphs, Discrete Applied Mathematics, 2 (1980) 185-191.
[4] A. J. Goldman, MInimax location of a facility in a network, Transportation Science, 6 (1972) 407-418.
[5] M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980.
[6] A. Hashimoto and J. Stevens, Wire routing by optimizing cannel assignment within large apertures, Proc., 8th IEEE Design Automation Workshop, (1971) 155-169.
[7] J. R. Jungck, O. Dick, and A. G. Dick, Computer assisted sequencing, interval graphs and molecular evolution, Biosystem, 15 (1982) 259-273.
[8] T. Ohtsuki, H. Mori E. S. Khu, T. Kashiwabara and T. Fujisawa, One dimensional logic gate assignment and interval graph, IEEE Trans. Circuits and Systems, 26 (1979) 675-684.
[9] S. Olariu, A simple linear time algorithm for compting the center of an interval grap, International Journal of Computer Mathematics, 34 (1990) 121-128.
[10] S. Olariu, J. L. Schwing and J. Zhang, Optimal parallel algoritms for problems modeled by a family of intervals, IEEE Trans. Paralles and Distributed Systems, 3 (1992) 364-374.
[11] A. Pal and M. Pal, Interval tree and its applications, Advanced Modeling and Optimization (An Electronic International Journal), 11(3) (2009) 211-224.
[12] M. Pal, Some sequential and parallel algorithms on interval graphs, Ph.D Thesis, Indian Institute of Technology, Kharagpur, India, 1995.
[13] M. Pal and G. P. Bhattecharjee, An optimal parallel algorithm to solve the all pair shortest path problem on an interval graph, In proceeding of 3rd National Seminar on theoritical computer science, India, June (1993) 309-318.
[14] M. Pal, G. P. Bhattacharjee, Optimal sequential and parallel algorithms for computing the diameter and the center of an interval graph, International Journal of Computer Mathematics, 59 (1995) 1-13.
[15] G. Ramalingam and C. Pandu Rangan, A uni£ed approach to domination problems in interval graphs, Information Processing Letters, 27 (1988) 271-274.