Graph theoretic properties of good sets in hypercube

Abstract

A good set on k vertices is a vertex induced subgraph of the hypercube $Q_n$ that has the maximum number of edges. In this paper we discuss graph theoretic properties of good sets including connectivity, vertex decomposition, domination and identifying path covers of good sets.

Keywords:

• Hypercube
• domination
• decomposition

Mathematics Subject Classifications:

• 05C90
• 05C69
• 06E99
• 68R10
• 94B99

Disclosure statement

The authors declare that no funds, grants, or other support were received during the preparation of this manuscript. Also, the authors have no relevant financial or non-financial interests to disclose. All authors contributed to the study conception and design. Data sharing not applicable to this article as no datasets were generated or analysed during the current study. We confirm that neither the manuscript nor any part of its content is presently under consideration or published in another journal. All authors have approved the manuscript and agree with its submission to International Journal of Computer Mathematics: Computer System Theory.