Efficient proper embedding of a daisy cube

DOI10.26493/1855-3974.2454.892MaRDI QIDQ5020294zbMATH OpenOpenAlexFDO

Authors Aleksander Vesel

Publication date 5 January 2022

Published in Ars Mathematica Contemporanea (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2006.08712

zbMATH Keywords

daisy cubeisometric embeddingpartial cubeproper embedding

Mathematics Subject Classification ID

Distance in graphs (05C12) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: For a set $X$ of binary words of length $h$ the daisy cube $Q_h(X)$ is defined as the subgraph of the hypercube $Q_h$ induced by the set of all vertices on shortest paths that connect vertices of $X$ with the vertex $0^h$. A vertex in the intersection of all of these paths is a minimal vertex of a daisy cube. A graph $G$ isomorphic to a daisy cube admits several isometric embeddings into a hypercube. We show that an isometric embedding is proper if and only if the label $0^h$ is assigned to a minimal vertex of $G$. This result allows us to devise an algorithm which finds a proper embedding of a graph isomorphic to a daisy cube into a hypercube in linear time.

Recommendations

• Daisy cubes: a characterization and a generalization
• Efficient Embeddings into Hypercube-like Topologies
• Embedding of Grids into Optimal Hypercubes
• Optimal embeddings of the exchanged hypercube and the dual-cube as vertex-induced subgraphs of the hypercube
• Embeddings of hypercubes and grids into de Bruijn graphs

Cites work

• Circular embeddability of isometric words
• Cube-complements of generalized Fibonacci cubes
• Daisy cubes and distance cube polynomial
• Daisy cubes: a characterization and a generalization
• Generalized Fibonacci and Lucas cubes arising from powers of paths and cycles
• Generalized Fibonacci cubes
• Handbook of product graphs
• scientific article; zbMATH DE number 3697163 (Why is no real title available?)
• Isometric embedding in products of complete graphs
• Isometric embeddings of subdivided connected graphs into hypercubes
• On domination-type invariants of Fibonacci cubes and hypercubes
• On the domination number and the total domination number of Fibonacci cubes
• Resonance graphs of kinky benzenoid systems are daisy cubes
• The parameters of Fibonacci and Lucas cubes

Cited in

(3)

• Daisy cubes: a characterization and a generalization
• Resonance graphs of plane bipartite graphs as daisy cubes
• Resonance graphs that are daisy cubes: from hypercubes to independent sets via resonant sets

This page was built for publication: Efficient proper embedding of a daisy cube

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