# Graceful signed graphs

Mukti Acharya; Tarkeshwar Singh

Czechoslovak Mathematical Journal (2004)

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

## Access Full Article

top## Abstract

top## How to cite

topAcharya, 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- Construction of certain infinite families of graceful graphs from a given graceful graph, Defence Sci. J. 32 (1982), 231–236. (1982) Zbl0516.05055
- On $D$-sequential graphs, J. Math. Phys. Sci. 17 (1983), 21–35. (1983) Zbl0532.05055MR0713702
- 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
- Arithmetic graphs, J. Graph Theory 14 (1989), 275–299. (1989) MR1060857
- On certain vertex valuations of a graph, Indian J. Pure Appl. Math. 22 (1991), 553–560. (1991) MR1124027
- $(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.
- 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
- 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
- 10.1137/0606051, SIAM J. Alg. Discrete Math. 6 (1985), 519–536. (1985) MR0791179DOI10.1137/0606051
- 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
- Additive variation of graceful theme: Some results on harmonious and other related graphs, Congr. Numer. 32 (1981), 181–197. (1981) MR0681879
- A dynamic survey of graph labeling, Electron. J. Combin. 5 (1998), 1–42. (1998) Zbl0953.05067MR1668059
- 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
- 10.1002/jgt.3190070208, J. Graph Theory 7 (1983), 195–201. (1983) Zbl0522.05063MR0698701DOI10.1002/jgt.3190070208
- Graph Theory, Addison-Wesley Publ. Co., Reading, Massachusettes, 1969. (1969) MR0256911
- On certain vertex valuations of finite graphs, Utilitas Math. 4 (1973), 261–290. (1973) Zbl0277.05102MR0384616
- On $d$-graceful graphs, LRI Rapport de Recherche No 84, 1981. (1981) MR0666937
- 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
- 10.1016/0012-365X(81)90066-2, Discrete Math. 34 (1981), 185–193. (1981) Zbl0461.05053MR0611431DOI10.1016/0012-365X(81)90066-2
- On $k$-graceful graphs, Congr. Numer. 36 (1982), 53–57. (1982) Zbl0519.05057MR0726049
- On $k$-graceful countable infintie graphs, Res. Rep. National University of Singapore, 1982. (1982)
- 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

## Citations in EuDML Documents

top## NotesEmbed ?

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