000217853 001__ 217853
000217853 005__ 20181203024225.0
000217853 022__ $$a0381-7032
000217853 02470 $$2ISI$$a000369773900020
000217853 037__ $$aARTICLE
000217853 245__ $$aIndependence number of generalized Petersen graphs
000217853 260__ $$bCharles Babbage Res Ctr$$c2016$$aWinnipeg
000217853 269__ $$a2016
000217853 300__ $$a17
000217853 336__ $$aJournal Articles
000217853 520__ $$aDetermining 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).
000217853 6531_ $$aGeneralized Petersen Graphs
000217853 6531_ $$aIndependent Set
000217853 6531_ $$aTree Decomposition
000217853 700__ $$uUniv Mazandaran, Dept Math Sci, Babol Sar, Iran$$aBesharati, Nazli
000217853 700__ $$uEcole Polytech Fed Lausanne, Stn 14, CH-1015 Lausanne, Switzerland$$aEbrahimi, J. B.
000217853 700__ $$aAzadi, A.
000217853 773__ $$j124$$tArs Combinatoria$$q239-255
000217853 909C0 $$xU12921$$0252575$$pTHL3
000217853 909CO $$pIC$$particle$$ooai:infoscience.tind.io:217853
000217853 937__ $$aEPFL-ARTICLE-217853
000217853 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL
000217853 980__ $$aARTICLE