The Independence Number for the Generalized Petersen Graphs

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 alpha(G) is the order of the 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 Generalized Petersen graphs.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2011
Accession Number
ADA548758

Entities

People

  • Joseph Fox
  • Pantelimon Stanica
  • Ralucca Gera

Organizations

  • Naval Postgraduate School

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Applied Mathematics
  • Classification
  • Graph Theory
  • Information Operations
  • Mathematics
  • Sequences
  • Triangles
  • Websites

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.