[feed] pefprints@pef.uni-lj.si | [feed] Atom [feed] RSS 1.0 [feed] RSS 2.0 |
  Logo Login | Create Account

The independence number of a graph

Nina Šere (2020) The independence number of a graph. MSc thesis.

Download (1833Kb)


    In the master's thesis we are dealing with the independence number of a graph. We show, that the well-known problem 3-SAT is reducible to the corresponding decision problem, the so-called independent set problem, which proves that the independent set problem is NP-complete. We then determine the independence number for different graphs, including some very well known infinite families of graphs like complete graphs, multi-partite complete graphs, cycle graphs, hypercube graphs, etc. In the last part of the thesis we focus on the family of generalized Petersen graphs GP(n,k). Based on their construction it is clear, that n is the upper bound for the independence number for GP(n,k). Moreover, if n is odd, the upper bound is n-1. In the master's thesis we determine the exact value of the independence number for different values of parameter k.

    Item Type: Thesis (MSc thesis)
    Keywords: independent set, independence number, NP-completeness, generalized Petersen graphs
    Number of Pages: 65
    Language of Content: Slovenian
    Mentor / Comentors:
    Mentor / ComentorsIDFunction
    izr. prof. dr. Primož ŠparlMentor
    Link to COBISS: https://plus.si.cobiss.net/opac7/bib/peflj/27336195
    Institution: University of Ljubljana
    Department: Faculty of Education
    Item ID: 6371
    Date Deposited: 07 Sep 2020 09:38
    Last Modified: 07 Sep 2020 09:38
    URI: http://pefprints.pef.uni-lj.si/id/eprint/6371

    Actions (login required)

    View Item