On recursively directed hypercubes
type: Item
instance of: scholarly article
title: On recursively directed hypercubes
zbMATH Open document ID: 0995.05103
author: Carmel Domshlak
published in: The Electronic Journal of Combinatorics
publication date: 2002-06-10T00:00:00Z
full work available at URL: https://eudml.org/doc/122071
full work available at URL: v9i1r23.html
review text: Summary: We introduce the recursively directed hypercubes, and analyze some of their structural properties. We show that every recursively directed hypercube is acyclic, and has a unique pair of source and sink nodes. The main contribution of the paper is an analysis of distances between the nodes in such a graph. We show that the distance from the source node to any other node, and from any node to the sink node is bounded by \(n+1\), where \(n\) is the dimension of the hypercube, but the diameter of a recursively directed hypercube may be exponential in \(n\).
Mathematics Subject Classification ID: 05C62
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 91B08
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 1753162
zbMATH Keywords: recursively directed hypercubes
zbMATH Keywords: distances
zbMATH Keywords: diameter
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1753162