On the vertex k-path cover

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

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;

Data

Language:	English
Year of publishing:	2013
Typology:	1.01 - Original Scientific Article
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
UDC:	519.17
COBISS:	19859464
ISSN:	0166-218X
Views:	351
Downloads:	6
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
URN:	URN:SI:UM:
Type (COBISS):	Not categorized
Pages:	str. 1943-1949
Volume:	Vol. 161
Issue:	iss. 13/14
Chronology:	2013
ID:	1477049