DIKUL - logo
FMF in IMFM, Matematična knjižnica, Ljubljana (MAKLJ)
  • On the independence graph of a graph
    Brešar, Boštjan ; Zmazek, Blaž
    Točke neodvisnostnega grafa ▫$G$▫ predstavljajo največje neodvisne množice grafa ▫$G$▫ in dve točki v njem sta sosednji, če sta pripadajoči množici disjunktni. Vizingova neenakost o neodvisnostnem ... številu kartezičnega produkta grafov ▫$G$▫ in ▫$H$▫ pove, da je ▫$\alpha(G \Box H) \le \min \{\alpha(G)|V(H)|, \alpha(H)|V(G)|\}$▫. Hell, Yu in Zhou so opazili, da je enakost dosežena natanko tedaj, ko obstaja homomorfizem iz enega faktorja v neodvisnostni graf drugega faktorja. V članku dokažemo, da je vsak graf neodvisnostni graf kakega grafa in predstavimo nekaj strukturnih lastnosti neodvisnostnih grafov, s pomočjo katerih opišemo velik razred grafov, za katere velja enakost ▫$\alpha(G \Box G) = \alpha(G)|V(G)|$▫.
    Vir: Discrete mathematics. - ISSN 0012-365X (Vol. 272, no. 2-3, 2003, str. 263-268)
    Vrsta gradiva - članek, sestavni del
    Leto - 2003
    Jezik - angleški
    COBISS.SI-ID - 12722009

vir: Discrete mathematics. - ISSN 0012-365X (Vol. 272, no. 2-3, 2003, str. 263-268)

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

Vnos na polico