| Title:
|
Graceful signed graphs (English) |
| Author:
|
Acharya, Mukti |
| Author:
|
Singh, Tarkeshwar |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
54 |
| Issue:
|
2 |
| Year:
|
2004 |
| Pages:
|
291-302 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
signed graphs |
| Keyword:
|
$(k,d)$-graceful signed graphs |
| MSC:
|
05C22 |
| MSC:
|
05C78 |
| idZBL:
|
Zbl 1080.05529 |
| idMR:
|
MR2059251 |
| . |
| Date available:
|
2009-09-24T11:12:38Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/127888 |
| . |
| Related article:
|
http://dml.cz/handle/10338.dmlcz/127957 |
| . |
| Reference:
|
[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 0516.05055 |
| Reference:
|
[2] B. D. Acharya: On $D$-sequential graphs.J. Math. Phys. Sci. 17 (1983), 21–35. Zbl 0532.05055, MR 0713702 |
| Reference:
|
[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 0761019 |
| Reference:
|
[4] B. D. Acharya and S. M. Hedge: Arithmetic graphs.J. Graph Theory 14 (1989), 275–299. MR 1060857 |
| Reference:
|
[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 1124027 |
| Reference:
|
[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. |
| Reference:
|
[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 0519261 |
| Reference:
|
[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. Zbl 0465.05027, MR 0557885 |
| Reference:
|
[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. MR 0791179, 10.1137/0606051 |
| Reference:
|
[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. Zbl 0714.05050, MR 1100035 |
| Reference:
|
[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 0681879 |
| Reference:
|
[12] J. A. Gallian: A dynamic survey of graph labeling.Electron. J. Combin. 5 (1998), 1–42. Zbl 0953.05067, MR 1668059 |
| Reference:
|
[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. Zbl 0293.05150, MR 0340107 |
| Reference:
|
[14] T. Grace: On sequential labelings of graphs.J. Graph Theory 7 (1983), 195–201. Zbl 0522.05063, MR 0698701, 10.1002/jgt.3190070208 |
| Reference:
|
[15] F. Harrary: Graph Theory.Addison-Wesley Publ. Co., Reading, Massachusettes, 1969. MR 0256911 |
| Reference:
|
[16] A. Kotzig: On certain vertex valuations of finite graphs.Utilitas Math. 4 (1973), 261–290. Zbl 0277.05102, MR 0384616 |
| Reference:
|
[17] M. Maheo and H. Thuillier: On $d$-graceful graphs.LRI Rapport de Recherche No 84, 1981. MR 0666937 |
| Reference:
|
[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. Zbl 0193.53204, MR 0223271 |
| Reference:
|
[19] P. J. Slater: On $k$-sequential and other numbered graphs.Discrete Math. 34 (1981), 185–193. Zbl 0461.05053, MR 0611431, 10.1016/0012-365X(81)90066-2 |
| Reference:
|
[20] P. J. Slater: On $k$-graceful graphs.Congr. Numer. 36 (1982), 53–57. Zbl 0519.05057, MR 0726049 |
| Reference:
|
[21] P. J. Slater: On $k$-graceful countable infintie graphs.Res. Rep. National University of Singapore, 1982. |
| Reference:
|
[22] P. J. Slater: On $k$-graceful locally finite graphs.J. Combin. Theory, Ser. B 35 (1983), 319–322. Zbl 0534.05057, MR 0735199, 10.1016/0095-8956(83)90058-8 |
| . |
