A graph with p vertices is said to be strongly multiplicative if its vertices can be labelled 1,2,...,p so that the values on the edges, obtained as the product of the labels of their end vertices, are all distinct. In this paper, we study structural properties of strongly multiplicative graphs. We show that all graphs in some classes, including all trees, are strongly multiplicative, and consider the question of the maximum number of edges in a strongly multiplicative graph of a given order.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1133,
author = {L.W. Beineke and S.M. Hegde},
title = {Strongly multiplicative graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {21},
year = {2001},
pages = {63-75},
zbl = {0989.05101},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1133}
}
L.W. Beineke; S.M. Hegde. Strongly multiplicative graphs. Discussiones Mathematicae Graph Theory, Tome 21 (2001) pp. 63-75. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1133/
[000] [1] B.D. Acharya and S.M. Hegde, On certain vertex valuations of a graph, Indian J. Pure Appl. Math. 22 (1991) 553-560. | Zbl 0759.05086
[001] [2] G.S. Bloom, A chronology of the Ringel-Kotzig conjecture and the continuing quest to call all trees graceful, Ann. N.Y. Acad. Sci. 326 (1979) 32-51, doi: 10.1111/j.1749-6632.1979.tb17766.x. | Zbl 0465.05027
[002] [3] F.R.K. Chung, Labelings of graphs, Selected Topics in Graph Theory 3 (Academic Press, 1988) 151-168.
[003] [4] P. Erdős, An asymptotic inequality in the theory of numbers, Vestnik Leningrad. Univ. 15 (1960) 41-49. | Zbl 0104.26804
[004] [5] J.A. Gallian, A dynamic survey of graph labeling, Electronic J. Comb. 5 (1998) #DS6. | Zbl 0953.05067
[005] [6] R.L. Graham and N.J.A. Sloane, On additive bases and harmonious graphs, SIAM J. Algebraic Discrete Methods 1 (1980) 382-404, doi: 10.1137/0601045. | Zbl 0499.05049
[006] [7] A. Rosa, On certain valuations of the vertices of a graph, in: Theory of Graphs, Internat. Symposium, Rome, July 1966 (Gordon and Breach, Dunod, 1967) 349-355.