217853
20181203024225.0
0381-7032
000369773900020
ISI
ARTICLE
Independence number of generalized Petersen graphs
Winnipeg
2016
Charles Babbage Res Ctr
2016
17
Journal Articles
Determining the size of a maximum independent set of a graph G, denoted by alpha(G), is an NP-hard problem. Therefore many attempts are made to find upper and lower bounds, or exact values of alpha(G) for special classes of graphs. This paper is aimed toward studying this problem for the class of generalized Petersen graphs. We find new upper and lower bounds and some exact values for alpha(P(n, k)). With a computer program we have obtained exact values for each n < 78. In [2] it is conjectured that the size of the minimum vertex cover, beta(P(n, k)), is less than or equal to n + inverted right perpendicular n/5 inverted left perpendicular, for all n and k with n > 2k. We prove this conjecture for some cases. In particular, we show that if n > 3k, the conjecture is valid. We checked the conjecture with our table for n < 78 and it had no inconsistency. Finally, we show that for every fixed k, alpha(P(n,k)) can be computed using an algorithm with running time O(n).
Generalized Petersen Graphs
Independent Set
Tree Decomposition
Besharati, Nazli
Univ Mazandaran, Dept Math Sci, Babol Sar, Iran
Ebrahimi, J. B.
Ecole Polytech Fed Lausanne, Stn 14, CH-1015 Lausanne, Switzerland
Azadi, A.
239-255
Ars Combinatoria
124
THL3
252575
U12921
oai:infoscience.tind.io:217853
article
IC
EPFL-ARTICLE-217853
EPFL
PUBLISHED
REVIEWED
ARTICLE