Premium
Dominating sets in n ‐cubes
Author(s) -
Weichsel Paul M.
Publication year - 1994
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190180506
Subject(s) - combinatorics , hypercube , mathematics , conjecture , vertex (graph theory) , graph , induced subgraph , discrete mathematics , dimension (graph theory)
A perfectdominatingset S of a graph Γ is a set of vertices of Γ such that every vertex of Γ is either in S or is adjacent to exactly one vertex of S. We show that a perfect dominating set of the n ‐cube Q n induces a subgraph of Q n whose components are isomorphic to hypercubes. We conjecture that each of these hypercubes has the same dimension. We then prove that if Q r is a component of the subgraph induced by S , then n − r 1 or 3 (mod 6). A number of examples are given and connections with Steiner Systems and codes are noted.