The k-independence number of graph products

  • Yaping Mao Qinghai Normal University, China
  • Eddie Cheng Oakland University, United States
  • Zhao Wang Beijing Normal University, China
  • Zhiwei Guo Qinghai Normal University, China
Keywords: Independence number, k-independent set, k-independence number, lexicographical product, strong product, Cartesian product, direct product

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