Using the minimum and maximum degrees to bound the diameter of orientations of bridgeless graphs

被引：0

作者：

Zhang, Wan-Ping ^{[1
]}

Meng, Ji-Xiang ^{[1
]}

Wu, Baoyindureng ^{[1
]}

机构：

[1] Xinjiang Univ, Coll Math & Syst Sci, Urumqi 830046, Xinjiang, Peoples R China

来源：

JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF CHINA | 2023年

基金：

中国国家自然科学基金;

关键词：

Orientation; Diameter; Minimum degree; Maximum degree; Girth; Packing; Bridgeless graph; ORIENTED DIAMETER; DISTANCES; DIGRAPHS;

D O I：

10.1007/s40305-023-00476-2

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

The oriented diameter of an undirected graph G, denoted by diam (G(?)), is defined as the minimum diameter of any strong orientation of G. In this paper, we prove that the oriented diameter of a bridgeless C-4-free graph is at most (37n)/ (d)2(-2[d/2]]1+1) + 19. We also consider some upper bounds of diam (G(?)) in terms of girth g, minimum degree d and maximum degree A and give some upper bounds of diam(G(?)) in bridgeless (C-4, C-5)-free graphs.

引用

页数：16

共 50 条

[1] Diameter of orientations of graphs with given minimum degree
Bau, Sheng
Dankelmann, Peter
EUROPEAN JOURNAL OF COMBINATORICS, 2015, 49 : 126 - 133
[2] The maximum girth and minimum circumference of graphs with prescribed radius and diameter
Qiao, Pu
Zhan, Xingzhi
DISCRETE MATHEMATICS, 2018, 341 (10) : 2827 - 2830
[3] Oriented diameter of graphs with given maximum degree
Dankelmann, Peter
Guo, Yubao
Surmacs, Michel
JOURNAL OF GRAPH THEORY, 2018, 88 (01) : 5 - 17
[4] Oriented diameter of graphs with given girth and maximum degree
Chen, Bin
Chang, An
DISCRETE MATHEMATICS, 2023, 346 (04)
[5] The upper bounds on the Steiner k-Wiener index in terms of minimum and maximum degrees
Zhang, Wanping
Meng, Jixiang
Wu, Baoyindureng
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2022, 44 (02) : 1199 - 1220
[6] The diameter of strong orientations of strong products of graphs
Ladinek, Irena Hrastnik
Spacapan, Simon
QUAESTIONES MATHEMATICAE, 2021, 44 (07) : 945 - 958
[7] Distance domination in graphs with given minimum and maximum degree
Henning, Michael A.
Lichiardopol, Nicolas
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 34 (02) : 545 - 553
[8] Diameter of orientations of graphs with given order and number of blocks
Dankelmann, P.
Morgan, M. J.
Rivett-Carnac, E. J.
QUAESTIONES MATHEMATICAE, 2025,
[9] The upper bounds on the Steiner k-Wiener index in terms of minimum and maximum degrees
Wanping Zhang
Jixiang Meng
Baoyindureng Wu
Journal of Combinatorial Optimization, 2022, 44 : 1199 - 1220
[10] EDGE NUMBER, MINIMUM DEGREE, MAXIMUM INDEPENDENT SET, RADIUS AND DIAMETER IN TWIN-FREE GRAPHS
Auger, David
Charon, Irene
Honkala, Iiro
Hudry, Oliver
Lobstein, Antoine
ADVANCES IN MATHEMATICS OF COMMUNICATIONS, 2009, 3 (01) : 97 - 114

← 1 2 3 4 5 →