Geodesic
Daisy Hamming graphs
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 2, pp. 421-436 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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 ℋ and characterize those daisy graphs generated by X of cardinality 2 that are isometric in ℋ. Finally, we give a characterization of isometric daisy graphs of a Hamming graph K_k_1⋯ K_k_n with respect to 0^n in terms of an expansion procedure.
Keywords: daisy graphs, expansion, isometric subgraphs 
@article{DMGT_2023_43_2_a6,
     author = {Dravec, Tanja and Taranenko, Andrej},
     title = {Daisy {Hamming} graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {421--436},
     year = {2023},
     volume = {43},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a6/}
}
TY  - JOUR
AU  - Dravec, Tanja
AU  - Taranenko, Andrej
TI  - Daisy Hamming graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 421
EP  - 436
VL  - 43
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a6/
LA  - en
ID  - DMGT_2023_43_2_a6
ER  - 
%0 Journal Article
%A Dravec, Tanja
%A Taranenko, Andrej
%T Daisy Hamming graphs
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 421-436
%V 43
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a6/
%G en
%F DMGT_2023_43_2_a6
Dravec, Tanja; Taranenko, Andrej. Daisy Hamming graphs. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 2, pp. 421-436. http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a6/

[1] 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

[2] 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

[3] 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

[4] V.D. Chepoi, Isometric subgraphs of Hamming graphs and d-convexity, Cybernet. Systems Anal. 24 (1988) 6–11. https://doi.org/10.1007/BF01069520

[5] 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

[6] 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

[7] 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

[8] 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

[9] H.M. Mulder, The Interval Function of a Graph, in: Mathematical 429 Centre Tracts 132 (Mathematisch Centrum, Amsterdam, 1980).

[10] H.M. Mulder, The structure of median graphs, Discrete Math. 24 (1978) 197–204. https://doi.org/10.1016/0012-365X(78)90199-1

[11] E. Munarini, C.P. Cippo and N.Z. Salvi, On the Lucas cubes, Fibonacci Quart. 39 (2001) 12–21.

[12] A. Taranenko, A new characterization and a recognition algorithm of Lucas cubes, Discrete Math. Theor. Comput. Sci. 15 (2013) 31–39.

[13] A. Taranenko, Daisy cubes: A characterization and a generalization, European J. Combin. 85 (2020) 103058. https://doi.org/10.1016/j.ejc.2019.103058

[14] A. Vesel, Cube-complements of generalized Fibonacci cubes, Discrete Math. 342 (2019) 1139–1146. https://doi.org/10.1016/j.disc.2019.01.008

[15] 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

[16] P. Žigert Pleteršek, Resonance graphs of kinky benzenoid systems are daisy cubes, MATCH Commun. Math. Comput. Chem. 80 (2018) 207–214.