The k-independence number of graph products

Authors

  • Yaping Mao Qinghai Normal University, China
  • Eddie Cheng Oakland University, United States https://orcid.org/0000-0003-4526-7983
  • Zhao Wang Beijing Normal University, China
  • Zhiwei Guo Qinghai Normal University, China

DOI:

https://doi.org/10.26493/2590-9770.1216.6d2

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.

Downloads

Published

2017-11-02

Issue

Vol. 1 No. 1 (2018)

Section

Articles