On the k-path vertex cover of some graph products

Jakovac, Marko; Taranenko, Andrej

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	On the k-path vertex cover of some graph products
Authors:	ID Jakovac, Marko (Author) ID Taranenko, Andrej (Author)
Files:	http://dx.doi.org/10.1016/j.disc.2012.09.010
Language:	English
Work type:	Not categorized
Typology:	1.01 - Original Scientific Article
Organization:	FNM - Faculty of Natural Sciences and Mathematics
Abstract:	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.
Keywords:	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
Year of publishing:	2013
Number of pages:	str. 94-100
Numbering:	Vol. 313, iss. 1
PID:	20.500.12556/DKUM-50595
UDC:	519.17
ISSN on article:	0012-365X
COBISS.SI-ID:	19464968
DOI:	10.1016/j.disc.2012.09.010
NUK URN:	URN:SI:UM:DK:ZJN22EFI
Publication date in DKUM:	10.07.2015
Views:	1486
Downloads:	29
Metadata:
Categories:	Misc.
:	JAKOVAC, Marko and TARANENKO, Andrej, 2013, On the k-path vertex cover of some graph products. Discrete mathematics [online]. 2013. Vol. 313, no. 1, p. 94–100. [Accessed 22 March 2025]. DOI 10.1016/j.disc.2012.09.010. Retrieved from: http://dx.doi.org/10.1016/j.disc.2012.09.010 Copy citation