1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Daisy Hamming Graphs

Published Online: 16 Dec 2020
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 27 May 2020
Accepted: 20 Oct 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
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 ℋ 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 Kk1 □ … □Kkn with respect to 0n in terms of an expansion procedure.

Keywords

MSC 2010

[1] B. Brešar, Partial Hamming graphs and expansion procedures, Discrete Math. 237 (2001) 13–27. doi: 10.1016/S0012-365X(00)00362-9Open DOISearch in Google Scholar

[2] B. Brešar, W. Imrich and S. Klavžar, Tree-like isometric subgraphs of hypercubes, Discuss. Math. Graph Theory 23 (2003) 227–240. doi: 10.7151/dmgt.1199Open DOISearch in Google Scholar

[3] S. Brezovnik, N. Tratnik and P. Žigert Pleteršek, Resonance graphs of catacondensed even ring systems, Appl. Math. Comput. 374 (2020) 125064. doi: 10.1016/j.amc.2020.125064Open DOISearch in Google Scholar

[4] V.D. Chepoi, Isometric subgraphs of Hamming graphs and d-convexity, Cybernet. Systems Anal. 24 (1988) 6–11. doi: 10.1007/BF01069520Open DOISearch in Google Scholar

[5] D. Ž. Djoković, Distance-preserving subgraphs of hypercubes, J. Combin. Theory Ser. B 14 (1973) 263–267. doi: 10.1016/0095-8956(73)90010-5Open DOISearch in Google Scholar

[6] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, 2nd Edition (CRC Press, Boca Raton, 2011). doi: 10.1201/b10959Open DOISearch in Google Scholar

[7] S. Klavžar, Structure of Fibonacci cubes: A survey, J. Comb. Optim. 25 (2013) 505–522. doi: 10.1007/s10878-011-9433-zOpen DOISearch in Google Scholar

[8] S. Klavžar and M. Mollard, Daisy cubes and distance cube polynomial, European J. Combin. 80 (2019) 214–223. doi: 10.1016/j.ejc.2018.02.019Open DOISearch in Google Scholar

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

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

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

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

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

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

[15] E. Wilkeit, Isometric embeddings in Hamming graphs, J. Combin. Theory Ser. B 50 (1990) 179–197. doi: 10.1016/0095-8956(90)90073-9Open DOISearch in Google Scholar

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

Recommended articles from Trend MD

Plan your remote conference with Sciendo