Akademska digitalna zbirka SLovenije - logo
FMF in IMFM, Matematična knjižnica, Ljubljana (MAKLJ)
  • Generalization of Maclane's characterization of planar graphs
    Mohar, Bojan
    Cikel grafa ▫$G$▫ je vsak Eulerjev podgraf. Prostor ciklov ▫$Z(G)$▫ je množica ciklov skupaj z operacijo simetrične razlike. ▫$B\subseteq Z(G)$▫ je 2-množica, če je poljubna povezava iz ▫$G$▫ ... vsebovana kvečjemu v dveh ciklih iz ▫$B$▫. Z ▫$\delta (B)$▫ označimo kodimenzijo v ▫$Z(G)$▫ prostora, ki ga generira 2-množica ▫$B$▫. Nadalje naj bo ▫$\omega(S) = 2-\chi$▫, kjer je ▫$\chi$▫ največja možna Eulerjeva karakteristika med vsemi sklenjenimi ploskvami, v katere lahko vložimo graf ▫$G$▫. Dokazana je naslednja posplošitev MacLaneove karakterizacije ravninskih grafov: Vsak graf ▫$G$▫ ima tako 2-množico ciklov ▫$B$▫, da je ▫$\delta(B) = \omega(G)$▫. Če je ▫$B$▫ poljubna 2-množica grafa ▫$G$▫, pa je ▫$\omega (G)\le 2\cdot \delta (B)$▫. Ta meja je najboljša možna.
    Vir: Preprint series of the Department of Mathematics. - ISSN 0352-3004 (Let. 24, št. 182, 1987, str. 297-303)
    Vrsta gradiva - članek, sestavni del
    Leto - 1987
    Jezik - angleški
    COBISS.SI-ID - 7370841

Vnos na polico