On recursively directed hypercubes

MaRDI QIDQ1599526zbMATH OpenFDO

Authors Carmel Domshlak

Publication date 10 June 2002

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/122071, http://www.emis.de/journals/EJC/Volume_9/Abstracts/v9i1r23.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

diameterdistancesrecursively directed hypercubes

Mathematics Subject Classification ID

Distance in graphs (05C12) Paths and cycles (05C38) Graph representations (geometric and intersection representations, etc.) (05C62) Individual preferences (91B08)

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\).

Recommendations

• Acyclic directed hypercubes may have exponential diameter
• A note on diameter of acyclic directed hypercubes
• On the unidirectional hyper-stars
• Topological properties of the directional hypercube
• Oriented hypercubes

Cited in

(7)

• Acyclic directed hypercubes may have exponential diameter
• Decycling hypercubes
• Positive and negative cycles in Boolean networks
• Vertex-degree based topological indices of digraphs
• Asynchronous simulation of Boolean networks by monotone Boolean networks
• Hypercubes As Direct Products
• A note on diameter of acyclic directed hypercubes

This page was built for publication: On recursively directed hypercubes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1599526)