On the vertex k-path cover

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

Povzetek

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$▫.

Ključne besede

matematika;teorija grafov;vozliščno pokritje;regularni grafi;mreže;mathematics;graph theory;vertex cover;grids;

Podatki

Jezik:	Angleški jezik
Leto izida:	2013
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
UDK:	519.17
COBISS:	19859464
ISSN:	0166-218X
Št. ogledov:	351
Št. prenosov:	6
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 1943-1949
Letnik:	Vol. 161
Zvezek:	iss. 13/14
Čas izdaje:	2013
ID:	1477049