A new notion of vertex independence and rank for finite graphs

2012/01/19 by John Rhodes, Rhodes, John, Pedro V. Silva +1
Computer Science · Mathematics · #05B35 #05C25 #05C50 #16Y60 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Representation Theory (math.RT) #cs.DM #math.CO #math.RT #msc:05B35 #msc:05C25 #msc:05C50 #msc:16Y60

paper · pdf · doi:10.48550/arxiv.1201.3984

47 pages

arxiv created 2012/02/13 · arxiv updated 2012/10/29

Abstract

A new notion of vertex independence and rank for a finite graph G is introduced. The independence of vertices is based on the boolean independence of columns of a natural boolean matrix associated to G. Rank is the cardinality of the largest set of independent columns. Some basic properties and some more advanced theorems are proved. Geometric properties of the graph are related to its rank and independent sets.

Related

• C-independence and c-rank of posets and lattices
• An algorithm for finding the Independence Number of a graph
• On Unique Independence Weighted Graphs
• On Vertex Rankings of Graphs and its Relatives
• The 1-nearly vertex independence number of a graph