On the vertex k-path cover

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

| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Prva stran > Izpis gradiva

Izpis gradiva

Naslov:	On the vertex k-path cover
Avtorji:	ID Brešar, Boštjan (Avtor) ID Jakovac, Marko (Avtor) ID Katrenič, Ján (Avtor) ID Semanišin, Gabriel (Avtor) ID Taranenko, Andrej (Avtor)
Datoteke:	http://dx.doi.org/10.1016/j.dam.2013.02.024
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 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
Leto izida:	2013
Št. strani:	str. 1943-1949
Številčenje:	Vol. 161, iss. 13/14
PID:	20.500.12556/DKUM-52029
UDK:	519.17
COBISS.SI-ID:	19859464
ISSN pri članku:	0166-218X
NUK URN:	URN:SI:UM:DK:6HE67TVJ
Datum objave v DKUM:	10.07.2015
Število ogledov:	1639
Število prenosov:	29
Metapodatki:
Področja:	Ostalo
:	BREŠAR, Boštjan, JAKOVAC, Marko, KATRENIČ, Ján, SEMANIŠIN, Gabriel in TARANENKO, Andrej, 2013, On the vertex k-path cover. Discrete applied mathematics [na spletu]. 2013. Vol. 161, no. 13/14, p. 1943–1949. [Dostopano 22 marec 2025]. Pridobljeno s: http://dx.doi.org/10.1016/j.dam.2013.02.024 Kopiraj citat