Geodesic
Graceful signed graphs: II. The case of signed cycles with connected negative sections
Czechoslovak Mathematical Journal, Tome 55 (2005) no. 1, pp. 25-40
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
Classification : 05C22, 05C78
Keywords: graceful signed graphs; signed cycles 
@article{CMJ_2005_55_1_a1,
     author = {Acharya, Mukti and Singh, Tarkeshwar},
     title = {Graceful signed graphs: {II.} {The} case of signed cycles with connected negative sections},
     journal = {Czechoslovak Mathematical Journal},
     pages = {25--40},
     year = {2005},
     volume = {55},
     number = {1},
     mrnumber = {2121654},
     zbl = {1081.05097},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2005_55_1_a1/}
}
TY  - JOUR
AU  - Acharya, Mukti
AU  - Singh, Tarkeshwar
TI  - Graceful signed graphs: II. The case of signed cycles with connected negative sections
JO  - Czechoslovak Mathematical Journal
PY  - 2005
SP  - 25
EP  - 40
VL  - 55
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/CMJ_2005_55_1_a1/
LA  - en
ID  - CMJ_2005_55_1_a1
ER  - 
%0 Journal Article
%A Acharya, Mukti
%A Singh, Tarkeshwar
%T Graceful signed graphs: II. The case of signed cycles with connected negative sections
%J Czechoslovak Mathematical Journal
%D 2005
%P 25-40
%V 55
%N 1
%U http://geodesic.mathdoc.fr/item/CMJ_2005_55_1_a1/
%G en
%F CMJ_2005_55_1_a1
Acharya, Mukti; Singh, Tarkeshwar. Graceful signed graphs: II. The case of signed cycles with connected negative sections. Czechoslovak Mathematical Journal, Tome 55 (2005) no. 1, pp. 25-40. http://geodesic.mathdoc.fr/item/CMJ_2005_55_1_a1/

[1] R. P.  Abelson and M. J.  Rosenberg: Symbolic psychology: A model of attitudinal cognition. Behav. Sci. 3 (1958), 1–13. | DOI

[2] B. D. Acharya: Spectral criterion for cycle balance in networks. J.  Graph Theory 4 (1981), 1–11. | MR

[3] B. D. Acharya: Construction of certain infinite families of graceful graphs. Def. Sci. J. 32 (1982), 231–236. | DOI | Zbl

[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

[5] B. D.  Acharya and M.  Acharya: New algebraic models of social systems. Indian J.  Pure Appl. Math. 17 (1986), 150–168. | MR

[6] B. D.  Acharya and S. M.  Hegde: Arithmetic graphs. J.  Graph Theory 14 (1990), 275–299. | DOI | MR

[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

[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 | MR

[10] M.  Behzad and G. T.  Chartrand: Line coloring of signed graphs. Elem. Math. 24 (1969), 49–52. | MR

[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 | Zbl

[13] C.  Flament: Application of Graph Theory to Group structures. Prentice Hall, Englewood Cliffs, 1963. | MR

[14] J. A.  Gallian: A dynamic survey of graph labelling. Electronic J.  Comb., Dynamic Survey 8 (2001, DS6), 1–55. | MR

[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

[16] F.  Harary: On the notion of balance of a signed graph. Mich. Math.  J. 2 (1954), 143–146. | MR | Zbl

[17] F.  Harary, R. Z.  Norman and D.  Cartwright: Structural Models: An Introduction to the Theory of Directed graphs. Wiley, New York, 1965. | MR

[18] F.  Harary: Graph Theory. Addison-Wesley Publ. Comp., Reading Massachusetts, 1969. | MR | Zbl

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

[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

[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

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

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

[25] T.  Sozanski: Enumeration of weak isomorphism classes of signed graphs. J.  Graph Theory 4 (1980), 127–144. | DOI | MR | Zbl

[26] T.  Zaslavsky: Signed graphs. Discrete Appl. Math. 4 (1982), 47–74. | DOI | MR | Zbl

[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