Further results on monotonic graph invariants and bipartiteness number

Abstract

The bipartiteness of a graph is the minimum number of vertices whose deletion from G results in a bipartite graph. If a graph invariant decreases or increases with addition of edges of its complement, then it is called a monotonic graph invariant. In this article, we determine the extremal values of some famous monotonic graph invariants, and characterize the corresponding extremal graphs in the class of all connected graphs with a given vertex bipartiteness.

Mathematics Subject Classication (2010): 05C07, 05C15, 05C50.

Keywords: Graph invariants, bipartiteness number, extremal values