| | 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 - 2 / 2
Na začetekNa prejšnjo stran1Na naslednjo stranNa konec
1.
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: 10.07.2015; Ogledov: 417; Prenosov: 7
URL Povezava na celotno besedilo

2.
The k-independence number of direct products of graphs and Hedetniemi's conjecture
Simon Špacapan, 2011, izvirni znanstveni članek

Opis: The ▫$k$▫-independence number of ▫$G$▫, denoted as ▫$alpha_k(G)$▫, is the size of a largest ▫$k$▫-colorable subgraph of ▫$G$▫. The direct product of graphs ▫$G$▫ and ▫$H$▫, denoted as ▫$G times H$▫, is the graph with vertex set ▫$V(G) times V(H)$▫, where two vertices ▫$(x_1, y_1)$▫ and ▫$(x_2, y_2)$▫ are adjacent in ▫$G times H$▫, if ▫$x_1$▫ is adjacent to ▫$x_2$▫ in ▫$G$▫ and ▫$y_1$▫ is adjacent to ▫$y_2$▫ in ▫$H$▫. We conjecture that for any graphs ▫$G$▫ and ▫$H$▫, ▫$$alpha_k(G times H) ge alpha_k(G)|V(H)| + alpha_k(H)|V(G)| - alpha_k(G) alpha_k(H).$$▫ The conjecture is stronger than Hedetniemi's conjecture. We prove the conjecture for ▫$k = 1, 2$▫ and prove that ▫$alpha_k(G times H) ge alpha_k(G)|V(H)| + alpha_k(H)|V(G)| - alpha_k(G) alpha_k(H)$▫ holds for any ▫$k$▫.
Ključne besede: matematika, teorija grafov, neodvisnostno število, kartezični produkt grafov, mathematics, graph theory, independence number, Cartesian product of graphs
Objavljeno: 10.07.2015; Ogledov: 519; Prenosov: 10
URL Povezava na celotno besedilo

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