Further results on sequentially additive graphs

Suresh Manjanath Hegde; Mirka Miller

Discussiones Mathematicae Graph Theory (2007)

  • Volume: 27, Issue: 2, page 251-268
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Suresh Manjanath Hegde, and Mirka Miller. "Further results on sequentially additive graphs." Discussiones Mathematicae Graph Theory 27.2 (2007): 251-268. <http://eudml.org/doc/270324>.

@article{SureshManjanathHegde2007,
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.},
author = {Suresh Manjanath Hegde, Mirka Miller},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {simply (k-)sequentially additive labelings (graphs); segregated labelings; graph labeling; k-sequentially additive labeling},
language = {eng},
number = {2},
pages = {251-268},
title = {Further results on sequentially additive graphs},
url = {http://eudml.org/doc/270324},
volume = {27},
year = {2007},
}

TY - JOUR
AU - Suresh Manjanath Hegde
AU - Mirka Miller
TI - Further results on sequentially additive graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2007
VL - 27
IS - 2
SP - 251
EP - 268
AB - 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.
LA - eng
KW - simply (k-)sequentially additive labelings (graphs); segregated labelings; graph labeling; k-sequentially additive labeling
UR - http://eudml.org/doc/270324
ER -

References

top
  1. [1] B.D. Acharya and S.M. Hegde, Arithmetic graphs, J. Graph Theory 14 (1990) 275-299, doi: 10.1002/jgt.3190140302. Zbl0735.05071
  2. [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. Zbl0741.05057
  3. [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. Zbl0508.05057
  4. [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. [5] Herbert B. Enderton, Elements of Set Theory (Academic Press, 2006). 
  6. [6] H. Enomoto, H. Liadi, A.S.T. Nakamigava and G. Ringel, Super edge magic graphs, SUT J. Mathematics 34 (2) (1998) 105-109. Zbl0918.05090
  7. [7] J.A. Gallian, A dynamic survey of graph labeling, Electronic J. Combinatorics DS#6 (2003) 1-148. 
  8. [8] S.W. Golomb, How to number a graph, in: Graph Theory and Computing, (ed. R.C. Read) (Academic Press, 1972), 23-37. Zbl0293.05150
  9. [9] F. Harary, Graph Theory (Addison Wesley, Reading, Massachusetts, 1969). 
  10. [10] S.M. Hegde, On indexable graphs, J. Combin., Information & System Sciences 17 (1992) 316-331. Zbl1231.05229
  11. [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. [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. [13] D.B. West, Introduction to Graph Theory (Prentice Hall of India, New Delhi, 2003). 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.