Article in volume
Authors:
Title:
Daisy Hamming graphs
PDFSource:
Discussiones Mathematicae Graph Theory 43(2) (2023) 421-436
Received: 2020-05-27 , Revised: 2020-10-20 , Accepted: 2020-10-20 , Available online: 2020-11-16 , https://doi.org/10.7151/dmgt.2373
Abstract:
Daisy graphs of a rooted graph $G$ with the root $r$ were recently introduced
as a generalization of daisy cubes, a class of isometric subgraphs of hypercubes.
In this paper we first address a problem posed in [A. Taranenko, Daisy
cubes: A characterization and a generalization, European J. Combin. 85 (2020)
#103058] and characterize rooted graphs $G$ with the root $r$ for which all
daisy graphs of $G$ with respect to $r$ are isometric in $G$, assuming the graph
$G$ satisfies the rooted triangle condition. We continue the investigation of
daisy graphs $G$ (generated by $X$) of a Hamming graph $\mathcal{H}$ and
characterize those daisy graphs generated by $X$ of cardinality 2 that are
isometric in $\mathcal{H}$. Finally, we give a characterization of isometric
daisy graphs of a Hamming graph $K_{k_1}\Box \cdots \Box K_{k_n}$ with respect
to $0^n$ in terms of an expansion procedure.
Keywords:
daisy graphs, expansion, isometric subgraphs
References:
- B. Brešar, Partial Hamming graphs and expansion procedures, Discrete Math. 237 (2001) 13–27.
https://doi.org/10.1016/S0012-365X(00)00362-9 - B. Brešar, W. Imrich and S. Klavžar, Tree-like isometric subgraphs of hypercubes, Discuss. Math. Graph Theory 23 (2003) 227–240.
https://doi.org/10.7151/dmgt.1199 - S. Brezovnik, N. Tratnik and P. Žigert Pleteršek, Resonance graphs of catacondensed even ring systems, Appl. Math. Comput. 374 (2020) 125064.
https://doi.org/10.1016/j.amc.2020.125064 - V.D. Chepoi, Isometric subgraphs of Hamming graphs and d-convexity, Cybernet. Systems Anal. 24 (1988) 6–11.
https://doi.org/10.1007/BF01069520 - D.Ž. Djoković, Distance-preserving subgraphs of hypercubes, J. Combin. Theory Ser. B 14 (1973) 263–267.
https://doi.org/10.1016/0095-8956(73)90010-5 - R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, 2nd Edition (CRC Press, Boca Raton, 2011).
https://doi.org/10.1201/b10959 - S. Klavžar, Structure of Fibonacci cubes: A survey, J. Comb. Optim. 25 (2013) 505–522.
https://doi.org/10.1007/s10878-011-9433-z - S. Klavžar and M. Mollard, Daisy cubes and distance cube polynomial, European J. Combin. 80 (2019) 214–223.
https://doi.org/10.1016/j.ejc.2018.02.019 - H.M. Mulder, The Interval Function of a Graph, in: Mathematical 429 Centre Tracts 132 (Mathematisch Centrum, Amsterdam, 1980).
- H.M. Mulder, The structure of median graphs, Discrete Math. 24 (1978) 197–204.
https://doi.org/10.1016/0012-365X(78)90199-1 - E. Munarini, C.P. Cippo and N.Z. Salvi, On the Lucas cubes, Fibonacci Quart. 39 (2001) 12–21.
- A. Taranenko, A new characterization and a recognition algorithm of Lucas cubes, Discrete Math. Theor. Comput. Sci. 15 (2013) 31–39.
- A. Taranenko, Daisy cubes: A characterization and a generalization, European J. Combin. 85 (2020) 103058.
https://doi.org/10.1016/j.ejc.2019.103058 - A. Vesel, Cube-complements of generalized Fibonacci cubes, Discrete Math. 342 (2019) 1139–1146.
https://doi.org/10.1016/j.disc.2019.01.008 - E. Wilkeit, Isometric embeddings in Hamming graphs, J. Combin. Theory Ser. B 50 (1990) 179–197.
https://doi.org/10.1016/0095-8956(90)90073-9 - P. Žigert Pleteršek, Resonance graphs of kinky benzenoid systems are daisy cubes, MATCH Commun. Math. Comput. Chem. 80 (2018) 207–214.
Close