Further results on monotonic graph invariants and bipartiteness number

  • Hanlin Chen
  • Jia-Bao Liu
Keywords: Graph invariants, bipartiteness number, extremal values

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

Published
2019-05-09
Section
Articles

Journal Identifiers


eISSN: 1727-933X
print ISSN: 1607-3606