The k-independence number of graph products

  • Yaping Mao
  • Eddie Cheng
  • Zhao Wang
  • Zhiwei Guo

Abstract

The concept of k-independent number is a natural generalization of classical independence number. A k-independent set is a set of vertices whose induced subgraph has maximum degree at most k. The k-independence number of G, denoted by αk(G), is defined as the maximum cardinality of a k-independent set of G. In this paper, we study the k-independence number on the lexicographical, strong, Cartesian and direct product and present several upper and lower bounds for these products of graphs.

Published
2017-11-02
Section
Articles