ArticleOriginal scientific text

Title

Further results on sequentially additive graphs

Authors 1, 2

Affiliations

  1. Department of mathematical and Computational sciences, National Institute of Technology Karnataka, Surathkal, Srinivasnagar-575025, India
  2. School of Electrical Engineering and Computer Science, University of Newcastle, Callaghan NSW 2308, Australia

Abstract

Given a graph G with p vertices, q edges and a positive integer k, a k-sequentially additive labeling of G is an assignment of distinct numbers k,k+1,k+2,...,k+p+q-1 to the p+q elements of G so that every edge uv of G receives the sum of the numbers assigned to the vertices u and v. A graph which admits such an assignment to its elements is called a k-sequentially additive graph. In this paper, we give an upper bound for k with respect to which the given graph may possibly be k-sequentially additive using the independence number of the graph. Also, we prove a variety of results on k-sequentially additive graphs, including the number of isolated vertices to be added to a complete graph with four or more vertices to be simply sequentially additive and a construction of an infinite family of k-sequentially additive graphs from a given k-sequentially additive graph.

Keywords

simply (k-)sequentially additive labelings (graphs), segregated labelings

Bibliography

  1. B.D. Acharya and S.M. Hegde, Arithmetic graphs, J. Graph Theory 14 (1990) 275-299, doi: 10.1002/jgt.3190140302.
  2. B.D. Acharya and S.M. Hegde, Strongly indexable graphs, Discrete Math. 93 (1991) 123-129, doi: 10.1016/0012-365X(91)90248-Z.
  3. D.W. Bange, A.E. Barkauskas and P.J. Slater, Sequentially additive graphs, Discrete Math. 44 (1983) 235-241, doi: 10.1016/0012-365X(83)90187-5.
  4. G.S. Bloom, Numbered undirected graphs and their uses: A survey of unifying scientific and engineering concepts and its use in developing a theory of non-redundant homometric sets relating to some ambiguities in x-ray diffraction analysis (Ph. D., dissertation, Univ. of Southern California, Loss Angeles, 1975).
  5. Herbert B. Enderton, Elements of Set Theory (Academic Press, 2006).
  6. H. Enomoto, H. Liadi, A.S.T. Nakamigava and G. Ringel, Super edge magic graphs, SUT J. Mathematics 34 (2) (1998) 105-109.
  7. J.A. Gallian, A dynamic survey of graph labeling, Electronic J. Combinatorics DS#6 (2003) 1-148.
  8. S.W. Golomb, How to number a graph, in: Graph Theory and Computing, (ed. R.C. Read) (Academic Press, 1972), 23-37.
  9. F. Harary, Graph Theory (Addison Wesley, Reading, Massachusetts, 1969).
  10. S.M. Hegde, On indexable graphs, J. Combin., Information & System Sciences 17 (1992) 316-331.
  11. S.M. Hegde and Shetty Sudhakar, Strongly k-indexable labelings and super edge magic labelings are equivalent, NITK Research Bulletin 12 (2003) 23-28.
  12. A. Rosa, On certain valuations of the vertices of a graph, in: Theory of Graphs, Proceedings of the International Symposium, Rome (ed. P. Rosentiehl) (Dunod, Paris, 1981) 349-355.
  13. D.B. West, Introduction to Graph Theory (Prentice Hall of India, New Delhi, 2003).
Pages:
251-268
Main language of publication
English
Received
2006-01-04
Accepted
2007-02-05
Published
2007
Exact and natural sciences