EMBEDDING ARBITRARY GRAPHS OF MAXIMUM DEGREE 2

被引：63

作者：

AIGNER, M

BRANDT, S

机构：

[1] II Math. Institut Freie Universität Berlin, Berlin

来源：

JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES | 1993年 / 48卷

关键词：

D O I：

10.1112/jlms/s2-48.1.39

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let delta(H) be the minimum degree of the graph H. We prove that a graph H of order n with delta(H) greater-than-or-equal-to (2n-1)/3 contains any graph G of order at most n and maximum degree DELTA(G) less-than-or-equal-to 2 as a subgraph, and this bound is best possible. Furthermore, this result settles the case DELTA(G) = 2 of the well-known conjecture of Bollobas, Catlin and Eldridge on packing two graphs with given maximum degree.

引用

页码：39 / 51

页数：13

共 11 条

[1]

Aigner Martin, 1988, COMBINATORIAL SEARCH

[2]

BOLLOBAS B, 1978, J OCMBIN THEORY B, V2525, P105

[3]

BOLLOBAS B, 1978, EXTREMAL GRAPH THEOR, V6

[4]

BONDY JA, 1971, GRAPH THEORY COMPUTI, V3, P80

[5]

Catlin P. A., 1974, Discrete Mathematics, V10, P225, DOI 10.1016/0012-365X(74)90119-8

[6]

Catlin P.A., 1976, THESIS OHIO STATE U

[7]

Corradi K., 1963, ACTA MATH HUNGAR, V14, P423

[8]

Dirac G. A., 1952, P LOND MATH SOC, V2, P69, DOI [10.1112/plms/s3-2.1.69, DOI 10.1112/PLMS/S3-2.1.69]

[9] ON CIRCUITS IN GRAPHS [J].

ELZAHAR, MH .

DISCRETE MATHEMATICS, 1984, 50 (2-3) :227-230

[10]

Hajnal A., 1970, COMBIN THEORY APPL, VII, P601

← 1 2 →