Independence number of generalized Petersen graphs.

zbMATH Open1413.05280arXiv1008.2583MaRDI QIDQ2828909FDOQ2828909

Authors: Nazli Besharati, J. B. Ebrahimi, A. Azadi 

Publication date: 26 October 2016

Published in: Ars Combinatoria (Search for Journal in Brave)

Abstract: 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 cite{MR2381433} it is conjectured that $$, for all $n$ and $k$. 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 fix $k$, $alpha(P(n,k))$ can be computed using an algorithm with running time O(n).

Full work available at URL: https://arxiv.org/abs/1008.2583

Recommendations

• On minimum vertex covers of generalized Petersen graphs
• scientific article; zbMATH DE number 6116809
• On the independent domination number of the generalized Petersen graphs
• On the minimum vertex cover of generalized Petersen graphs
• On the domination number of some graphs

zbMATH Keywords

independent settree decompositiongeneralized Petersen graphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distance in graphs (05C12)

Cited In (6)

• Title not available (Why is that?)
• Minimum Coprime Labelings of Generalized Petersen and Prism Graphs
• On \(\delta^{(k)}\)-coloring of generalized Petersen graphs
• On the independent domination number of the generalized Petersen graphs
• On minimum vertex covers of generalized Petersen graphs
• Eternal domination of generalized Petersen graph

This page was built for publication: Independence number of generalized Petersen graphs.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2828909)