Graceful signed graphs

Mukti Acharya; Tarkeshwar Singh

Czechoslovak Mathematical Journal (2004)

  • Volume: 54, Issue: 2, page 291-302
  • ISSN: 0011-4642

Abstract

top
A ( p , q ) -sigraph S is an ordered pair ( G , s ) where G = ( V , E ) is a ( p , q ) -graph and s is a function which assigns to each edge of G a positive or a negative sign. Let the sets E + and E - consist of m positive and n negative edges of G , respectively, where m + n = q . Given positive integers k and d , S is said to be ( k , d ) -graceful if the vertices of G can be labeled with distinct integers from the set { 0 , 1 , ⋯ , k + ( q - 1 ) d } such that when each edge u v of G is assigned the product of its sign and the absolute difference of the integers assigned to u and v the edges in E + and E - are labeled k , k + d , k + 2 d , ⋯ , k + ( m - 1 ) d and - k , - ( k + d ) , - ( k + 2 d ) , ⋯ , - ( k + ( n - 1 ) d ) , respectively. In this paper, we report results of our preliminary investigation on the above new notion, which indeed generalises the well-known concept of ( k , d ) -graceful graphs due to B. D. Acharya and S. M. Hegde.

How to cite

top

Acharya, Mukti, and Singh, Tarkeshwar. "Graceful signed graphs." Czechoslovak Mathematical Journal 54.2 (2004): 291-302. <http://eudml.org/doc/30860>.

@article{Acharya2004,
abstract = {A $(p,q)$-sigraph $S$ is an ordered pair $(G,s)$ where $G = (V,E)$ is a $(p,q)$-graph and $s$ is a function which assigns to each edge of $G$ a positive or a negative sign. Let the sets $E^+$ and $E^-$ consist of $m$ positive and $n$ negative edges of $G$, respectively, where $m + n = q$. Given positive integers $k$ and $d$, $S$ is said to be $(k,d)$-graceful if the vertices of $G$ can be labeled with distinct integers from the set $\lbrace 0,1,\dots , k + (q-1)d\rbrace $ such that when each edge $uv$ of $G$ is assigned the product of its sign and the absolute difference of the integers assigned to $u$ and $v$ the edges in $E^+$ and $E^-$ are labeled $k, k + d, k + 2d,\dots , k + (m - 1)d$ and $-k, -(k + d), -(k + 2d),\dots ,-(k + (n - 1)d)$, respectively. In this paper, we report results of our preliminary investigation on the above new notion, which indeed generalises the well-known concept of $(k,d)$-graceful graphs due to B. D. Acharya and S. M. Hegde.},
author = {Acharya, Mukti, Singh, Tarkeshwar},
journal = {Czechoslovak Mathematical Journal},
keywords = {signed graphs; $(k,d)$-graceful signed graphs; signed graphs; -graceful signed graphs},
language = {eng},
number = {2},
pages = {291-302},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Graceful signed graphs},
url = {http://eudml.org/doc/30860},
volume = {54},
year = {2004},
}

TY - JOUR
AU - Acharya, Mukti
AU - Singh, Tarkeshwar
TI - Graceful signed graphs
JO - Czechoslovak Mathematical Journal
PY - 2004
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 54
IS - 2
SP - 291
EP - 302
AB - A $(p,q)$-sigraph $S$ is an ordered pair $(G,s)$ where $G = (V,E)$ is a $(p,q)$-graph and $s$ is a function which assigns to each edge of $G$ a positive or a negative sign. Let the sets $E^+$ and $E^-$ consist of $m$ positive and $n$ negative edges of $G$, respectively, where $m + n = q$. Given positive integers $k$ and $d$, $S$ is said to be $(k,d)$-graceful if the vertices of $G$ can be labeled with distinct integers from the set $\lbrace 0,1,\dots , k + (q-1)d\rbrace $ such that when each edge $uv$ of $G$ is assigned the product of its sign and the absolute difference of the integers assigned to $u$ and $v$ the edges in $E^+$ and $E^-$ are labeled $k, k + d, k + 2d,\dots , k + (m - 1)d$ and $-k, -(k + d), -(k + 2d),\dots ,-(k + (n - 1)d)$, respectively. In this paper, we report results of our preliminary investigation on the above new notion, which indeed generalises the well-known concept of $(k,d)$-graceful graphs due to B. D. Acharya and S. M. Hegde.
LA - eng
KW - signed graphs; $(k,d)$-graceful signed graphs; signed graphs; -graceful signed graphs
UR - http://eudml.org/doc/30860
ER -

References

top
  1. Construction of certain infinite families of graceful graphs from a given graceful graph, Defence Sci. J. 32 (1982), 231–236. (1982) Zbl0516.05055
  2. On D -sequential graphs, J. Math. Phys. Sci. 17 (1983), 21–35. (1983) Zbl0532.05055MR0713702
  3. Are all polyominoes arbitrarily graceful? In: Graph Theory, Singapore 1983, Lecture Notes in Mathematics No. 1073, K. M. Koh, H. P. Yap (eds.), Springer-Verlag, Berlin, 1984, pp. 205–211. (1984) MR0761019
  4. Arithmetic graphs, J. Graph Theory 14 (1989), 275–299. (1989) MR1060857
  5. On certain vertex valuations of a graph, Indian J. Pure Appl. Math. 22 (1991), 553–560. (1991) MR1124027
  6. ( k , d ) -graceful packings of a graph, In: Proc. of Group discussion on graph labelling problems, held in K.R.E.C. Surathkal August 16–25, 1999. 
  7. On a combinatorial problem of antennas in radio-astronomy, In: Combinatorics. Proc. of the Colloquium of the Mathematical Society, Janos Bolyayi held in Kezthely, Hungary 1976 vol. 18, North-Holland, Amsterdam, 1978, pp. 135–149. (1978) MR0519261
  8. A chronology of the Ringel-Kotzig conjecture and the continuing quest to call all trees graceful, In: Topics in Graph Theory, F. Harrary (ed.) vol. 328, Ann. New York Acad. Sci., 1979, pp. 32–51. (1979) Zbl0465.05027MR0557885
  9. 10.1137/0606051, SIAM J. Alg. Discrete Math. 6 (1985), 519–536. (1985) MR0791179DOI10.1137/0606051
  10. Status of graceful tree conjecture in 1989, In: Topics in Combinatorics and Graph Theory, R. Bodendiek, R. Henn (eds.), Physica-Verlag, Heidelberg, 1990. (1990) Zbl0714.05050MR1100035
  11. Additive variation of graceful theme: Some results on harmonious and other related graphs, Congr. Numer. 32 (1981), 181–197. (1981) MR0681879
  12. A dynamic survey of graph labeling, Electron. J. Combin. 5 (1998), 1–42. (1998) Zbl0953.05067MR1668059
  13. How to number a graph, In: Graph Theory and Computing, R. C. Read (ed.), Academic Press, New York, 1972, pp. 23–37. (1972) Zbl0293.05150MR0340107
  14. 10.1002/jgt.3190070208, J. Graph Theory 7 (1983), 195–201. (1983) Zbl0522.05063MR0698701DOI10.1002/jgt.3190070208
  15. Graph Theory, Addison-Wesley Publ. Co., Reading, Massachusettes, 1969. (1969) MR0256911
  16. On certain vertex valuations of finite graphs, Utilitas Math. 4 (1973), 261–290. (1973) Zbl0277.05102MR0384616
  17. On d -graceful graphs, LRI Rapport de Recherche No 84, 1981. (1981) MR0666937
  18. On certain valuations of the vertices of a graph, In: Theory of graphs. Proc. Internat. Symp., Rome 1966, P. Rosentiehl (ed.), Dunod, Paris, 1967, pp. 349–355. (1967) Zbl0193.53204MR0223271
  19. 10.1016/0012-365X(81)90066-2, Discrete Math. 34 (1981), 185–193. (1981) Zbl0461.05053MR0611431DOI10.1016/0012-365X(81)90066-2
  20. On k -graceful graphs, Congr. Numer. 36 (1982), 53–57. (1982) Zbl0519.05057MR0726049
  21. On k -graceful countable infintie graphs, Res. Rep. National University of Singapore, 1982. (1982) 
  22. 10.1016/0095-8956(83)90058-8, J. Combin. Theory, Ser. B 35 (1983), 319–322. (1983) Zbl0534.05057MR0735199DOI10.1016/0095-8956(83)90058-8

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.