Discussiones Mathematicae Graph Theory 27(2) (2007)
Suresh Manjanath Hegde
Department of mathematical and Computational sciences
School of Electrical Engineering and Computer Science
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.
2000 Mathematics Subject Classification: 05C78.
|||B.D. Acharya and S.M. Hegde, Arithmetic graphs, J. Graph Theory 14 (1990) 275-299, doi: 10.1002/jgt.3190140302.|
|||B.D. Acharya and S.M. Hegde, Strongly indexable graphs, Discrete Math. 93 (1991) 123-129, doi: 10.1016/0012-365X(91)90248-Z.|
|||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.|
|||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).|
|||Herbert B. Enderton, Elements of Set Theory (Academic Press, 2006).|
|||H. Enomoto, H. Liadi, A.S.T. Nakamigava and G. Ringel, Super edge magic graphs, SUT J. Mathematics 34 (2) (1998) 105-109.|
|||J.A. Gallian, A dynamic survey of graph labeling, Electronic J. Combinatorics DS#6 (2003) 1-148.|
|||S.W. Golomb, How to number a graph, in: Graph Theory and Computing, (ed. R.C. Read) (Academic Press, 1972), 23-37.|
|||F. Harary, Graph Theory (Addison Wesley, Reading, Massachusetts, 1969).|
|||S.M. Hegde, On indexable graphs, J. Combin., Information & System Sciences 17 (1992) 316-331.|
|||S.M. Hegde and Shetty Sudhakar, Strongly k-indexable labelings and super edge magic labelings are equivalent, NITK Research Bulletin 12 (2003) 23-28.|
|||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.|
|||D.B. West, Introduction to Graph Theory (Prentice Hall of India, New Delhi, 2003).|
Received 4 January 2006
Revised 5 February 2007
Accepted 5 February 2007