Premium
Embedding Arbitrary Graphs of Maximum Degree Two
Author(s) -
Aigner M.,
Brandt S.
Publication year - 1993
Publication title -
journal of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.441
H-Index - 62
eISSN - 1469-7750
pISSN - 0024-6107
DOI - 10.1112/jlms/s2-48.1.39
Subject(s) - combinatorics , mathematics , degree (music) , conjecture , embedding , graph , discrete mathematics , induced subgraph , factor critical graph , line graph , graph power , computer science , physics , vertex (graph theory) , artificial intelligence , acoustics
Let δ( H ) be the minimum degree of the graph H . We prove that a graph H of order n with δ( H ) ⩾ (2 n −1)/3 contains any graph G of order at most n and maximum degree Δ( G ) ⩽ 2 as a subgraph, and this bound is best possible. Furthermore, this result settles the case Δ( G ) = 2 of the well‐known conjecture of Bollobás, Catlin and Eldridge on packing two graphs with given maximum degree.