2019/05/17 by Andrej Taranenko, Taranenko, Andrej · 1 citation
Computer Science · Mathematics · #05C75 #05C85 #68R10 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO #msc:05C75 #msc:05C85 #msc:68R10
paper · pdf · doi:10.48550/arxiv.1905.07243
arxiv created 2019/05/17 · arxiv updated 2019/05/20
Daisy cubes are a recently introduced class of isometric subgraphs of hypercubes Qn. They are induced with intervals between chosen vertices of Qn and the vertex 0n∈ V(Qn). In this paper we characterize daisy cubes in terms of an expansion procedure thus answering an open problem proposed by Klavžar and Mollard, 2018, in the introductory paper of daisy cubes \citeKlaMol-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.