1. The Hosoya-Wiener polynomial of weighted treesBlaž 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
 Celotno besedilo (182,69 KB)
Gradivo ima več datotek! Več...
|
2. Edge-transitive lexicographic and cartesian productsWilfried 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
Celotno besedilo (150,33 KB)
Gradivo ima več datotek! Več...
|
3. On the vertex k-path coverBoš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
 Povezava na celotno besedilo |
4. Minimum k-path vertex coverBoš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
Povezava na celotno besedilo |
5. Transitive, locally finite median graphs with finite blocksWilfried 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
Povezava na celotno besedilo |
6. Transitive, locally finite median graphs with finite blocksWilfried 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
Povezava na celotno besedilo |
7. Maximal proper subgraphs of median graphsBoš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
Povezava na celotno besedilo |
8. Bendall, Sarah; Hammack, Richard: Centers of $n$-fold tensor products of graphs. (English summary). - Discuss. Math. Graph Theory 24 (2004), no. 3, 491--501.Sandi Klavžar, 2005, recenzija, prikaz knjige, kritika Ključne besede: matematika, teorija grafov, center, radij, mathematics, graph theory, center, vertex eccentricity, radius
Objavljeno v DKUM: 10.07.2015; Ogledov: 440; Prenosov: 20
Povezava na celotno besedilo |
9. A counterexample to the uniform shortest path routing conjecture for vertex-transitive graphsJozef Širáň, Sangho Shim, Janez Žerovnik, 2000, objavljeni povzetek znanstvenega prispevka na konferenci Ključne besede: matematika, teorija grafov, po vozliščih prehodni grafi, najkrajše poti, krepki produkt, mathematics, graph theory, vertex-transitive graphs, shortest paths, strong product
Objavljeno v DKUM: 10.07.2015; Ogledov: 723; Prenosov: 23
Povezava na celotno besedilo |
10. On the k-path vertex cover of some graph productsMarko 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
Povezava na celotno besedilo |
