On the vertex k-path cover

被引：46

作者：

Bresar, Bostjan ^{[1
,2
]}

Jakovac, Marko ^{[1
,2
]}

Katrenic, Jan ^{[3
]}

Semanisin, Gabriel ^{[3
]}

Taranenko, Andrej ^{[1
,2
]}

机构：

[1] Univ Maribor, Fac Nat Sci & Math, Koroska 160, SLO-2000 Maribor, Slovenia

[2] Inst Math Phys & Mech, Ljubljana 1000, Slovenia

[3] Safarik Univ, Inst Comp Sci, Kosice 04154, Slovakia

来源：

DISCRETE APPLIED MATHEMATICS | 2013年 / 161卷 / 13-14期

关键词：

k-path vertex cover; Average degree; Regular graphs; Grids; BIPARTITE GRAPHS;

D O I：

10.1016/j.dam.2013.02.024

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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). (C) 2013 Elsevier B.V. All rights reserved.

引用

页码：1943 / 1949

页数：7

共 8 条

[1] NP-hard graph problems and boundary classes of graphs [J].

Alekseev, V. E. ;

Boliac, R. ;

Korobitsyn, D. V. ;

Lozin, V. V. .

THEORETICAL COMPUTER SCIENCE, 2007, 389 (1-2) :219-236

[2]

Boliac R, 2004, ARS COMBINATORIA, V72, P241

[3] Minimum k-path vertex cover [J].

Bresar, Bostjan ;

Kardos, Frantisek ;

Katrenic, Jan ;

Semanisin, Gabriel .

DISCRETE APPLIED MATHEMATICS, 2011, 159 (12) :1189-1195

[4]

Novotny M, 2010, LECT NOTES COMPUT SC, V6033, P106, DOI 10.1007/978-3-642-12368-9_8

[5] The complexity of dissociation set problems in graphs [J].

Orlovich, Yury ;

Dolgui, Alexandre ;

Finke, Gerd ;

Gordon, Valery ;

Werner, Frank .

DISCRETE APPLIED MATHEMATICS, 2011, 159 (13) :1352-1366

[6] A factor 2 approximation algorithm for the vertex cover P3 problem [J].

Tu, Jianhua ;

Zhou, Wenli .

INFORMATION PROCESSING LETTERS, 2011, 111 (14) :683-686

[7] NODE-DELETION PROBLEMS ON BIPARTITE GRAPHS [J].

YANNAKAKIS, M .

SIAM JOURNAL ON COMPUTING, 1981, 10 (02) :310-327

[8]

[No title captured]

← 1 →