Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
graceful signed graphs; signed cycles
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.
Related articles:
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
Search
Partner of
