# Article

Full entry | PDF   (0.3 MB)
Keywords:
graceful signed graphs; signed cycles
Summary:
In our earlier paper [9], generalizing the well known notion of graceful graphs, a $(p,m,n)$-signed graph $S$ of order $p$, with $m$ positive edges and $n$ negative edges, is called graceful if there exists an injective function $f$ that assigns to its $p$ vertices integers $0,1,\dots ,q = m+n$ such that when to each edge $uv$ of $S$ one assigns the absolute difference $|f(u) - f(v)|$ the set of integers received by the positive edges of $S$ is $\lbrace 1,2,\dots ,m\rbrace$ and the set of integers received by the negative edges of $S$ is $\lbrace 1,2,\dots ,n\rbrace$. Considering the conjecture therein that all signed cycles $Z_k$, of admissible length $k \ge 3$ and signed structures, are graceful, we establish in this paper its truth for all possible signed cycles of lengths $0,2$ or $3\hspace{4.44443pt}(\@mod \; 4)$ in which the set of negative edges forms a connected subsigraph.
References:
[1] R. P.  Abelson and M. J.  Rosenberg: Symbolic psychology: A model of attitudinal cognition. Behav. Sci. 3 (1958), 1–13. DOI 10.1002/bs.3830030102
[2] B. D. Acharya: Spectral criterion for cycle balance in networks. J.  Graph Theory 4 (1981), 1–11. MR 0558448
[3] B. D. Acharya: Construction of certain infinite families of graceful graphs. Def. Sci. J. 32 (1982), 231–236. DOI 10.14429/dsj.32.6301 | Zbl 0516.05055
[4] B. D.  Acharya: Are all polyominoes arbitrarily graceful? In: Graph Theory Singapore 1983. Lecture note in Mathematics, No. 1073, K. M.  Koh, Y. P. Yap (eds.), Springer-Verlag, Berlin, 1984, pp. 205–211. MR 0761019
[5] B. D.  Acharya and M.  Acharya: New algebraic models of social systems. Indian J.  Pure Appl. Math. 17 (1986), 150–168. MR 0830552
[6] B. D.  Acharya and S. M.  Hegde: Arithmetic graphs. J.  Graph Theory 14 (1990), 275–299. DOI 10.1002/jgt.3190140302 | MR 1060857
[7] B. D.  Acharya and S. M.  Hegde: On certain vertex valuations of a graph. Indian J.  Pure Appl. Math. 22 (1991), 553–560. MR 1124027
[8] B. D.  Acharya: $(k,d)$-graceful packings of a graph. In: Proc. of Group Discussion on graph labelling problems, Karnataka Regional Engineering College, Surathkal, August 16–25, 1999, B. D.  Acharya, S M.  Hegde (eds.).
[9] M.  Acharya and T.  Singh: Graceful signed graphs. Czechoslovak Math. J. 54(129) (2004), 291–302. DOI 10.1023/B:CMAJ.0000042369.18091.15 | MR 2059251
[10] M.  Behzad and G. T.  Chartrand: Line coloring of signed graphs. Elem. Math. 24 (1969), 49–52. MR 0244098
[11] J. C.  Bermod, A.  Kotzig and J. Trugeon: On a combinatorial problem of antennas in radio astronomy. In: Combinatorics; Proc. of the Colloquium of the Janos Bolyayi Mathematical Society (Keszthly; Hungary: 1976), Vol.  18, North-Holland, Amsterdam, 1978, pp. 135–149.
[12] G. T.  Chartrand: Graphs as Mathematical Models. Prindle, Weber and Schmidt, Boston, Masschusetts, 1977. MR 0490611 | Zbl 0384.05029
[13] C.  Flament: Application of Graph Theory to Group structures. Prentice Hall, Englewood Cliffs, 1963. MR 0157785
[14] J. A.  Gallian: A dynamic survey of graph labelling. Electronic J.  Comb., Dynamic Survey 8 (2001, DS6), 1–55. MR 1668059
[15] 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
[16] F.  Harary: On the notion of balance of a signed graph. Mich. Math.  J. 2 (1954), 143–146. MR 0067468 | Zbl 0056.42103
[17] F.  Harary, R. Z.  Norman and D.  Cartwright: Structural Models: An Introduction to the Theory of Directed graphs. Wiley, New York, 1965. MR 0184874
[18] F.  Harary: Graph Theory. Addison-Wesley Publ. Comp., Reading Massachusetts, 1969. MR 0256911 | Zbl 0196.27202
[19] A.  Kotzig: On certain vertex valuations of finite graphs. Utilitas Math. 4 (1973), 261–290. MR 0384616 | Zbl 0277.05102
[20] V.  Mishra: Graphs Associated with $[0,1]$ and $[0,+1,-1]$ Matrices. Department of Mathematics, Indian Institute of Technology, Bombay, 1974.
[21] F. S.  Roberts: Graph Theory and its Application to Problems of Society. SIAM, Philadelphia, 1978. MR 0508050
[22] 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, 1968, pp. 349–355. MR 0223271
[23] 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
[24] P. J.  Slater: On $k$-graceful graphs. Congr. Numer. 36 (1982), 53–57. MR 0726049 | Zbl 0519.05057
[25] T.  Sozanski: Enumeration of weak isomorphism classes of signed graphs. J.  Graph Theory 4 (1980), 127–144. DOI 10.1002/jgt.3190040202 | MR 0570348 | Zbl 0434.05059
[26] T.  Zaslavsky: Signed graphs. Discrete Appl. Math. 4 (1982), 47–74. DOI 10.1016/0166-218X(82)90033-6 | MR 0676405 | Zbl 0498.05030
[27] T.  Zaslavsky: A mathematical bibliography of signed and gain graphs and allied areas (manuscript prepared with Marge Pratt). Electronic J. Combinatorics 8 (1998). MR 1744869

Partner of