DIKUL - logo
(UL)
PDF
  • Characterization of general position sets and its applications to cographs and bipartite graphs
    Anand, Bijo S. ...
    Podmnožica vozlišč ▫$S$▫ grafa ▫$G$▫ je množica v splošni legi, če nobeno vozlišče iz ▫$S$▫ ne leži na najkrajši poti med dvema drugima vozliščema iz ▫$S$▫. Kardinalnost največje množice vozlišč v ... splošni legi je število splošne lege ▫${\rm gp}(G)$▫ grafa ▫$G$▫. Dokazano je, da je ▫$S\subseteq V(G)$▫ v splošni legi natanko tedaj, ko so komponenente porojenega podgrafa ▫$G[S]$▫ polni grafi, katerih vozlišča tvorijo in-tranzitivno, razdaljno-konstantno particijo množice ▫$S$▫. Če je ▫${\rm diam}(G) = 2$▫, potem je ▫${\rm gp}(G)$▫ maksimum od ▫$\omega(G)$▫ in velikosti največje množice vozlišč, ki inducira polni multipartitni podgraf komplementa grafa ▫$G$▫. Posledica tega rezultata je, da lahko ▫${\rm gp}(G)$▫ kografa ▫$G$▫ določimo v polinomskem času. Če je graf ▫$G$▫ dvodelen, potem velja ▫${\rm gp}(G) \leq \alpha(G)$▫ z enakostjo, če je ▫${\rm diam}(G) \in \{2,3\}$▫. Izpeljana je formula za število splošne lege za komplemente poljubnih dvodelnih grafov in poenostavljena za komplemente dreves, rešetk in hiperkock.
    Vir: Applied mathematics and computation. - ISSN 0096-3003 (Vol. 359, Oct. 2019, str. 84-89)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2019
    Jezik - angleški
    COBISS.SI-ID - 18636121

    Povezava(-e):

    https://doi.org/10.1016/j.amc.2019.04.064
    DOI

vir: Applied mathematics and computation. - ISSN 0096-3003 (Vol. 359, Oct. 2019, str. 84-89)

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

Vnos na polico