𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Short Dominating Paths and Cycles in the Binary Hypercube

✍ Scribed by Uri Blass; Iiro Honkala; Mark G. Karpovsky; Simon Litsyn

Publisher
Springer
Year
2001
Tongue
English
Weight
92 KB
Volume
5
Category
Article
ISSN
0218-0006

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Long dominating cycles and paths in grap
Long dominating cycles and paths in graphs with large neighborhood unions
✍ H. J. Broersma; H. J. Veldman πŸ“‚ Article πŸ“… 1991 πŸ› John Wiley and Sons 🌐 English βš– 413 KB πŸ‘ 1 views

## Abstract Let __G__ be a graph of order __n__ and define __NC(G)__ = min{|__N__(__u__) βˆͺ __N__(__v__)| |__uv__ βˆ‰ __E__(__G__)}. A cycle __C__ of __G__ is called a __dominating cycle__ or __D__‐__cycle__ if __V__(__G__) ‐ __V__(__C__) is an independent set. A __D__‐__path__ is defined analogously.

Cycles identifying vertices and edges in
Cycles identifying vertices and edges in binary hypercubes and 2-dimensional tori
✍ Iiro Honkala; Mark G. Karpovsky; Simon Litsyn πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 272 KB

A set of subgraphs C1; C2; : : : ; C k in a graph G is said to identify the vertices (resp. the edges) if the sets {j: v ∈ Cj} (resp. {j: e ∈ Cj}) are nonempty for all the vertices v (edges e) and no two are the same set. We consider the problem of minimizing k when the subgraphs Ci are required to

Hamiltonian cycles and paths with a pres
Hamiltonian cycles and paths with a prescribed set of edges in hypercubes and dense sets
✍ Rostislav Caha; V. Koubek πŸ“‚ Article πŸ“… 2005 πŸ› John Wiley and Sons 🌐 English βš– 275 KB πŸ‘ 1 views

## Abstract This paper studies techniques of finding hamiltonian paths and cycles in hypercubes and dense sets of hypercubes. This problem is, in general, easily solvable but here the problem was modified by the requirement that a set of edges has to be used in such path or cycle. The main result o