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 条
  • [1] THE MAXIMUM VALUES OF BEANS FUNCTIONS OF GRAPHS OVER INTERVALS
    Enami, Kengo
    JOURNAL OF NONLINEAR AND CONVEX ANALYSIS, 2018, 19 (10) : 1771 - 1774
  • [2] ON BIPARTITE GRAPHS WHICH ATTAIN MINIMUM RANK AMONG BIPARTITE GRAPHS WITH A GIVEN DIAMETER
    Li, Hong-Hai
    Su, Li
    Sun, Hui-Xian
    ELECTRONIC JOURNAL OF LINEAR ALGEBRA, 2012, 23 : 137 - 150
  • [3] Which Graphs have Non-integral Spectra?
    Katja Mönius
    Jörn Steuding
    Pascal Stumpf
    Graphs and Combinatorics, 2018, 34 : 1507 - 1518
  • [4] Which Graphs have Non-integral Spectra?
    Moenius, Katja
    Steuding, Joern
    Stumpf, Pascal
    GRAPHS AND COMBINATORICS, 2018, 34 (06) : 1507 - 1518
  • [5] Steiner intervals, geodesic intervals, and betweenness
    Bresar, Bostjan
    Changat, Manoj
    Mathews, Joseph
    Peterin, Iztok
    Narasimha-Shenoi, Prasanth G.
    Horvat, Aleksandra Tepeh
    DISCRETE MATHEMATICS, 2009, 309 (20) : 6114 - 6125
  • [6] Reciprocal complementary Wiener numbers of trees, unicyclic graphs and bicyclic graphs
    Cai, Xiochun
    Zhou, Bo
    DISCRETE APPLIED MATHEMATICS, 2009, 157 (14) : 3046 - 3054
  • [7] On Some Parameters of the Central Graphs of the Identity Graphs of Finite Cyclic Groups
    Alib, Clarence T.
    Magpantay, Daryl M.
    EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS, 2022, 15 (03): : 1098 - 1112
  • [8] Golden Laplacian Graphs
    Akhter, Sadia
    Frasca, Mattia
    Estrada, Ernesto
    MATHEMATICS, 2024, 12 (04)
  • [9] The diameter of directed graphs
    Dankelmann, P
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2005, 94 (01) : 183 - 186
  • [10] DISTANCE MAJORIZATION SETS IN GRAPHS
    Sundareswaran, R.
    Swaminathan, V.
    TWMS JOURNAL OF APPLIED AND ENGINEERING MATHEMATICS, 2015, 5 (01): : 118 - 123