| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Naslov: On the k-path vertex cover of some graph products Jakovac, Marko (Avtor)Taranenko, Andrej (Avtor) http://dx.doi.org/10.1016/j.disc.2012.09.010 Angleški jezik Delo ni kategorizirano (r6) 1.01 - Izvirni znanstveni članek FNM - Fakulteta za naravoslovje in matematiko 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. 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 2013 str. 94-100 Vol. 313, iss. 1 519.17 19464968 10.1016/j.disc.2012.09.010 0012-365X URN:SI:UM:DK:ZJN22EFI 609 12 Ostalo

Skupna ocena: (0 glasov) Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. AddThis uporablja piškotke, za katere potrebujemo vaše privoljenje.Uredi privoljenje...

Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.