Displaying similar documents to “Bounds of graph parameters for global constraints”

Some news about the independence number of a graph

Jochen Harant (2000)

Discussiones Mathematicae Graph Theory

Similarity:

For a finite undirected graph G on n vertices some continuous optimization problems taken over the n-dimensional cube are presented and it is proved that their optimum values equal the independence number of G.

On the Maximum and Minimum Sizes of a Graph with Givenk-Connectivity

Yuefang Sun (2017)

Discussiones Mathematicae Graph Theory

Similarity:

The concept of k-connectivity κk(G), introduced by Chartrand in 1984, is a generalization of the cut-version of the classical connectivity. For an integer k ≥ 2, the k-connectivity of a connected graph G with order n ≥ k is the smallest number of vertices whose removal from G produces a graph with at least k components or a graph with fewer than k vertices. In this paper, we get a sharp upper bound for the size of G with κk(G) = t, where 1 ≤ t ≤ n − k and k ≥ 3; moreover, the unique...