On the vertex k-path cover

Brešar, Boštjan; Jakovac, Marko; Katrenič, Ján; Semanišin, Gabriel; Taranenko, Andrej

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	On the vertex k-path cover
Authors:	ID Brešar, Boštjan (Author) ID Jakovac, Marko (Author) ID Katrenič, Ján (Author) ID Semanišin, Gabriel (Author) ID Taranenko, Andrej (Author)
Files:	http://dx.doi.org/10.1016/j.dam.2013.02.024
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 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$ .
Keywords:	matematika, teorija grafov, vozliščno pokritje, regularni grafi, mreže, mathematics, graph theory, vertex cover, grids
Year of publishing:	2013
Number of pages:	str. 1943-1949
Numbering:	Vol. 161, iss. 13/14
PID:	20.500.12556/DKUM-52029
UDC:	519.17
ISSN on article:	0166-218X
COBISS.SI-ID:	19859464
NUK URN:	URN:SI:UM:DK:6HE67TVJ
Publication date in DKUM:	10.07.2015
Views:	1639
Downloads:	29
Metadata:
Categories:	Misc.
:	BREŠAR, Boštjan, JAKOVAC, Marko, KATRENIČ, Ján, SEMANIŠIN, Gabriel and TARANENKO, Andrej, 2013, On the vertex k-path cover. Discrete applied mathematics [online]. 2013. Vol. 161, no. 13/14, p. 1943–1949. [Accessed 17 March 2025]. Retrieved from: http://dx.doi.org/10.1016/j.dam.2013.02.024 Copy citation