The Independence Number for the Generalized Petersen Graphs

reportActive / Technical Report | Accession Number: ADA548758 | Open PDF

Abstract:

Given a graph G, an independent set IG is a subset of the vertices of G such that no two vertices in IG are adjacent. The independence number alphaG 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.

Author(s):
Fox, Joseph ; Gera, Ralucca ; Stanica, Pantelimon
Author Organization(s):
NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF APPLIED MATHEMATICS
Descriptive Note:
Research paper
Supplementary Note:
Accepted for publication in Ars Combinatoria.
Pagination:
0014

Security Markings

DOCUMENT & CONTEXTUAL SUMMARY

Distribution:
Approved For Public Release
Distribution Statement:
Approved For Public Release; Distribution Is Unlimited.

RECORD

Collection: TR
Identifying Numbers
Monitor Series:
NPS-DAM
 Subject Terms
Joint Capability Areas:
JCA_8_Building Partnerships
Communities of Interest:
No COI(s) Identified
Descriptor(s):
*GRAPHS, APPLIED MATHEMATICS, COMBINATORIAL ANALYSIS, EDGES, POLYGONS, THEORY
Field(s)/Group(s):
Theoretical Mathematics
Keyword(s):
*INDEPENDENCE NUMBER, *GENERALIZED PETERSEN GRAPHS, INDEPENDENT VERTICES, LOWER BOUNDS, UPPER BOUNDS, CUBIC GRAPHS, STAR POLYGONS, REGULAR POLYGONS, INTEGERS
Report Date:
2010 Jan 01
Creation Date:
2011 Oct 18