VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Graphs with a unique maximum independent set up to automorphisms
    Brešar, Boštjan ...
    Če za vsaki dve največji neodvisni množici ▫$A$▫ in ▫$B$▫ grafa ▫$G$▫ obstaja tak avtomorfizem grafa ▫$G$▫, ki ▫$A$▫ preslika na ▫$B$▫, pravimo, da je ▫$G$▫ ▫$\alpha$▫-izo-enoličen graf. V članku ... razširimo več znanih karakterizacij dreves, ki imajo enolično največjo neodvisno množico, in s tem dobimo karakterizacije ▫$\alpha$▫-izo-enoličnih dreves. Taka drevesa imajo bodisi lastnost, da brisanje poljubne povezave ne spremeni neodvisnostnega števila bodisi imajo centralno povezavo, ki povezuje dve izomorfni poddrevesi in zgolj brisanje te centralne povezave poveča neodvisnostno število. Ena od karakterizacij pripelje do linearnega algoritma za odločitev, ali je poljubno drevo ▫$\alpha$▫-izo-enolično. Po drugi strani dokažemo, da za poljuben graf problem odločitve, ali je ta graf ▫$\alpha$▫-izo-enoličen, ni polinomski, razen če je P=NP. Podamo tudi konstrukcije velikih družin ▫$\alpha$▫-izo-enoličnih grafov, ki so povezane s simplicialnimi vozlišči in tetivnimi grafi. Med drugim tudi dokažemo, da je vsak graf induciran podgraf nekega ▫$\alpha$▫-izo-enoličnega grafa. Nazadnje pa okarakteriziramo še ▫$\alpha$▫-izo-enolične grafe med kartezičnimi produkti ▫$G\Box H$▫ tujih si grafov ▫$G$▫ in ▫$H$▫, za katera velja ▫$\alpha(G\Box H)=\alpha(G)|V(H)|$▫.
    Vir: Discrete applied mathematics. - ISSN 0166-218X (Vol. 317, Aug. 2022, str. 124-135)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2022
    Jezik - angleški
    COBISS.SI-ID - 108645123

    Povezava(-e):

    https://www.sciencedirect.com/science/article/pii/S0166218X22001251
    DOI

Vnos na polico