| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Iskanje po katalogu digitalne knjižnice Pomoč

Iskalni niz: išči po
išči po
išči po
išči po
* po starem in bolonjskem študiju

Opcije:
  Ponastavi


1 - 10 / 14
Na začetekNa prejšnjo stran12Na naslednjo stranNa konec
1.
Median graphs, the remoteness function, periphery transversals, and geodetic number two
Kannan Balakrishnan, Boštjan Brešar, Manoj Changat, Wilfried Imrich, Sandi Klavžar, Matjaž Kovše, Ajitha R. Subhamathi, 2008

Opis: Periferna transverzala medianskega grafa ▫$G$▫ je vpeljana kot množica vozlišč, ki zadane vse periferije grafa $G$. S pomočjo tega koncepta so na dva različna načina karakterizirani medianski grafi z geodetskim številom 2. To so natanko tisti medianski grafi, ki vsebujejo periferno transverzalo moči 2, kot tudi medianski grafi, za katere obstaja takšen profil, da je funkcija oddaljenosti konstantna na ▫$G$▫. Predstavljen je tudi algoritem, ki v času ▫$O(m log n)$▫ odloči, ali je dani graf z ▫$n$▫ vozlišči in ▫$m$▫ povezavami medianski graf z geodetskim številom 2. Dobljenih je še več nadaljnjih lastnosti funkcije oddaljenosti na hiperkockah in medianskih grafih. Navedenih je tudi nekaj odprtih problemov.
Ključne besede: medianski graf, medianska množica, funkcija oddaljenosti, geodetsko število, periferna transverzala, median graph, median set, remoteness function, geodetic number, periphery transverzal, hypercube
Objavljeno: 10.07.2015; Ogledov: 365; Prenosov: 10
URL Povezava na celotno besedilo

2.
Characterizing posets for which their natural transit functions coincide
Boštjan Brešar, Manoj Changat, Sandi Klavžar, Joseph Mathews, Antony Mathews, Prasanth G. Narasimha-Shenoi, 2009, izvirni znanstveni članek

Opis: Standardna tranzitna funkcija delno urejene množice ▫$P$▫ je funkcija ▫$T_P$▫, ki vsakemu paru primerljivih elementov priredi interval med njima, za neprimerljiva elementa ▫$x,y$▫ pa je ▫$T_P(x,y) = {x,y}$▫. Na tri načine, tudi s prepovedanimi delno urejenimi podmnožicami, okarakteriziramo tiste delno urejene množice, v katerih standardna tranzitna funkcija sovpada s tranzitno funkcijo najkrajših poti njenega grafa pokritij-neprimerljivosti.
Ključne besede: matematika, teorija grafov, tranzitna funkcija, rangirana delno urejena množica, temeljni graf, geodetski interval, interval induciranih poti, mathematics, graph theory, transit function, ranked poset, underlying graph, geodesic interval, induced-path interval
Objavljeno: 10.07.2015; Ogledov: 497; Prenosov: 59
URL Povezava na celotno besedilo

3.
Cover-incomparability graphs of posets
Boštjan Brešar, Manoj Changat, Sandi Klavžar, Matjaž Kovše, Joseph Mathews, Antony Mathews, 2008, izvirni znanstveni članek

Opis: Vpeljemo graf pokritij-neprimerljivosti (ki mu na kratko rečemo CI-graf), katerega množica povezav je unija množic povezav grafa neprimerljivosti in grafa pokritja dane delno urejene množice. S pomočjo prepovedanih izometričnih delno urejenih podmnožic, okarakteriziramo tiste delno urejene množice, katerih CI-graf je tetiven (razdaljno-hereditaren, ptolemajski) in predlagamo splošen pristop k obravnavi CI-grafov. Predstavimo tudi več odprtih problemov.
Ključne besede: matematika, teorija grafov, delno urejena množica, temeljni graf, tranzitna funkcija, tetiven graf, razdaljno-hereditaren graf, mathematics, graph theory, poset, underlying graph, transit function, chordal graph, distance-hereditary graph, claw
Objavljeno: 10.07.2015; Ogledov: 302; Prenosov: 54
URL Povezava na celotno besedilo

4.
Strongly distance-balanced graphs and graph products
Kannan Balakrishnan, Manoj Changat, Iztok Peterin, Simon Špacapan, Primož Šparl, Ajitha R. Subhamathi, 2008, izvirni znanstveni članek

Opis: A graph ▫$G$▫ is strongly distance-balanced if for every edge ▫$uv$▫ of ▫$G$▫ and every ▫$i ge 0$▫ the number of vertices ▫$x$▫ with ▫$d(x,u) = d(x,v)-1 = i$▫ equals the number of vertices ▫$y$▫ with ▫$d(y,v) = d(y,u)-1 = i$▫. It is proved that the strong product of graphs is strongly distance-balanced if and only if both factors are strongly distance-balanced. It is also proved that connected components of the direct product of two bipartite graphs are strongly distance-balanced if and only if both factors are strongly distance-balanced. Additionally, a new characterization of distance-balanced graphs and an algorithm of time complexity ▫$O(mn)$▫ for their recognition, where m is the number of edges and ▫$n$▫ the number of vertices of the graph in question, are given.
Ključne besede: matematika, teorija grafov, razdaljno uravnoteženi grafi, mathematics, graph theory, distance-balanced grapha
Objavljeno: 10.07.2015; Ogledov: 479; Prenosov: 27
URL Povezava na celotno besedilo

5.
Steiner intervals, geodesic intervals, and betweenness
Boštjan Brešar, Manoj Changat, Joseph Mathews, Iztok Peterin, Prasanth G. Narasimha-Shenoi, Aleksandra Tepeh, 2009, izvirni znanstveni članek

Opis: Koncept ▫$k$▫-Steinerjevih intervalov naravno posplošuje geodetske (binarne) intervale. Definiran je kot preslikava ▫$S: Vtimes cdots times V longrightarrow 2^V$▫, kjer je ▫$S(u_1, dots ,u_k)$▫ množica tistih vozlišč grafa ▫$G$▫, ki ležijo na kakem Steinerjevem drevesu glede na multimnožico ▫$W = {u_1, dots ,u_k}$▫ vozlišč iz ▫$G$▫. V tem članku za vsako naravno število ▫$k$▫ dokažemo karakterizacijo razreda tistih grafov, v katerih imajo vsi ▫$k$▫-Steinerjevi intervali t.i. lastnost unije, ki pravi, da ▫$S(u_1,ldots, u_k)$▫ sovpada z unijo geodetskih intervalov ▫$I(u_i,u_j)$▫ med vsemi pari vozlišč iz ▫$W$▫. Izkaže se, da tedaj, ko je ▫$k>3$▫, ta razred sovpada z razredom grafov, v katerih ▫$k$▫-Steinerjev interval zadošča aksiomu monotonosti(m), kot tudi z razredom grafov, v katerih ▫$k$▫-Steinerjev interval zadošča aksiomu (b2), ki sta pogoja iz teorije vmesnosti. In sicer preslikava ▫$S$▫ zadošča aksiomu (m), če iz ▫$x_1, dots ,x_k in S(u_1, dots ,u_k)$▫ sledi ▫$S(x_1, dots ,x_k) subseteq S(u_1, dots ,u_k)$▫; ter ▫$S$▫ zadošča (b2), če iz ▫$x in S(u_1,u_2, dots ,u_k)$▫ sledi ▫$S(x,u_2, dots ,u_k) subseteq S(u_1, dots ,u_k)$▫. V primeru ▫$k=3$▫ so ti trije razredi grafov različni in za razreda grafov, v katerih Steinerjev interval zadošča lastnosti unije oz. aksiomu monotonosti (m), dokažemo strukturni karakterizaciji. Prav tako predstavimo več delnih ugotovitev za razred grafov, v katerih 3-Steinerjev interval zadošča aksimu (b2), ki vodijo do domneve, da so to natanko tisti grafi, v katerih je vsak blok geodetski graf z diametrom 2.
Ključne besede: matematika, teorija grafov, Steinerjev interval, geodetski interval, razdalja, vmesnost, monotonost, bločni graf, mathematics, graph theory, Steiner interval, geodesic interval, distance, betweenness, monotonicity, block graph
Objavljeno: 10.07.2015; Ogledov: 310; Prenosov: 44
URL Povezava na celotno besedilo

6.
On the remoteness function in median graphs
Kannan Balakrishnan, Boštjan Brešar, Manoj Changat, Wilfried Imrich, Sandi Klavžar, Matjaž Kovše, Ajitha R. Subhamathi, 2009, izvirni znanstveni članek

Opis: Profil grafa ▫$G$▫ je poljubna neprazna multimnožica vozlišč iz ▫$G$▫. Pripadajoča funkcija oddaljenosti priredi vsakemu vozlišču iz ▫$V(G)$▫ vsoto razdalj do vozlišč iz profila. Najprej so dobljene nekatere uporabne lastnosti funkcije oddaljenosti na hiperkockah, nato pa je funkcija oddaljenosti obravnavana na poljubnih medianskih grafih glede na njihove izometrične vložitve v hiperkocke. V posebnem je najdena povezava med vozlišči medianskega grafa ▫$G$▫, katerega funkcija oddaljenosti je največja (antimedianska množica v ▫$G$▫), z antimediansko množico pripadajoče hiperkocke. Medtem ko je za lihe profile antimedianska množica neodvisna množica, ki leži na strogem robu medianskega grafa, obstajajo medianski grafi, v katerih določeni sodi profili porajajo konstantno funkcijo oddaljenosti. Take medianske grafe karakteriziramo na dva načina: kot grafe, katerih periferna transverzala je 2, in kot grafe z geodetskim številom 2. Nazadnje predstavimo algoritem, ki za dani graf ▫$G$▫ z ▫$n$▫ vozlišči in ▫$m$▫ povezavami v času ▫$O(m log n)$▫ odloči, ali je ▫$G$▫ medianski graf z geodetskim številom 2.
Ključne besede: hiperkocka, medianski graf, medianska množica, funkcija oddaljenosti, geodetsko število, periferna transverzala, median graph, median set, remoteness function, geodetic number, periphery transverzal, hypercube
Objavljeno: 10.07.2015; Ogledov: 361; Prenosov: 60
URL Povezava na celotno besedilo

7.
Simultaneous embeddings of graphs as median and antimedian subgraphs
Kannan Balakrishnan, Boštjan Brešar, Manoj Changat, Sandi Klavžar, Matjaž Kovše, Ajitha R. Subhamathi, 2010, izvirni znanstveni članek

Opis: Razdalja ▫$D_G(v)$▫ vozlišča ▫$v$▫ v grafu ▫$G$▫ je vsota razdalj med ▫$v$▫ in vsemi drugimi vozlišči grafa ▫$G$▫. Množica vozlišč grafa ▫$G$▫ z maksimalno (minimalno) razdaljo je antimedianska (medianska) množica grafa ▫$G$▫. Dokazano je, da za poljubna grafa ▫$G$▫ in ▫$J$▫ ter za poljubno naravno število ▫$r ge 2$▫ obstaja povezani graf ▫$H$▫, tako da je ▫$G$▫ antimedianski in ▫$J$▫ medianski podgraf grafa ▫$H$▫ ter da pri tem velja ▫$d_H(G,J) = r$▫. V primeru, ko sta oba ▫$G$▫ in ▫$J$▫ povezana, lahko dodatno naredimo, da sta ▫$G$▫ in ▫$J$▫ konveksna podgrafa v ▫$H$▫.
Ključne besede: matematika, teorija grafov, problemi razmeščanja, medianske množice, antimedianske množice, konveksni podgrafi, mathematics, graph theory, facility location problems, median sets, antimedian sets, convex subgraphs
Objavljeno: 10.07.2015; Ogledov: 301; Prenosov: 51
URL Povezava na celotno besedilo

8.
Cover-incomparability graphs and chordal graphs
Boštjan Brešar, Manoj Changat, Tanja Gologranc, Joseph Mathews, Antony Mathews, 2010, izvirni znanstveni članek

Opis: Problem prepoznavanja grafov pokritij-neprimerljivosti (to je grafov, ki jih dobimo iz delno urejenih množic kot povezavno unijo njihovega grafa pokritij in grafa neprimerljivosti) je NP-poln v splošnem, kot so dokazali v [J. Maxová, P. Pavlíkova, A. Turzík, On the complexity of cover-incomparability graphs of posets, Order 26 (2009) 229-236], medtem ko je na primer očitno polinomski v razredu dreves. V tem članku se osredotočimo na razrede tetivnih grafov in dokažemo, da je vsak graf pokritij-neprimerljivosti, ki je tetiven graf, kar graf intervalov. Okarakteriziramo tiste delno urejene množice, ki imajo za graf pokritij-neprimerljivosti bločni graf, oziroma razcepljeni graf in tudi okarakteriziramo grafe pokritij-neprimerljivosti med bločnimi, oziroma razcepljenimi grafi. Slednji karakterizaciji dasta tudi linearen algoritem za prepoznavanje bločnih, oziroma razcepljenih grafov, ki so grafi pokritij-neprimerljivosti.
Ključne besede: matematika, teorija grafov, delno urejena množica, temeljni graf, tetiven graf, razcepljen graf, bločni graf, mathematics, graph theory, poset, underlying graph, chordal graph, split graf, block graph
Objavljeno: 10.07.2015; Ogledov: 445; Prenosov: 50
URL Povezava na celotno besedilo

9.
A note on Steiner intervals and betweenness
Manoj Changat, Anandavally K. Lakshmikuttyamma, Joseph Mathews, Iztok Peterin, Prasanth G. Narasimha-Shenoi, Aleksandra Tepeh, 2011, izvirni znanstveni članek

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: 10.07.2015; Ogledov: 349; Prenosov: 42
URL Povezava na celotno besedilo

10.
Some Steiner concepts on lexicographic products of graphs
Bijo S. Anand, Manoj Changat, Iztok Peterin, Prasanth G. Narasimha-Shenoi, 2012, izvirni znanstveni članek

Opis: The smallest tree that contains all vertices of a subset ▫$W$▫ of ▫$V(G)$▫ is called a Steiner tree. The number of edges of such a tree is the Steiner distance of ▫$W$▫ and union of all Steiner trees of ▫$W$▫ form a Steiner interval. Both of them are described for the lexicographic product in the present work. We also give a complete answer for the following invariants with respect to the Steiner convexity: the Steiner number, the rank, the hull number, and the Carathéodory number, and a partial answer for the Radon number. At the end we locate and repair a small mistake from [J. Cáceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, On the geodetic and the hull numbers in strong product graphs, Comput. Math. Appl. 60 (2010) 3020--3031].
Ključne besede: teorija grafov, leksikografski produkt, Steinerjeva konveksnost, Steinerjeva množica, Steinerjeva razdalja, graph theory, lexicographic product, Steiner convexity, Steiner set, Steiner distance
Objavljeno: 10.07.2015; Ogledov: 372; Prenosov: 50
URL Povezava na celotno besedilo

Iskanje izvedeno v 0.24 sek.
Na vrh
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici