Geodesic
Graceful signed graphs
Czechoslovak Mathematical Journal, Tome 54 (2004) no. 2, pp. 291-302
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
Classification : 05C22, 05C78
Keywords: signed graphs; $(k, d)$-graceful signed graphs 
@article{CMJ_2004_54_2_a2,
     author = {Acharya, Mukti and Singh, Tarkeshwar},
     title = {Graceful signed graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {291--302},
     year = {2004},
     volume = {54},
     number = {2},
     mrnumber = {2059251},
     zbl = {1080.05529},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2004_54_2_a2/}
}
TY  - JOUR
AU  - Acharya, Mukti
AU  - Singh, Tarkeshwar
TI  - Graceful signed graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2004
SP  - 291
EP  - 302
VL  - 54
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/CMJ_2004_54_2_a2/
LA  - en
ID  - CMJ_2004_54_2_a2
ER  - 
%0 Journal Article
%A Acharya, Mukti
%A Singh, Tarkeshwar
%T Graceful signed graphs
%J Czechoslovak Mathematical Journal
%D 2004
%P 291-302
%V 54
%N 2
%U http://geodesic.mathdoc.fr/item/CMJ_2004_54_2_a2/
%G en
%F CMJ_2004_54_2_a2
Acharya, Mukti; Singh, Tarkeshwar. Graceful signed graphs. Czechoslovak Mathematical Journal, Tome 54 (2004) no. 2, pp. 291-302. http://geodesic.mathdoc.fr/item/CMJ_2004_54_2_a2/

[1] B. D. Acharya: Construction of certain infinite families of graceful graphs from a given graceful graph. Defence Sci. J. 32 (1982), 231–236. | Zbl

[2] B. D. Acharya: On $D$-sequential graphs. J. Math. Phys. Sci. 17 (1983), 21–35. | MR | Zbl

[3] B. D. Acharya: 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. | MR

[4] B. D. Acharya and S. M. Hedge: Arithmetic graphs. J. Graph Theory 14 (1989), 275–299. | MR

[5] B. D. Acharya and S. M. Hedge: On certain vertex valuations of a graph. Indian J. Pure Appl. Math. 22 (1991), 553–560. | MR

[6] B. D. Acharya: $(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] J. C. Bermond, A. Kotzig and J. Turgeon: 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. | MR

[8] G. S. Bloom: 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. | MR | Zbl

[9] G. S. Bloom and D. F. Hsu: On graceful directed graphs (Tech. Rep. Univ. of California). SIAM J. Alg. Discrete Math. 6 (1985), 519–536. | DOI | MR

[10] I. Cahit: Status of graceful tree conjecture in 1989. In: Topics in Combinatorics and Graph Theory, R. Bodendiek, R. Henn (eds.), Physica-Verlag, Heidelberg, 1990. | MR | Zbl

[11] G. J. Chang, D. F. Hsu and D. G. Rogers: Additive variation of graceful theme: Some results on harmonious and other related graphs. Congr. Numer. 32 (1981), 181–197. | MR

[12] J. A. Gallian: A dynamic survey of graph labeling. Electron. J. Combin. 5 (1998), 1–42. | MR | Zbl

[13] S. W. Golomb: How to number a graph. In: Graph Theory and Computing, R. C. Read (ed.), Academic Press, New York, 1972, pp. 23–37. | MR | Zbl

[14] T. Grace: On sequential labelings of graphs. J. Graph Theory 7 (1983), 195–201. | DOI | MR | Zbl

[15] F. Harrary: Graph Theory. Addison-Wesley Publ. Co., Reading, Massachusettes, 1969. | MR

[16] A. Kotzig: On certain vertex valuations of finite graphs. Utilitas Math. 4 (1973), 261–290. | MR | Zbl

[17] M. Maheo and H. Thuillier: On $d$-graceful graphs. LRI Rapport de Recherche No 84, 1981. | MR

[18] A. Rosa: 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. | MR | Zbl

[19] P. J. Slater: On $k$-sequential and other numbered graphs. Discrete Math. 34 (1981), 185–193. | DOI | MR | Zbl

[20] P. J. Slater: On $k$-graceful graphs. Congr. Numer. 36 (1982), 53–57. | MR | Zbl

[21] P. J. Slater: On $k$-graceful countable infintie graphs. Res. Rep. National University of Singapore, 1982.

[22] P. J. Slater: On $k$-graceful locally finite graphs. J. Combin. Theory, Ser. B 35 (1983), 319–322. | DOI | MR | Zbl