The Diameter of an Interval Graph is Twice of its Radius
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.
[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.
[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.
@article{"International Journal of Engineering, Mathematical and Physical Sciences:52557", author = "Tarasankar Pramanik and Sukumar Mondal and Madhumangal Pal", title = "The Diameter of an Interval Graph is Twice of its Radius", 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.", volume = "5", number = "8", pages = "1194-6", }
