Beperkingen op de boom

The Erös-Sós conjecture for Trees of Diameter Four

McLennan, A.
Stelling 1 Als #E>(k-2)#V/2, dan bevat G iedere boom B van orde k waarvoor geldt dat de diameter kleiner of gelijk aan k-2 is.

Idee van het bewijs
  • Als de diameter 2 is dan heb je een stervormige boom. De graaf bevat altijd een een punt met graad k-1. Dus G bevat deze boom
  • Sidorenko heeft bewezen dat G iedere boom B bevat die een knoop v bevat met k/2-1 leaf neighbors. Een consequentie hiervan is dat G iedere boom B bevat die diameter 3 heeft.
  • Wanneer de boom diameter 4 heeft is er een knoop a in de boom die maximaal afstand 2 heeft tot alle andere knopen in de boom. Kijk nu naar de graad van elementen uit N(a). Met behulp van drie lemma's wordt bewezen dat er een inbedding van de boom B in G moet bestaan.

    On maximal paths and circuits of graphs

    Erdös, P. & Gallai, T.
    Wanneer aan de aanname uit de conjecture is voldaan dan bevat G een pad van lengte k-1. Dit is 1 speciaal geval van de conjecture.

    On the Erös-Sós conjecture

    Wozniak, M
    In dit artikel wordt bewezen dat er een inbedding bestaat van iedere 'spider' van diepte 2 en orde 2 in de graaf G. Dit is een speciaal geval van hetgeen dat McLennan heeft bewezen. Wanneer een boom namelijk diepte 2 heeft dan is de diameter maximaal 4.

    A Sufficient Degree Condition for a Graph to Contain Alle Trees of Size k

    Camino Balbuena, Alberto Marquez en Jose Ramon Portillo
    Dit artikel gaat eigenlijk niet over beperkingen op de boom. Wel is er een opsomming over deelresultaten die behaald zijn. Hieronder vindt je een opsomming. In dit artikel vindt je de verwijzingen naar de artikelen waar deze deelresultaten worden bewezen:
  • G bevat een iedere boom die uit minder dan 8 knopen bestaat;
  • G bevat iedere boom, met k of minder knopen, die een knoop bevatten die tenminste t 'leaves' als buur heeft, met t ≥ (k-3)/2;
  • G bevat iedere comets, dit is een graaf die is verkregen is uit een ster door iedere zijde te vervangen voor een pad van lengte l, waar l vast staat.
  • G bevat iedere caterpillar, is een graaf waarvan de basis een pad is.

    © 2014 Mark Coumans
    Template design by Andreas Viklund / Best hosted at www.svenskadomaner.se