independence number

independence number

[‚in·di′pen·dəns ‚nəm·bər]
(mathematics)
For a graph, the largest possible number of vertices in an independent set. Also known as internal stability number.
References in periodicals archive ?
A set of rectangles is said to be independent if they are pairwise independent, and we define the independence number of a set of axis-parallel rectangles to be the size of the largest independent set of rectangles it contains.
It follows readily that if [Real part] is a set of closed axis-parallel rectangles and [Imaginary part] is the corresponding set of 2-intervals then the independence number of [Real part] is equal to the packing number of [Imaginary part].
If a finite collection [Real part] of axis-parallel rectangles has independence number at most m then there is a collection of 4m vertical and horizontal lines which slice every rectangle in [Real part].
will take significantly The 2015 UK general election factor in be a complicating negotiations, if the Labour Party independence number of secure a substantial seats in Scotland but fail to win or outright majority commanding in the House of Commons.
Thus the independence number of SR(d, n) is the maximum number of nonattacking rooks that can be placed on a simplicial chessboard with n + 1 "squares" on each side.
The smallest eigenvalue is significant in spectral graph theory; for instance, it is related to the independence number (Godsil and Royle, 2001, Lemma 9.
The independence number and edge independence number of G are respectively denoted by [[beta].
There is a vast amount of literature concerning conditions in terms of for instance order, size, vertex degrees, degree sums, independence number, chromatic number, feedback vertex sets that are sufficient for the existence of some number of vertex-disjoint cycles, which may additionally contain specified elements or satisfy certain length conditions.
Schiermeyer, Independence number and vertex-disjoint cycles, Discrete Math.
c](G) is equal to the number of vertices minus the independence number of G in this case.
Locke [18] constructed an infinite family of connected cubic triangle-free graphs with n := 30k + 22 vertices and independence number 11k + 8.
Graph coloring and related topics of cliques, independence numbers, and graph factorization are addressed next.

Full browser ?