Strongly multiplicative graphs

L.W. Beineke; S.M. Hegde

Discussiones Mathematicae Graph Theory (2001)

  • Volume: 21, Issue: 1, page 63-75
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

L.W. Beineke, and S.M. Hegde. "Strongly multiplicative graphs." Discussiones Mathematicae Graph Theory 21.1 (2001): 63-75. <http://eudml.org/doc/270685>.

@article{L2001,
abstract = {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.},
author = {L.W. Beineke, S.M. Hegde},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph labelling; multiplicative labelling},
language = {eng},
number = {1},
pages = {63-75},
title = {Strongly multiplicative graphs},
url = {http://eudml.org/doc/270685},
volume = {21},
year = {2001},
}

TY - JOUR
AU - L.W. Beineke
AU - S.M. Hegde
TI - Strongly multiplicative graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2001
VL - 21
IS - 1
SP - 63
EP - 75
AB - 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.
LA - eng
KW - graph labelling; multiplicative labelling
UR - http://eudml.org/doc/270685
ER -

References

top
  1. [1] B.D. Acharya and S.M. Hegde, On certain vertex valuations of a graph, Indian J. Pure Appl. Math. 22 (1991) 553-560. Zbl0759.05086
  2. [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. Zbl0465.05027
  3. [3] F.R.K. Chung, Labelings of graphs, Selected Topics in Graph Theory 3 (Academic Press, 1988) 151-168. 
  4. [4] P. Erdős, An asymptotic inequality in the theory of numbers, Vestnik Leningrad. Univ. 15 (1960) 41-49. Zbl0104.26804
  5. [5] J.A. Gallian, A dynamic survey of graph labeling, Electronic J. Comb. 5 (1998) #DS6. Zbl0953.05067
  6. [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. Zbl0499.05049
  7. [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. 

NotesEmbed ?

top

You must be logged in to post comments.