✦ LIBER ✦

Dominating sets in n-cubes

✍ Scribed by Paul M. Weichsel

Publisher: John Wiley and Sons
Year: 1994
Tongue: English
Weight: 525 KB
Volume: 18
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190180506

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

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.

📜 SIMILAR VOLUMES

Dominating Sets in Planar Graphs

✍ Lesley R. Matheson; Robert E. Tarjan 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 174 KB

Dominating sets in triangulations on sur

Dominating sets in triangulations on surfaces

✍ Tatsuya Honjo; Ken-ichi Kawarabayashi; Atsuhiro Nakamoto 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 194 KB 👁 1 views

## Abstract Let __G__ be a graph and let __S__⊂__V__(__G__). We say that __S__ is __dominating__ in __G__ if each vertex of __G__ is in __S__ or adjacent to a vertex in __S__. We show that every triangulation on the torus and the Klein bottle with __n__ vertices has a dominating set of cardinality

Independent dominating sets and hamilton

Independent dominating sets and hamiltonian cycles

✍ Penny Haxell; Ben Seamone; Jacques Verstraete 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 168 KB

## Abstract A graph is uniquely hamiltonian if it contains exactly one hamiltonian cycle. In this note we prove that there are no __r__‐regular uniquely hamiltonian graphs when __r__ > 22. This improves upon earlier results of Thomassen. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 233–244, 20

Dominating sets with small clique coveri

Dominating sets with small clique covering number

✍ Penrice, Stephen G. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 84 KB 👁 2 views

Motivated by earlier work on dominating cliques, we show that if a graph G is connected and contains no induced subgraph isomorphic to P 6 or H t (the graph obtained by subdividing each edge of K 1,t , t ≥ 3, by exactly one vertex), then G has a dominating set which induces a connected graph with cl

Rainbow connection number and connected

Rainbow connection number and connected dominating sets

✍ L. Sunil Chandran; Anita Das; Deepak Rajendraprasad; Nithin M. Varma 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 167 KB

## Abstract The __rainbow connection number__ of a connected graph is the minimum number of colors needed to color its edges, so that every pair of its vertices is connected by at least one path in which no two edges are colored the same. In this article we show that for every connected graph on __

Set domination in graphs

✍ E. Sampathkumar; L. Pushpa Latha 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 355 KB

## Abstract Let __G__ = (__V, E__) be a connected graph. A set __D__ ⊂ __V__ is a __set‐dominating set__ (sd‐set) if for every set __T__ ⊂ __V__ − __D__, there exists a nonempty set __S__ ⊂ __D__ such that the subgraph 〈__S__ ∪ __T__〉 induced by __S__ ∪ __T__ is connected. The set‐domination number