Naval Postgraduate School
The Independence Number for the Generalized Petersen Graphs
GenPetersen.pdf (196.0Kb)Abstract
Given a graph G, an independent set (I(G) is a subset of the vertices of G such that no two vertices in I(G) are adjacent. The independence number (G) is the order of a largest set of independent vertices. In this paper, we study the independence number for the Generalized Petersen graphs, finding both sharp bounds and exact results for subclasses of the Genralized Petersen graphs.
Description
Ars Combinatoria 103 (2012), 439-451.
Ars Combin. 103 (2012) pp 439-451 (accepted 2007)
Collections
Related items
Showing items related by title, author, creator and subject.
-
Competitive Weighted Matching in Transversal Matroids
(2010-09);Consider a bipartite graph with a set of left-vertices and a set of right-vertices. All the edges adjacent to the same left-vertex have the same weight. We present an algorithm that, given the set of right-vertices and the ... -
Stratified domination in oriented graphs
(2007);An oriented graph is 2-stratified if its vertex set is partitioned into two classes, where the vertices in one class are colored red and those in the other class are colored blue. Let H be a 2-stratified oriented graph ... -
On stratification and domination in graphs
(2006);A graph G is 2-stratified if its vertex set is partitioned into two classes (each of which is a stratum or a color class), where the vertices in one class are colored red and those in the other class are colored blue. Let ...
