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 条
  • [21] On the harmonic index and the average eccentricity of graphs
    Zhong, Lingping
    Cui, Qing
    UTILITAS MATHEMATICA, 2017, 103 : 311 - 318
  • [22] On the minimal eccentric connectivity indices of graphs
    Zhang, Jianbin
    Zhou, Bo
    Liu, Zhongzhu
    DISCRETE MATHEMATICS, 2012, 312 (05) : 819 - 829
  • [23] On the maximal eccentric connectivity indices of graphs
    Zhang Jian-bin
    Liu Zhong-zhu
    Zhou Bo
    APPLIED MATHEMATICS-A JOURNAL OF CHINESE UNIVERSITIES SERIES B, 2014, 29 (03) : 374 - 378
  • [24] Some properties for a class of interchange graphs
    Jin, Jingjing
    DISCRETE APPLIED MATHEMATICS, 2011, 159 (17) : 2069 - 2077
  • [25] On the maximal eccentric connectivity indices of graphs
    Jian-bin Zhang
    Zhong-zhu Liu
    Bo Zhou
    Applied Mathematics-A Journal of Chinese Universities, 2014, 29 : 374 - 378
  • [26] Traveling in randomly embedded random graphs
    Frieze, Alan
    Pegden, Wesley
    RANDOM STRUCTURES & ALGORITHMS, 2019, 55 (03) : 649 - 676
  • [27] Belief intervals aggregation
    Sun, Guidong
    Guan, Xin
    Yi, Xiao
    Zhao, Jing
    INTERNATIONAL JOURNAL OF INTELLIGENT SYSTEMS, 2018, 33 (12) : 2425 - 2447
  • [28] On the difference between proximity and other distance parameters in triangle-free graphs and C4-free graphs
    Dankelmann, Peter
    Mafunda, Sonwabile
    DISCRETE APPLIED MATHEMATICS, 2022, 321 : 295 - 307
  • [29] On the resistance diameters of graphs and their line graphs
    Xu, Si-Ao
    Li, Yun-Xiang
    Hua, Hongbo
    Pan, Xiang-Feng
    DISCRETE APPLIED MATHEMATICS, 2022, 306 : 174 - 185
  • [30] The maximum Wiener polarity index of unicyclic graphs
    Hou, Huoquan
    Liu, Bolian
    Huang, Yufei
    APPLIED MATHEMATICS AND COMPUTATION, 2012, 218 (20) : 10149 - 10157