Daisy cubes: a characterization and a generalization

DOI10.1016/J.EJC.2019.103058MaRDI QIDQ2297914zbMATH OpenOpenAlexWikidataFDO

Authors Andrej Taranenko

Publication date 20 February 2020

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

bipartite wheelsFibonacci cubesisometric subgraphs of hypercubesLucas cubes

Mathematics Subject Classification ID

Distance in graphs (05C12) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: Daisy cubes are a recently introduced class of isometric subgraphs of hypercubes $Q_n$. They are induced with intervals between chosen vertices of $Q_n$ and the vertex $0^{n}inV(Q_n)$. In this paper we characterize daisy cubes in terms of an expansion procedure thus answering an open problem proposed by Klavv{z}ar and Mollard, 2018, in the introductory paper of daisy cubes cite{KlaMol-18}. To obtain such a characterization several interesting properties of daisy cubes are presented. For a given graph $G$ isomorphic to a daisy cube, but without the corresponding embedding into a hypercube, we present an algorithm which finds a proper embedding of $G$ into a hypercube in $O(mn)$ time. Finally, daisy graphs of a rooted graph are introduced and shown to be a generalization of daisy cubes.

Recommendations

• Efficient proper embedding of a daisy cube
• Daisy cubes and distance cube polynomial
• Resonance graphs of kinky benzenoid systems are daisy cubes
• Disjoint cycles and spanning graphs of hypercubes
• Cube-complements of generalized Fibonacci cubes

Cites work

• A new characterization and a recognition algorithm of Lucas cubes
• Cube-complements of generalized Fibonacci cubes
• Daisy cubes and distance cube polynomial
• Handbook of product graphs
• Isometric embedding in products of complete graphs
• Isometric subgraphs of Hamming graphs and d-convexity
• On the Lucas cubes
• Resonance graphs of kinky benzenoid systems are daisy cubes
• Structure of Fibonacci cubes: a survey

Cited in

(10)

• From modular decomposition trees to rooted median graphs
• Daisy cubes and distance cube polynomial
• Daisy structure in Desarguesian projective planes
• Resonance graphs of kinky benzenoid systems are daisy cubes
• Efficient proper embedding of a daisy cube
• On the chromatic polynomial and the domination number of \(k\)-Fibonacci cubes
• A decomposition structure of resonance graphs that are daisy cubes
• Daisy Hamming graphs
• 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: Daisy cubes: a characterization and a generalization

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