UP - logo
FMF in IMFM, Matematična knjižnica, Ljubljana (MAKLJ)
  • Independence number of products of Kneser graphs
    Brešar, Boštjan ; Valencia-Pabon, Mario
    Obravnavamo neodvisnostno število produktov Kneserjevih grafov ▫$K(n,k)$▫ samih s sabo, z ozirom na vse štiri standardne grafovske produkte. Problem ni zahteven v primerih direktnega, krepkega in ... leksikografskega produkta Kneserjevih grafov (formula za ▫$\alpha(K(n,k)\boxtimes K(n,k))$▫ je predstavljena v tem članku), medtem ko je za kartezični produkt Kneserjevih grafov problem precej bolj kompleksen. V članku izpeljemo spodnje in zgornje meje za neodvisnostno število grafa ▫$K(n,2)\Box K(n,2)$▫, ki se asimptotično bližajo ▫$n^3/3$▫ oziroma ▫$3n^3/8$▫. Prva meja je dobljena s konstrukcijo, ki se razlikuje od standardne diagonalizacijske procedure, medtem ko za zgornjo mejo uporabimo ▫$\ell$▫-neodvisnostno število Kneserjevih grafov. Predstavimo tudi nekaj konstrukcij v lihih grafih ▫$K(2k+1,k)$▫, ki porajajo spodnjo mejo za 2-neodvisnostno število teh grafov in dokažemo, da dve takšni konstrukciji dajeta isto spodnjo mejo kot že prej znana konstrukcija. Nazadnje obravnavamo tudi ▫$s$▫-stabilne Kneserjeve grafe, ▫$K(ks+1,k)_{s-\operatorname{stab}}$▫, izpeljemo formulo za njihovo $\ell$-neodvisnostno število in predstavimo točne vrednosti za neodvisnostno število kartezičnega kvadrata grafa ▫${K}(ks+1,k)_{s-\operatorname{stab}}$▫.
    Vir: Discrete mathematics. - ISSN 0012-365X (Vol. 342, iss. 4, April 2019, str. 1017-1027)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2019
    Jezik - angleški
    COBISS.SI-ID - 18538073

    Povezava(-e):

    https://doi.org/10.1016/j.disc.2018.12.017
    DOI

vir: Discrete mathematics. - ISSN 0012-365X (Vol. 342, iss. 4, April 2019, str. 1017-1027)

loading ...
loading ...
loading ...

Vnos na polico