Daisy cubes and distance cube polynomial
From MaRDI portal
Publication:2311367
DOI10.1016/J.EJC.2018.02.019zbMATH Open1415.05121arXiv1705.08674OpenAlexW2963508913MaRDI QIDQ2311367FDOQ2311367
Authors: Sandi Klavžar, Michel Mollard 
Publication date: 10 July 2019
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Abstract: Let X {0, 1} n. Then the daisy cube Q n (X) is introduced as the sub-graph of Q n induced by the intersection of the intervals I(x, 0 n) over all x X. Daisy cubes are partial cubes that include Fibonacci cubes, Lucas cubes, and bipartite wheels. If u is a vertex of a graph G, then the distance cube polynomial D G,u (x, y) is introduced as the bivariate polynomial that counts the number of induced subgraphs isomorphic to Q k at a given distance from the vertex u. It is proved that if G is a daisy cube, then D G,0 n (x, y) = C G (x + y -- 1), where C G (x) is the previously investigated cube polynomial of G. It is also proved that if G is a daisy cube, then D G,u (x, --x) = 1 holds for every vertex u in G.
Full work available at URL: https://arxiv.org/abs/1705.08674
Recommendations
Cites Work
- Handbook of product graphs
- There are no finite partial cubes of girth more than 6 and minimum degree at least 3
- Title not available (Why is that?)
- Isometric embedding in products of complete graphs
- Convexity in partial cubes: the hull number
- Distance-preserving subgraphs of hypercubes
- Geometry of cuts and metrics
- Structure of Fibonacci cubes: a survey
- On the Lucas cubes
- A new characterization and a recognition algorithm of Lucas cubes
- Extremal combinatorics. With applications in computer science
- On disjoint hypercubes in Fibonacci cubes
- Counting disjoint hypercubes in Fibonacci cubes
- Generalized fibonacci cubes are mostly hamiltonian
- Proofs of two conjectures on generalized Fibonacci cubes
- Generalized Fibonacci cubes
- Cube polynomial of Fibonacci and Lucas cubes
- Families of Non-disjoint subsets
- Gated sets in metric spaces
- The structure of median graphs
- A new characterization of median graphs
- Non covered vertices in Fibonacci cubes by a maximum set of disjoint hypercubes
- On gated sets in graphs
- Graphs and cubes
- A convexity lemma and expansion procedures for bipartite graphs
- The cube polynomial and its derivatives: The case of median graphs
- Isometric subgraphs of Hamming graphs and d-convexity
- Roots of cube polynomials of median graphs
- Two relations for median graphs
- \(q\)-counting hypercubes in Lucas cubes
- A correction of a characterization of planar partial cubes
- A characterization of planar partial cubes
- The rupture degree and gear graphs
- Netlike partial cubes III. The median cycle property
- \(q\)-cube enumerator polynomial of Fibonacci cubes
- Classification of Vertex‐Transitive Cubic Partial Cubes
Cited In (14)
- On the chromatic polynomial and the domination number of \(k\)-Fibonacci cubes
- Cube-complements of generalized Fibonacci cubes
- Edges in Fibonacci cubes, Lucas cubes and complements
- Boundary enumerator polynomial of hypercubes in Fibonacci cubes
- Fibonacci and Lucas \(p\)-cubes
- Efficient proper embedding of a daisy cube
- Fibonacci-run graphs. I: Basic properties
- Lucas-run graphs
- Resonance graphs of kinky benzenoid systems are daisy cubes
- On the domination number and the total domination number of Fibonacci cubes
- Resonance graphs of catacondensed even ring systems
- From modular decomposition trees to rooted median graphs
- Daisy cubes: a characterization and a generalization
- Resonance Graphs and a Binary Coding of Perfect Matchings of Outerplane Bipartite Graphs
This page was built for publication: Daisy cubes and distance cube polynomial
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2311367)
