Graphs which are intervals

被引:0
|
作者
Bau, Sheng [1 ]
Johnson, Peter [2 ]
机构
[1] Univ KwaZulu Natal, Sch Math Stat & Comp Sci, CH-3209 Scottsville, South Africa
[2] Auburn Univ, Dept Math & Stat, Auburn, AL 36830 USA
来源
BULLETIN MATHEMATIQUE DE LA SOCIETE DES SCIENCES MATHEMATIQUES DE ROUMANIE | 2024年 / 67卷 / 04期
关键词
Diameter; distance; extremal; homomorphism; shortest path;
D O I
暂无
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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).
引用
收藏
页码:419 / 427
页数:9
相关论文
共 50 条