On size, order, diameter and edge-connectivity of graphs

被引：4

作者：

Ali, P. ^{[1
]}

Mazorodze, J. P. ^{[2
]}

Mukwembi, S. ^{[2
,3
]}

Vetrik, T. ^{[4
]}

机构：

[1] Univ Malawi, Dept Math Sci, Chancellor Coll, Zomba, Malawi

[2] Univ Zimbabwe, Dept Math, Harare, Zimbabwe

[3] Univ KwaZulu Natal, Sch Math Stat & Comp Sci, Durban, South Africa

[4] Univ Free State, Dept Math & Appl Math, Bloemfontein, South Africa

来源：

ACTA MATHEMATICA HUNGARICA | 2017年 / 152卷 / 01期

基金：

新加坡国家研究基金会;

关键词：

extremal graph theory; size; order; diameter; edge-connectivity; MINIMUM DEGREE;

D O I：

10.1007/s10474-017-0699-1

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

To bound the size (the number of edges) of a graph in terms of other parameters of a graph forms an important family of problems in the extremal graph theory. We present a number of upper bounds on the size of general graphs and triangle-free graphs. We bound the size of any graph and of any triangle-free graph in terms of its order (number of vertices), diameter and edge-connectivity. We also give an upper bound on the size of triangle-free graphs of given order, diameter and minimum degree. All bounds presented in this paper are asymptotically sharp.

引用

页码：11 / 24

页数：14

共 14 条

[1]

Bollobas B., 1976, ARS COMBINATORIA, V2, P3

[2] GRAPHS OF MAXIMUM DIAMETER [J].

CACCETTA, L ;

SMYTH, WF .

DISCRETE MATHEMATICS, 1992, 102 (02) :121-141

[3]

Caccetta L., 1987, J. Combin. Math. Combin. Comput, V2, P111

[4] Maximum sizes of graphs with given domination parameters [J].

Dankelmann, P ;

Domke, GS ;

Goddard, W ;

Grobler, P ;

Hattingh, JH ;

Swart, HC .

DISCRETE MATHEMATICS, 2004, 281 (1-3) :137-148

[5] Minimum size of a graph or digraph of given radius [J].

Dankelmann, Peter ;

Volkmann, Lutz .

INFORMATION PROCESSING LETTERS, 2009, 109 (16) :971-973

[6]

ERDOS P, 1989, J COMB THEORY B, V47, P73

[7]

Erdos P., 1966, Studia Sci. Math. Hungar., V1, P215

[8]

Erdos P., 1963, PUBL MATH I HUNG, V7, P623

[9] THE MAXIMUM NUMBER OF EDGES IN A MINIMAL GRAPH OF DIAMETER-2 [J].

FUREDI, Z .

JOURNAL OF GRAPH THEORY, 1992, 16 (01) :81-98

[10] On size, order, diameter and minimum degree [J].

Mukwembi, Simon .

INDIAN JOURNAL OF PURE & APPLIED MATHEMATICS, 2013, 44 (04) :467-472

← 1 2 →