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 条

[21] Distance domination in graphs with given minimum and maximum degree [J].

Michael A. Henning ;

Nicolas Lichiardopol .

Journal of Combinatorial Optimization, 2017, 34 :545-553

[22] Average eccentricity, minimum degree and maximum degree in graphs [J].

Dankelmann, P. ;

Osaye, F. J. .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2020, 40 (03) :697-712

[23] Average eccentricity, minimum degree and maximum degree in graphs [J].

P. Dankelmann ;

F. J. Osaye .

Journal of Combinatorial Optimization, 2020, 40 :697-712

[24] On the Minimum Kirchhoff Index of Unicyclic Graphs with Given Girth and Diameter [J].

Feihong Yang ;

Mei Lu ;

Jia Guo .

Bulletin of the Malaysian Mathematical Sciences Society, 2022, 45 :1287-1299

[25] On the Minimum Kirchhoff Index of Unicyclic Graphs with Given Girth and Diameter [J].

Yang, Feihong ;

Lu, Mei ;

Guo, Jia .

BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2022, 45 (03) :1287-1299

[26] Maximum diameter of 3-and 4-colorable graphs [J].

Czabarka, Eva ;

Smith, Stephen J. ;

Szekely, Laszlo .

JOURNAL OF GRAPH THEORY, 2023, 102 (02) :262-270

[27] Counterexamples to the conjecture on orientations of graphs with minimum Wiener index [J].

Fang, Yibin ;

Gao, Yubin .

DISCRETE APPLIED MATHEMATICS, 2017, 232 :213-220

[28] MINIMUM EDGE CUTS IN DIAMETER 2 GRAPHS [J].

Bickle, Allan ;

Schwenk, Allen .

DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2019, 39 (02) :605-608

[29] Wiener index in graphs with given minimum degree and maximum degree [J].

Alochukwu, Alex ;

Dankelmann, Peter .

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2021, 23 (01)

[30] On the Maximum Diameter of Path-Pairable Graphs [J].

Girao, Antonio ;

Popielarz, Kamil ;

Meszaros, Gabor ;

Snyder, Richard .

GRAPHS AND COMBINATORICS, 2019, 35 (06) :1647-1657

← 1 2 3 4 5 →