ALL libraries (COBIB.SI union bibliographic/catalogue database)
  • Graph minors and minimum degree [Elektronski vir]
    Fijavž, Gašper ; Wood, David Richard
    Z ▫$\mathcal{D}_k$▫ označimo razred grafov, za katere velja, da ima vsak njihov minor točko stopnje največ ▫$k$▫. Razred ▫$\mathcal{D}_k$▫ je zaprt za grafovske minorje. Izrek o grafovskih minorjih ... Robertson-Seymourja trdi, da lahko razred ▫$\mathcal{D}_k$▫ karakteriziramo s končno družino prepovedanih minorjev, ki jo označimo z ▫$\widehat{\mathcal{D}}_k$▫. V članku študiramo družine ▫$\widehat{\mathcal{D}}_k$▫. Naši štirje glavni rezultati so: (1) Vsak ▫$(k+1)$▫-regularen graf z največ ▫$\frac{4}{3}(k+2)$▫ točkami pripada ▫$\widehat{\mathcal{D}}_k$▫, in meja o številu točk je najboljša možna. (2) Natančno opišemo grafe iz ▫$\widehat{\mathcal{D}}_{k+1}$▫, ki jih lahko dobimo iz grafov v ▫$\widehat{\mathcal{D}}_k$▫ z dodajanjem ene same točke. (3) Pri ▫$k\leq 3$▫ so vsi grafi družine ▫$\widehat{\mathcal{D}}_k$▫ tudi ▫$(k+1)$▫-povezani, za velike ▫$k$▫ pa lahko konstruiramo grafe ▫$\mathcal{D}_k$▫ s povezanostjo 1. Še več, konstruiramo lahko grafe v ▫$\widehat{\mathcal{D}}_k$▫ s poljubno bločno srukturo. (4) Karakteriziramo polne multipartitne grafe tako iz ▫$\widehat{\mathcal{D}}_k$▫, kot tudi iz analognih družin prepovedanih minorjev v primeru parametrov povezanosti, drevesne širine in linearne drevesne širine.
    Source: The Electronic journal of combinatorics [Elektronski vir]. - ISSN 1077-8926 (Vol. 17, no. 1, 2010, R151 (30 str.))
    Type of material - e-article
    Publish date - 2010
    Language - english
    COBISS.SI-ID - 15813209

    Link(s):

    http://www.combinatorics.org/Volume_17/PDF/v17i1r151.pdf

Shelf entry