On the k-path vertex cover of some graph products
Povzetek
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.
Ključne besede
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;
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: |
19464968
|
| ISSN: | 0012-365X |
| Št. ogledov: | 891 |
| Št. prenosov: | 14 |
| Ocena: | 0 (0 glasov) |
| Metapodatki: |
|
Ostali podatki
| Sekundarni jezik: | Angleški jezik |
|---|---|
| URN: | URN:SI:UM: |
| Vrsta dela (COBISS): | Delo ni kategorizirano |
| Strani: | str. 94-100 |
| Letnik: | ǂVol. ǂ313 |
| Zvezek: | ǂiss. ǂ1 |
| Čas izdaje: | 2013 |
| DOI: | 10.1016/j.disc.2012.09.010 |
| ID: | 1440224 |
Priporočena dela:
On the k-path vertex cover of some graph products
2013,
ni podatka o podnaslovu
Minimum k-path vertex cover
2011,
ni podatka o podnaslovu
On the vertex k-path cover
2013,
ni podatka o podnaslovu
t-tonska barvanja
2014,
magistrsko delo
Strongly distance-balanced graphs and graph products
2008,
ni podatka o podnaslovu