A graph G is called an interval if there exist a, b is an element of V(G) such that G is the union of shortest paths connecting a and b. In this paper we show that 1. If G is an interval between a and b, then there exists a path H with diameter d(H) = d(G) such that there is a homomorphism f : G -> H and the distance rho(a,b) + 1 <= |H| <= |G|-1; 2. Every interval is a connected bipartite graph; 3. If G is an interval between a and b that is not a path, then G has a path P with internal vertices (if any) all of degree 2 such that deletion of the internal vertices of P from G gives rise to an interval (if P = uv then G-uv is an interval).
机构:
Slovak Univ Technol Bratislava, Fac Chem & Food Technol, Bratislava 81237, SlovakiaSlovak Univ Technol Bratislava, Fac Chem & Food Technol, Bratislava 81237, Slovakia
机构:
Comenius Univ, Fac Math Phys & Informat, Dept Math Anal & Numer Math, SK-84248 Bratislava, SlovakiaComenius Univ, Fac Math Phys & Informat, Dept Math Anal & Numer Math, SK-84248 Bratislava, Slovakia