×

zbMATH — the first resource for mathematics

A-cordial graphs. (English) Zbl 0753.05059
Let \(A\) be an Abelian group. A labelling of a graph \(G=(V,E)\) is any mapping \(f:V\to A\). Every such mapping induces a mapping \(f_ E:E\to A\) by \(f_ E(xy):=f(x)+f(y)\) for \(xy\in E\). A graph is called \(A\)-cordial if there is some labelling \(f\) such that \(\| f^{-1}(a)| -| f^{-1}(b)\|\leq 1\) and \(\| f_ E^{-1}(a)| -| f_ E^{-1}(b)\|\leq 1\) for all \(a,b\in A\). This is a generalization of the notions of harmonious
(i.e. \({\mathcal Z}_{| E|}\)-cordial) or cordial (i.e. \({\mathcal Z}_ 2\)-cordial) graphs.
It has been conjectured by R. L. Graham and N. J. A. Sloane [SIAM J. Algebraic Discrete Methods 1, 382-404 (1980; Zbl 0499.05049)] that every tree \(T=(V,E)\) is \({\mathcal Z}_{| E|}\)-cordial. In this paper it is shown that every tree is \({\mathcal Z}_ 3\)-, \({\mathcal Z}_ 4\)-, and \({\mathcal Z}_ 5\)-cordial. Several more results and conjectures are given.

MSC:
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C05 Trees
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Cahit, I., Cordial graphs: a weaker version of graceful and harmonious graphs, Ars. combin., 23, 201-207, (1987) · Zbl 0616.05056
[2] Chang, G.; Hsu, D.; Rogers, D., Additive variations on a graceful theme, Utilitas math., 32, 181-197, (1987)
[3] S.M. Lee and A. Liu, On cordial graphs, to appear. · Zbl 0755.05086
[4] Grace, T., On sequential labelings of graphs, J. graph theory, 7, 195-201, (1987) · Zbl 0522.05063
[5] Graham, R.L.; Sloane, N.J.A., On additive bases and harmonious graphs, SIAM J. algebraic discrete methods, 1, 382-404, (1980) · Zbl 0499.05049
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.