| | 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 / 10
Na začetekNa prejšnjo stran1Na naslednjo stranNa konec
1.
The Hosoya-Wiener polynomial of weighted trees
Blaž Zmazek, Janez Žerovnik, 2007, izvirni znanstveni članek

Opis: Formulas for the Wiener number and the Hosoya-Wiener polynomial of edge and vertex weighted graphs are given in terms of edge and path contributions. For a rooted tree, the Hosoya-Wiener polynomial is expressed as a sum of vertex contributions. Finally, a recursive formula for computing the Hosoya-Wiener polynomial of a weighted tree is given.
Ključne besede: mathematics, graph theory, Hosoya-Wiener polynomial, weighted tree, vertex weighted graphs
Objavljeno v DKUM: 05.07.2017; Ogledov: 686; Prenosov: 70
.pdf Celotno besedilo (182,69 KB)
Gradivo ima več datotek! Več...

2.
Edge-transitive lexicographic and cartesian products
Wilfried Imrich, Ali Iranmanesh, Sandi Klavžar, Abolghasem Soltani, 2016, izvirni znanstveni članek

Opis: In this note connected, edge-transitive lexicographic and Cartesian products are characterized. For the lexicographic product ▫$G \circ H$▫ of a connected graph ▫$G$▫ that is not complete by a graph ▫$H$▫, we show that it is edge-transitive if and only if ▫$G$▫ is edge-transitive and ▫$H$▫ is edgeless. If the first factor of ▫$G \circ H$▫ is non-trivial and complete, then ▫$G \circ H$▫ is edge-transitive if and only if ▫$H$▫ is the lexicographic product of a complete graph by an edgeless graph. This fixes an error of Li, Wang, Xu, and Zhao (Appl. Math. Lett. 24 (2011) 1924--1926). For the Cartesian product it is shown that every connected Cartesian product of at least two non-trivial factors is edge-transitive if and only if it is the Cartesian power of a connected, edge- and vertex-transitive graph.
Ključne besede: edge-transitive graph, vertex-transitive graph, lexicographic product of graphs, Cartesian product of graphs
Objavljeno v DKUM: 31.03.2017; Ogledov: 639; Prenosov: 363
.pdf Celotno besedilo (150,33 KB)
Gradivo ima več datotek! Več...

3.
On the vertex k-path cover
Boštjan Brešar, Marko Jakovac, Ján Katrenič, Gabriel Semanišin, Andrej Taranenko, 2013, izvirni znanstveni članek

Opis: A subset ▫$S$▫ of vertices of a graph ▫$G$▫ is called a vertex ▫$k$▫-path cover if every path of order ▫$k$▫ in ▫$G$▫ contains at least one vertex from ▫$S$▫. Denote by ▫$psi_k(G)$▫ the minimum cardinality of a vertex ▫$k$▫-path cover in ▫$G$▫. In this paper, an upper bound for ▫$psi_3$▫ in graphs with a given average degree is presented. A lower bound for ▫$psi_k$▫ of regular graphs is also proven. For grids, i.e. the Cartesian products of two paths, we give an asymptotically tight bound for ▫$psi_k$▫ and the exact value for ▫$psi_3$▫.
Ključne besede: matematika, teorija grafov, vozliščno pokritje, regularni grafi, mreže, mathematics, graph theory, vertex cover, grids
Objavljeno v DKUM: 10.07.2015; Ogledov: 821; Prenosov: 19
URL Povezava na celotno besedilo

4.
Minimum k-path vertex cover
Boštjan Brešar, František Kardoš, Ján Katrenič, Gabriel Semanišin, 2011, izvirni znanstveni članek

Opis: Podmnožica ▫$S$▫ množice vozlišč grafa ▫$G$▫ se imenuje po poteh ▫$k$▫-vozliščno pokritje, če vsaka pot reda ▫$k$▫ v grafu ▫$G$▫ vsebuje vsaj eno vozlišče iz ▫$S$▫. Označimo s ▫$psi_k(G)$▫ najmanjšo kardinalnost po poteh ▫$k$▫-vozliščnega pokritja v grafu ▫$G$▫. V članku dokažemo, da je problem določitve ▫$psi_k(G)$▫ NP-poln problem za vsak ▫$k geq 2$▫, medtem ko lahko za drevesa ta problem rešimo v linearnem času. Raziskujemo zgornje meje za vrednost ▫$psi_k(G)$▫ in dokažemo več ocen ter točnih vrednosti za to število. Prav tako dokažemo, da je ▫$psi_3(G) leq (2n + m)/6$▫, za vsak graf ▫$G$▫ z ▫$n$▫ vozlišči in ▫$m$▫ povezavami.
Ključne besede: matematika, teorija grafov, algoritem, vozliščno pokritje, pot, NP-polnost, disociacijsko število, po poteh vozliščno pokritje, mathematics, graph theory, algorithm, path, vertex cover, dissociation number, path vertex cover, NP-complete
Objavljeno v DKUM: 10.07.2015; Ogledov: 729; Prenosov: 9
URL Povezava na celotno besedilo

5.
Transitive, locally finite median graphs with finite blocks
Wilfried Imrich, Sandi Klavžar, 2009, izvirni znanstveni članek

Opis: V članku obravnavamo neskončne, lokalno končne, vozliščno-tranzitivne medianske grafe. Pokazano je, da končnost ▫$Theta$▫-razredov takih grafov ne zagotavlja končnosti blokov. Bloki pa postanejo neskončni, če nadalje nobeno končno zaporedje ▫$Theta$▫-kontrakcij ne naredi novih prereznih vozlišč. Dokazano je, da obstaja končno mnogo vozliščno-tranzitivnih medianskih grafov fiksne stopnje, ki imajo končne bloke. Konstruirana je neskončna družina vozliščno-tranzitivnih medianskih grafov z intranzitivnimi bloki. Podan je tudi seznam vseh vozliščno-tranzitivnih medianskih grafov stopnje 4.
Ključne besede: teorija grafov, medianski grafi, neskočni grafi, vozliščno-tranzitivni grafi, graph theory, median graphs, infinite graphs, vertex-transitive graphs
Objavljeno v DKUM: 10.07.2015; Ogledov: 914; Prenosov: 88
URL Povezava na celotno besedilo

6.
Transitive, locally finite median graphs with finite blocks
Wilfried Imrich, Sandi Klavžar, 2008

Opis: V članku obravnavamo neskončne, lokalno končne, vozliščno-tranzitivne medianske grafe. Pokazano je, da končnost ▫$Theta$▫-razredov takih grafov ne zagotavlja končnosti blokov. Bloki pa postanejo neskončni, če nadalje nobeno končno zaporedje ▫$Theta$▫-kontrakcij ne naredi novih prereznih vozlišč. Dokazano je, da obstaja končno mnogo vozliščno-tranzitivnih medianskih grafov fiksne stopnje, ki imajo končne bloke. Konstruirana je neskončna družina vozliščno-tranzitivnih medianskih grafov z intranzitivnimi bloki. Podan je tudi seznam vseh vozliščno-tranzitivnih medianskih grafov stopnje 4.
Ključne besede: teorija grafov, medianski grafi, neskočni grafi, vozliščno-tranzitivni grafi, graph theory, median graphs, infinite graphs, vertex-transitive graphs
Objavljeno v DKUM: 10.07.2015; Ogledov: 962; Prenosov: 80
URL Povezava na celotno besedilo

7.
Maximal proper subgraphs of median graphs
Boštjan Brešar, Sandi Klavžar, 2007, izvirni znanstveni članek

Opis: Za medianski graf ▫$G$▫ in vozlišče ▫$v$▫, ki ni presečno, dokažemo, da je ▫$G-v$▫ medianski graf natanko tedaj, ko ▫$v$▫ ni center dvodelnega kolesa. To je nadalje ekvivalentno obstoju določene eliminacijske sheme za povezave, ki so incidenčne z ▫$v$▫. Rezultat implicira karakterizacijo po vozliščih kritičnih (po vozliščih polnih) medianskih grafov, ki so medianski grafi, katerih vsi podgrafi brez enega vozlišča niso medianski (so medianski). Podani sta tudi dve analogni karakterizaciji za primer odstranjevanja povezav.
Ključne besede: matematika, teorija grafov, medianski graf, podgraf brez enega vozlišča, dvodelno kolo, kvadratna povezava, mathematics, graph theory, median graph, vertex-deleted subgraph, bipartite wheel, square-eddge, square-dismantlable vertex
Objavljeno v DKUM: 10.07.2015; Ogledov: 622; Prenosov: 67
URL Povezava na celotno besedilo

8.
9.
10.
On the k-path vertex cover of some graph products
Marko Jakovac, Andrej Taranenko, 2013, izvirni znanstveni članek

Opis: A subset S of vertices of a graph G is called a k-path vertex cover if every path of order k in G contains at least one vertex from S. Denote by ▫$psi_k$▫(G) the minimum cardinality of a k-path vertex cover in G. In this paper, improved lower and upper bounds for ▫$psi_k$▫ of the Cartesian and the strong product of paths are derived. It is shown that for ▫$psi_3$▫ those bounds are tight. For the lexicographic product bounds are presented for ▫$psi_k$▫, moreover ▫$psi_2$▫ and ▫$psi_3$▫ are exactly determined for the lexicographic product of two arbitrary graphs. As a consequence the independence and the dissociation number of the lexicographic product are given.
Ključne besede: matematika, teorija grafov, vozliščno pokritje, po poteh vozliščno pokritje, disociacijsko število, neodvisnostno število, grafovski produkti, mathematics, graph theory, vertex cover, path vertex cover, dissociation number, independence number, graph products
Objavljeno v DKUM: 10.07.2015; Ogledov: 874; Prenosov: 14
URL Povezava na celotno besedilo

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