TY - JOUR
T1 - On the minimum vertex cover of generalized Petersen graphs
AU - Jin, Dannielle D.D.
AU - Wang, David G.L.
N1 - Publisher Copyright:
© 2018 Elsevier B.V.
PY - 2019/8/15
Y1 - 2019/8/15
N2 - 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≥2k+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∈{2k+2,3k−1,3k+1}.
AB - 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≥2k+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∈{2k+2,3k−1,3k+1}.
KW - Generalized Petersen graph
KW - Independent set
KW - Minimum vertex cover
UR - http://www.scopus.com/inward/record.url?scp=85059765524&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2018.12.011
DO - 10.1016/j.dam.2018.12.011
M3 - Article
AN - SCOPUS:85059765524
SN - 0166-218X
VL - 266
SP - 309
EP - 318
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
ER -