On the minimum vertex cover of generalized Petersen graphs

Autor:	David G. L. Wang, Dannielle D.D. Jin
Rok vydání:	2019
Předmět:	Combinatorics Applied Mathematics Vertex cover Discrete Mathematics and Combinatorics Generalized Petersen graph Valuation (measure theory) Mathematics
Zdroj:	Discrete Applied Mathematics. 266:309-318
ISSN:	0166-218X
DOI:	10.1016/j.dam.2018.12.011
Popis:	It is known that any vertex cover of the generalized Petersen graph P ( n , k ) has size at least n . Behsaz, Hatami and Mahmoodian characterized such graphs with minimum vertex cover numbers n and n + 1 , and those with k ≤ 3 . For k ≥ 4 and n ≥ 2 k + 2 , we prove that if the 2-adic valuation of n is less than or equal to that of k , then the minimum vertex cover number of P ( n , k ) equals n + 2 if and only if n ∈ { 2 k + 2 , 3 k − 1 , 3 k + 1 } .
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::3c99d3702852f5f869b690755a2422b6 https://doi.org/10.1016/j.dam.2018.12.011 Zobrazit plný text záznamu Full Text from ScienceDirect