给定点数,最小度和条件直径的图的边数的上界

马花萍; 田应智

doi:10.13568/j.cnki.651094.651316.2020.04.16.0005

您当前的位置：

首页 >

文章列表页 >

给定点数,最小度和条件直径的图的边数的上界

更新时间：2026-01-21

- 给定点数,最小度和条件直径的图的边数的上界
- Journal of Xinjiang University (Natural Science Edition in Chinese and English) Vol. 38, Issue 4, Pages: 385-396(2021)
- 作者机构：
  
  新疆大学数学与系统科学学院
- 作者简介：
- 基金信息：
- DOI：10.13568/j.cnki.651094.651316.2020.04.16.0005
  CLC： O157.5
- Published：2021
- 稿件说明：
移动端阅览
[1]马花萍,田应智.给定点数,最小度和条件直径的图的边数的上界[J].新疆大学学报(自然科学版)(中英文),2021,38(04):385-396.
[1]马花萍,田应智.给定点数,最小度和条件直径的图的边数的上界[J].新疆大学学报(自然科学版)(中英文),2021,38(04):385-396. DOI： 10.13568/j.cnki.651094.651316.2020.04.16.0005.

DOI：10.13568/j.cnki.651094.651316.2020.04.16.0005.

摘要

图G的直径是G中任意两个点之间的最大距离.给定两个正整数l和s

条件直径D(G;l

s)是点数分别为l和s的两个点集之间的最大距离.当l=s=1时

图G的条件直径D(G;1

1)恰好是图G的直径D(G).本文得到了在给定点数

最小度和条件直径下图G的边数上界

且验证了这个边数的上界是渐进紧的.

Abstract

The diameter D(G) of a graph G is the the maximum distance between two vertices in G. For given positive integers l and s

the conditional diameter D(G; l

s) of a graph G is the maximum distance between two subsets of vertices with cardinalities l and s. When l = s = 1

the conditional diameter D(G; 1

1) is just the diameter D(G) of G. In this paper

we obtain an asymptotically tight upper bound on the size of G in terms of order

minimum degree and conditional diameter.

关键词

Keywords

references

BONDY J A,MURTY U S R.Graph theory[M].Berlin:Springer,Graduate Texts in Mathematics 244,2008.

BALBUENA C,CARMONA A,F`ABREGA J,et al.On the connectivity and the conditional diameter of graphs and digraphs[J].Networks,1996,28:97-105.

BALBUENA C,GARC′IA-V′AZQUEZ P,MARCOTE X,et al.Conditional diameter saturated graphs[J].Networks,2008,52(4):196-201.

ERD"OS P,R′ENYI A.On a problem in the theory of graphs[J].Publ Math Inst Hungar Acad Sci,Ser B,1963,7:623-639.

ERD"OS P,R′ENYI A,S′OS V T.On a problem of graph theory[J].Studia Sci Math Hungar,1966,1:215-235.

BOLLOB′AS B.Graphs with given diameter and minimal degree[J].Ars Combin,1976,2:3-9.

ORE O.Diameters in graphs[J].J Combin Theory,1968,5:75-81.

MUKWEMBI S.On size,order,diameter and minimum degree[J].Indian J Pure Appl Math,2013,44(4):467-472.

ALI P,MAZORODZE J P,MUKWEMBI S,et al.On size,order,diameter and edge-connectivity of graphs[J].Acta Math Hungar,2017,152(1):11-24.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

特征值互不相同的图(英文)

给定围长的图的超三限制性连通度的充分条件(英文)

有向循环图的直径与覆盖指数

广义笛卡尔积图的连通度

若干类循环图的直径及其最优直径

Related Author

张艳玲

黄琼湘

马志辉

孟吉翔

代玉林

孟吉翔

黄琼湘

Related Institution

新疆大学计算中心,新疆大学数学系,

新疆大学数学系

新疆大学数学系,

青海民族学院,

厦门理工学院应用数学学院

⁰