zbMATH — the first resource for mathematics

Harmonious order of graphs. (English) Zbl 1188.05138
Summary: We consider the following generalization of the concept of harmonious graphs. Given a graph \(G=(V,E)\) and a positive integer \(t\geq|E|\), a function \(\widetilde{h}:V(G)\to\mathbb Z_t\) is called a \(t\)-harmonious labeling of \(G\) if \(\widetilde{h}\) is injective for \(t\geq|V|\) or surjective for \(t<|V|\), and \(\widetilde{h}(v)+ \widetilde{h}(w)\neq \widetilde{h}(x)+ \widetilde{h}(y)\) for all distinct edges \(vw,xy\in E(G)\). Then the smallest possible \(t\) such that \(G\) has a \(t\)-harmonious labeling is named the harmonious order of \(G\). We determine the harmonious order of some non-harmonious graphs, such as complete graphs \(K_n\) \((n\geq5)\), complete bipartite graphs \(K_{m,n}\) \((m,n>1)\), even cycles \(C_n\), some powers of paths \(P_n^k\), disjoint unions of triangles \(nK_3\) (\(n\) even). We also present some general results concerning harmonious order of the Cartesian product of two given graphs or harmonious order of the disjoint union of copies of a given graph. Furthermore, we establish an upper bound for harmonious order of trees.

05C78 Graph labelling (graceful graphs, bandwidth, etc.)
Full Text: DOI
[1] Acharya, B.D.; Hegde, S.M., Arithmetic graphs, J. graph theory, 14, 275-299, (1990) · Zbl 0735.05071
[2] Aldred, R.E.L.; McKay, Brendan D., Graceful and harmonious labellings of trees, ICA bull., 23, 69-72, (1998) · Zbl 0909.05040
[3] Arumugam, S.; Germina, K., On indexable graphs, Discrete math., 161, 285-289, (1996) · Zbl 0869.05058
[4] Balakrishnan, R.; Selvam, A.; Yegnanarayanan, V., Some results on elegant graphs, Indian J. pure appl. math., 28, 905-916, (1997) · Zbl 0890.05063
[5] Baumert, L.D., ()
[6] Beals, R.; Gallian, J.; Headley, P.; Jungreis, D., Harmonious groups, J. combin. theory ser. A, 56, 223-238, (1991) · Zbl 0718.20013
[7] Bolian, L.; Xiankun, Z., On harmonious labelings of graphs, Ars combin., 36, 315-326, (1993) · Zbl 0793.05102
[8] Bose, R.C., An affine analogue of singer’s theorem, J. Indian math. soc., 6, 1-15, (1942) · Zbl 0063.00542
[9] Bu, C.; Shi, J., Some conclusions about indexable graphs, J. Harbin eng. univ., 16, 92-94, (1995)
[10] Cahit, I., On harmonious tree labelings, Ars combin., 41, 311-317, (1995) · Zbl 0846.05072
[11] Chang, G.J.; Hsu, D.F.; Rogers, D.G., Additive variations on a graceful theme: some results on harmonious and other related graphs, Congr. numer., 32, 181-197, (1981) · Zbl 0496.05053
[12] Gallian, J.A., A dynamic survey of graph labeling, Electron. J. combin., 5, #DS6, (2002) · Zbl 0953.05067
[13] Grace, T., On sequential labelings of graphs, J. graph theory, 7, 195-201, (1983) · Zbl 0522.05063
[14] Graham, R.L.; Sloane, N.J.A., On additive bases and harmonious graphs, SIAM J. algebr. discrete methods, 1, 382-404, (1980) · Zbl 0499.05049
[15] Haanpää, H.; Huima, A.; Östergard, P., Sets in \(Z_n\) with distinct sums of pairs, Optimal discrete structures and algorithms, ODSA 2000, Discrete appl. math., 138, 99-106, (2004) · Zbl 1035.05021
[16] Lu, Hui-Chuan; Fu, Hung-Lin, New results on harmonious trees, Util. math., 74, 97-110, (2007) · Zbl 1163.05006
[17] Mollard, M.; Payan, C., Elegant labeling and edge-colorings. A proof of two conjectures of hartman, chang, hsu, Rogers, Ars combin., 36, 97-106, (1993) · Zbl 0793.05104
[18] Singer, J., A theorem in finite projective geometry and some applications to number theory, Trans. amer. math. soc., 43, 377-385, (1938) · JFM 64.0972.04
[19] Z. Skupień, A. Żak, Modular packing functions and rainbow regular labeling (submitted for publication)
[20] Skupień, Z.; Żak, A., Rainbow regular order of graphs, Australas. J. combin., 42, 115-127, (2008) · Zbl 1153.05028
[21] Wood, D.R., On vertex-magic and edge-magic total injections, Australas. J. combin., 26, 49-63, (2002) · Zbl 1015.05084
[22] Wood, D.R., Drawing a graph in a hypercube, Electron. J. combin., 13, 1, R73, (2006) · Zbl 1098.05024
[23] Youssef, M.Z., Two general results on harmonious labelings, Ars combin., 68, 225-230, (2003) · Zbl 1071.05572
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.