On the k-path vertex cover of some graph products

Jakovac, Marko; Taranenko, Andrej

| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Prva stran > Izpis gradiva

Izpis gradiva

Naslov:	On the k-path vertex cover of some graph products
Avtorji:	ID Jakovac, Marko (Avtor) ID Taranenko, Andrej (Avtor)
Datoteke:	http://dx.doi.org/10.1016/j.disc.2012.09.010
Jezik:	Angleški jezik
Vrsta gradiva:	Delo ni kategorizirano
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	FNM - Fakulteta za naravoslovje in matematiko
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
Leto izida:	2013
Št. strani:	str. 94-100
Številčenje:	Vol. 313, iss. 1
PID:	20.500.12556/DKUM-50595
UDK:	519.17
COBISS.SI-ID:	19464968
DOI:	10.1016/j.disc.2012.09.010
ISSN pri članku:	0012-365X
NUK URN:	URN:SI:UM:DK:ZJN22EFI
Datum objave v DKUM:	10.07.2015
Število ogledov:	1486
Število prenosov:	29
Metapodatki:
Področja:	Ostalo
:	JAKOVAC, Marko in TARANENKO, Andrej, 2013, On the k-path vertex cover of some graph products. Discrete mathematics [na spletu]. 2013. Vol. 313, no. 1, p. 94–100. [Dostopano 23 marec 2025]. DOI 10.1016/j.disc.2012.09.010. Pridobljeno s: http://dx.doi.org/10.1016/j.disc.2012.09.010 Kopiraj citat