DIKUL - logo
FMF in IMFM, Matematična knjižnica, Ljubljana (MAKLJ)
  • Crossing graphs as joins of graphs and cartesian products of median graphs
    Brešar, Boštjan ; Klavžar, Sandi
    Križni graf ▫$G^\#$▫ delne kocke ▫$G$▫ je graf, katerega vozlišča so ▫$\Theta$▫-razredi grafa ▫$G$▫, razreda pa sta sosednja, če se križata na nekem ciklu v ▫$G$▫. Obravnavan je naslednji problem, ki ... je bil postavljen v [S. Klavžar in H. M. Mulder, SIAM J. Discrete Math., 15 (2002), pp. 235-251, Problem 7.1]: Kaj lahko rečemo o delni kocki ▫$G$▫, če je ▫$G^\#$▫ spoj ▫$A \oplus B$▫ grafov ▫$A$▫ in ▫$B$▫ z vsaj eno povezavo? Dokazano je, da za poljubna grafa ▫$A$▫ in ▫$B$▫, kjer vsaj eden od njiju vsebuje vsaj eno povezavo, obstaja delna kocka ▫$G$▫, ki je nerazcepna glede na kartezični produkt grafov, tako da velja ▫$G^\# = A \oplus B$▫. Po drugi strani, če je ▫$G$▫ medianski graf, tedaj je ▫$G^\# = A \oplus B$▫ natanko tedaj, ko je ▫$G = H\,\square\, K$▫, kjer je ▫$H^\# = A$▫ in ▫$K^\# = B$▫. Spotoma so dobljena tudi nekatera nova dejstva o delnih kockah; na primer, dvodelni graf radija 2 je delna kocka natanko tedaj, ko ne vsebuje podgrafa ▫$K_{2,3}$▫.
    Vir: SIAM journal on discrete mathematics. - ISSN 0895-4801 (Vol. 21, no. 1, 2007, str. 26-32)
    Vrsta gradiva - članek, sestavni del
    Leto - 2007
    Jezik - angleški
    COBISS.SI-ID - 14194777

    Povezava(-e):

    http://dx.doi.org/10.1137/050622997

vir: SIAM journal on discrete mathematics. - ISSN 0895-4801 (Vol. 21, no. 1, 2007, str. 26-32)

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

Vnos na polico