An algorithm for finding the Independence Number of a graph

2008/01/03 by Omar Kettani, Kettani, Omar
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Graph theory and applications #cs.DM #cs.DS

paper · pdf · doi:10.48550/arxiv.0801.0590

15 pages; a corrected proof for the second method is added

arxiv created 2008/01/09 · arxiv updated 2009/12/01

Abstract

In this paper, we prove that for every connected graph G, there exists a split graph H with the same independence number and the same order. Then we propose a first algorithm for finding this graph, given the degree sequence of the input graph G. Further, we propose a second algorithm for finding the independence number of G, given the adjacency matrix of G.

Related

• Sharp upper bounds on the k-independence number in graphs with given minimum and maximum degree
• Unified bounds for the independence number of graph powers
• A new lower bound on the independence number of a graph
• On independence domination
• Relating the independence number and the dissociation number