×

Distinguishing number of hierarchical products of graphs. (English) Zbl 1461.05175

Summary: The distinguishing number \(D(G)\) of a graph \(G\) is the least number \(k\) such that \(G\) has a coloring with \(k\) colors that is only preserved by the trivial automorphism. In this paper, we study the distinguishing number of hierarchical products of graphs. The distinguishing number of hierarchical products of two complete graphs is determined. We obtain an upper bound for the distinguishing number of the hierarchical product of two connected graphs. Moreover, the distinguishing number is determined for the hierarchical product of an arbitrary graph by a special graph such as a complete graph, a hierarchical power of \(K_2\), or a tree.

MSC:

05C76 Graph operations (line graphs, products, etc.)
05C15 Coloring of graphs and hypergraphs
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahmadi, B.; Alinaghipour, F.; Shekarriz, M. H., Number of distinguishing colorings and partitions, Discrete Math., 343, 9, Article 111984 pp. (2020) · Zbl 1443.05057
[2] Albertson, M. O.; Boutin, D. L., Using determining sets to distinguish Kneser graphs, Electron. J. Comb., 14, Article R20 pp. (2007) · Zbl 1114.05089
[3] Albertson, M. O.; Collins, K. L., Symmetry breaking in graphs, Electron. J. Comb., 3, 1, Article 18 pp. (1996)
[4] Alikhani, S.; Soltani, S., Distinguishing number and distinguishing index of certain graphs, Filomat, 31, 14, 4393-4404 (2017) · Zbl 1405.05049
[5] Alikhani, S.; Soltani, S., The distinguishing number and the distinguishing index of line and graphoidal graph(s), AKCE Int. J. Graphs Comb., 17, 1, 1-6 (2020)
[6] Arezoomand, M.; Taeri, B., Applications of generalized hierarchical product of graphs in computing the szeged index of chemical graphs, MATCH Commun. Math. Comput. Chem., 64, 591-602 (2010) · Zbl 1265.05567
[7] Andersona, S. E.; Guob, Y.; Tenney, A.; Wash, K. A., Prime factorization and domination in the hierarchical product of graphs, Discuss. Math., Graph Theory, 37, 873-890 (2017) · Zbl 1375.05208
[8] Arvind, V.; Cheng, C.; Devanur, N., On computing the distinguishing numbers of planar graphs and beyond: a counting approach, SIAM J. Discrete Math., 22, 4, 1297-1324 (2008) · Zbl 1226.05210
[9] Barrière, L.; Comellas, F.; Dalfó, C.; Fiol, M. A., The hierarchical product of graphs, Discrete Appl. Math., 157, 36-48 (2009) · Zbl 1200.05196
[10] Barrière, L.; Dalfó, C.; Fiol, M. A.; Mitjana, M., The generalized hierarchical product of graphs, Discrete Math., 309, 3871-3881 (2009) · Zbl 1210.05120
[11] Bogstad, B.; Cowen, L. J., The distinguishing number of the hypercube, Discrete Math., 283, 29-35 (2004) · Zbl 1044.05039
[12] Bondy, J. A.; Murty, U. S.R., Graph Theory, GTM, vol. 244 (2008), Springer · Zbl 1134.05001
[13] Chan, M., The distinguishing number of the direct and wreath product action, J. Algebraic Comb., 24, 331-345 (2006) · Zbl 1113.20002
[14] Cheng, C. T., On computing the distinguishing numbers of trees and forests, Electron. J. Comb., 13, 1, Article 11 pp. (2006)
[15] Cheng, C. T., On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results, Discrete Math., 309, 5169-5182 (2009) · Zbl 1213.05071
[16] Collins, K. L.; Trenk, A. N., The distinguishing chromatic number, Electron. J. Comb., 13, 1, Article 16 pp. (2006) · Zbl 1081.05033
[17] Eliasi, M.; Iranmanesh, A., Hosoya polynomial of hierarchical product of graphs, MATCH Commun. Math. Comput. Chem., 69, 1, 111-119 (2013) · Zbl 1299.05174
[18] Fisher, M. J.; Isaak, G., Distinguishing colorings of Cartesian products of complete graphs, Discrete Math., 308, 2240-2246 (2008) · Zbl 1147.05029
[19] Imrich, W.; Jerebic, J.; Klavžar, S., The distinguishing number of Cartesian products of complete graphs, Eur. J. Comb., 29, 922-929 (2008) · Zbl 1205.05198
[20] Imrich, W.; Klavžar, S.; Trofimov, V., Distinguishing infinite graphs, Electron. J. Comb., 14, 1, Article 36 pp. (2007)
[21] Russell, A.; Sundaram, R., A note on the asymptotics and computational complexity of graph distinguishability, Electron. J. Comb., 5, Article R23 pp. (1998)
[22] Skardal, P. S.; Wash, K., Spectral properties of the hierarchical product of graphs, Phys. Rev. E, 94, Article 052311 pp. (2016)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.