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

马花萍; 田应智

doi:10.13568/j.cnki.651094.651316.2020.04.16.0005

您当前的位置：

首页 >

文章列表页 >

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

数理科学 | 更新时间：2026-01-21

- 给定点数,最小度和条件直径的图的边数的上界
- 给定点数,最小度和条件直径的图的边数的上界
- 新疆大学学报（自然科学版中英文） 2021年38卷第4期页码：385-396
- 作者机构：
  
  新疆大学数学与系统科学学院
- 作者简介：
- 基金信息：
  
  国家自然科学基金(11861066;11531011);新疆天山青年项目(2018Q066)~~
- DOI：10.13568/j.cnki.651094.651316.2020.04.16.0005
  中图分类号： O157.5
- 纸质出版：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.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

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

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

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

广义笛卡尔积图的连通度

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