Iskanje po katalogu digitalne knjižnice

Opis: Pravilno barvanje vozlišč grafa kjer vsak barvni razred vsebuje vozlišče, ki ima soseda v vseh preostalih barvnih razredih, imenujemo b-barvanje. Največje naravno število ▫$varphi (G)$▫, za katero obstaja b-barvanje grafa ▫$G$▫, imenujemo b-kromatično število. Določimo nekatere spodnje in zgornje meje b-kromatičnega števila za krepki produkt ▫$G,boxtimes, H$▫, leksikografski produkt ▫$G[H]$▫ in za direktni produkt ▫$G,times, H$▫. Prav tako določimo nekatere točne vrednosti za produkte poti, ciklov, zvezd in polnih dvodelnih grafov. Pokažemo tudi, da lahko določimo b-kromatično število za ▫$P_n ,boxtimes, H$▫, ▫$C_n ,boxtimes, H$▫, ▫$P_n[H]$▫, ▫$C_n[H]$▫ in ▫$K_{m,n}[H]$▫ za poljuben graf ▫$H$▫, če sta le ▫$m$▫ in ▫$n$▫ dovolj veliki.
Ključne besede: teorija grafov, b-kromatično število, krepki produkt, leksikografski produkt, direktni produkt, graph theory, b-chromatic number, strong product, lexicographic product, direct product
Objavljeno v DKUM: 10.07.2015; Ogledov: 1190; Prenosov: 90
Povezava na celotno besedilo

Objavljeno v DKUM: 10.07.2015; Ogledov: 512; Prenosov: 35
Povezava na celotno besedilo

Opis: Predstavljeni so vsi minimalni klični separatorji za vse štiri standardne produkte: kartezičnega, krepkega, leksikografskega in direktnega. Maksimalne atome natančno opišemo le za prve tri prej omenjene standardne produkte. V direktnem produktu maksimalne atome opišemo le delno. Tipična situacija za standardni grafovski produkt je, da ne vsebuje kličnih separatorjev in je posledično ves produkt maksimalni atom.
Ključne besede: matematika, teorija grafov, produkt grafov, klični separator, atom, mathematics, graph theory, clique separator, atom, graph products
Objavljeno v DKUM: 10.07.2015; Ogledov: 1063; Prenosov: 134
Povezava na celotno besedilo

Opis: Geodetka in geodetski interval, ki je sestavljen iz vseh vozlišč, ki pripadajo kakšni geodetki med fiksnim parom vozlišč v povezanem grafu ▫$G$▫, sta sestavni del metrične teorije grafov. Prav tako je znano, da je Steinerjevo drevo (multi) množice s ▫$k$▫ (▫$k>2$▫) vozlišči, posplošitev geodetke. V (B. Brešar, M. Changat, J. Mathews, I. Peterin, P. G. Narasimha-Shenoi, A. Tepeh Horvat, Steiner intervals, geodesic intervals, and betweenness, Discrete Math. 309 (2009) 6114--6125) so se avtorji ukvarjali s ▫$k$▫-Steinerjevimi intervali ▫$S(u_{1},u_{2},ldots, u_{k})$▫ povezanih grafov (▫$k geq 3$▫) kot ▫$k$▫-arnimi posplošitvami geodetskih intervalov. Analogno sta bila iz binarne na ▫$k$▫-arno funkcijo posplošena tudi vmesnostni aksiom (b2) in monotoni aksiom(m) kot: za vsa vozlišča ▫$u_{1}, ldots, u_{k}, x, x_{1}, ldots, x_{k} in V(G)$▫, ki niso nujno različna ▫$$(b2)quad x in S(u_{1}, u_{2}, ldots, u_{k}) Rightarrow S(x, u_{2}, ldots, u_{k}) subseteq S(u_{1}, u_{2}, ldots, u_{k}),$$▫ ▫$$(m) quad x_{1}, ldots, x_{k} in S(u_{1}, ldots, u_{k})Rightarrow S(x_{1}, ldots,x_{k}) subseteq S(u_{1}, ldots, u_{k}).$$▫ Avtorji so v zgoraj omenjenem članku domnevali, da ▫$3$▫-Steinerjev interval povezanega grafa ▫$G$▫ zadošča vmesnostnemu aksiomu (b2) natanko tedaj, ko je vsak blok grafa ▫$G$▫ geodetski z diametrom največ 2. V tem delu dokažemo to domnevo. Pri tem dodatno dokažemo, da v vsakem geodetskem bloku z diametrom vsaj 3 obstaja izometrični cikel dolžine ▫$2k+1$▫, ▫$k>2$▫. Prav tako predstavimo dodaten aksiom (b2(2)), ki je smiseln le za 3-Steinerjeve intervale in pokažemo, da je le ta ekvivalenten monotonemu aksiomu.
Ključne besede: matematika, teorija grafov, Steinerjev interval, geodetski graf, vmesnost, mathematics, graph theory, Steiner interval, geodetic graph, betweenness
Objavljeno v DKUM: 10.07.2015; Ogledov: 1032; Prenosov: 87
Povezava na celotno besedilo

Objavljeno v DKUM: 10.07.2015; Ogledov: 470; Prenosov: 21
Povezava na celotno besedilo