On the k-path vertex cover of some graph products
Abstract
A subset S of vertices of a graph G is called a k-path vertex 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 k-path vertex cover in G. In this paper, improved lower and upper bounds for ▫$\psi_k$▫ of the Cartesian and the strong product of paths are derived. It is shown that for ▫$\psi_3$▫ those bounds are tight. For the lexicographic product bounds are presented for ▫$\psi_k$▫, moreover ▫$\psi_2$▫ and ▫$\psi_3$▫ are exactly determined for the lexicographic product of two arbitrary graphs. As a consequence the independence and the dissociation number of the lexicographic product are given.
Keywords
matematika;teorija grafov;vozliščno pokritje;po poteh vozliščno pokritje;disociacijsko število;neodvisnostno število;grafovski produkti;mathematics;graph theory;vertex cover;path vertex cover;dissociation number;independence number;graph products;
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: |
19464968
|
| ISSN: | 0012-365X |
| Views: | 891 |
| Downloads: | 14 |
| Average score: | 0 (0 votes) |
| Metadata: |
|
Other data
| Secondary language: | English |
|---|---|
| URN: | URN:SI:UM: |
| Type (COBISS): | Not categorized |
| Pages: | str. 94-100 |
| Volume: | ǂVol. ǂ313 |
| Issue: | ǂiss. ǂ1 |
| Chronology: | 2013 |
| DOI: | 10.1016/j.disc.2012.09.010 |
| ID: | 1440224 |
Recommended works:
On the k-path vertex cover of some graph products
2013,
no subtitle data available
Minimum k-path vertex cover
2011,
no subtitle data available
On the vertex k-path cover
2013,
no subtitle data available
t-tonska barvanja
2014,
magistrsko delo
Strongly distance-balanced graphs and graph products
2008,
no subtitle data available