Article
Full entry |
PDF
(0.4 MB)
Feedback
PDF
(0.4 MB)
Feedback
Keywords:
signed graphs; $(k,d)$-graceful signed graphs
signed graphs; $(k,d)$-graceful signed graphs
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.
Related articles:
References:
[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
[2] B. D. Acharya: On $D$-sequential graphs. J. Math. Phys. Sci. 17 (1983), 21–35. MR 0713702 | Zbl 0532.05055
[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
[4] B. D. Acharya and S. M. Hedge: Arithmetic graphs. J. Graph Theory 14 (1989), 275–299. MR 1060857
[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
[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 0519261
[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 0557885 | Zbl 0465.05027
[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 10.1137/0606051 | MR 0791179
[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 1100035 | Zbl 0714.05050
[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
[12] J. A. Gallian: A dynamic survey of graph labeling. Electron. J. Combin. 5 (1998), 1–42. MR 1668059 | Zbl 0953.05067
[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 0340107 | Zbl 0293.05150
[14] T. Grace: On sequential labelings of graphs. J. Graph Theory 7 (1983), 195–201. DOI 10.1002/jgt.3190070208 | MR 0698701 | Zbl 0522.05063
[15] F. Harrary: Graph Theory. Addison-Wesley Publ. Co., Reading, Massachusettes, 1969. MR 0256911
[16] A. Kotzig: On certain vertex valuations of finite graphs. Utilitas Math. 4 (1973), 261–290. MR 0384616 | Zbl 0277.05102
[17] M. Maheo and H. Thuillier: On $d$-graceful graphs. LRI Rapport de Recherche No 84, 1981. MR 0666937
[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 0223271 | Zbl 0193.53204
[19] P. J. Slater: On $k$-sequential and other numbered graphs. Discrete Math. 34 (1981), 185–193. DOI 10.1016/0012-365X(81)90066-2 | MR 0611431 | Zbl 0461.05053
[20] P. J. Slater: On $k$-graceful graphs. Congr. Numer. 36 (1982), 53–57. MR 0726049 | Zbl 0519.05057
[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 10.1016/0095-8956(83)90058-8 | MR 0735199 | Zbl 0534.05057
Search
Partner of
