| Title:
|
Graceful signed graphs: II. The case of signed cycles with connected negative sections (English) |
| Author:
|
Acharya, Mukti |
| Author:
|
Singh, Tarkeshwar |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
55 |
| Issue:
|
1 |
| Year:
|
2005 |
| Pages:
|
25-40 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
graceful signed graphs |
| Keyword:
|
signed cycles |
| MSC:
|
05C22 |
| MSC:
|
05C78 |
| idZBL:
|
Zbl 1081.05097 |
| idMR:
|
MR2121654 |
| . |
| Date available:
|
2009-09-24T11:20:39Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/127957 |
| . |
| Related article:
|
http://dml.cz/handle/10338.dmlcz/127888 |
| . |
| Reference:
|
[1] R. P. Abelson and M. J. Rosenberg: Symbolic psychology: A model of attitudinal cognition.Behav. Sci. 3 (1958), 1–13. 10.1002/bs.3830030102 |
| Reference:
|
[2] B. D. Acharya: Spectral criterion for cycle balance in networks.J. Graph Theory 4 (1981), 1–11. MR 0558448 |
| Reference:
|
[3] B. D. Acharya: Construction of certain infinite families of graceful graphs.Def. Sci. J. 32 (1982), 231–236. Zbl 0516.05055, 10.14429/dsj.32.6301 |
| Reference:
|
[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 |
| Reference:
|
[5] B. D. Acharya and M. Acharya: New algebraic models of social systems.Indian J. Pure Appl. Math. 17 (1986), 150–168. MR 0830552 |
| Reference:
|
[6] B. D. Acharya and S. M. Hegde: Arithmetic graphs.J. Graph Theory 14 (1990), 275–299. MR 1060857, 10.1002/jgt.3190140302 |
| Reference:
|
[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 |
| Reference:
|
[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.). |
| Reference:
|
[9] M. Acharya and T. Singh: Graceful signed graphs.Czechoslovak Math. J. 54(129) (2004), 291–302. MR 2059251, 10.1023/B:CMAJ.0000042369.18091.15 |
| Reference:
|
[10] M. Behzad and G. T. Chartrand: Line coloring of signed graphs.Elem. Math. 24 (1969), 49–52. MR 0244098 |
| Reference:
|
[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. |
| Reference:
|
[12] G. T. Chartrand: Graphs as Mathematical Models.Prindle, Weber and Schmidt, Boston, Masschusetts, 1977. Zbl 0384.05029, MR 0490611 |
| Reference:
|
[13] C. Flament: Application of Graph Theory to Group structures.Prentice Hall, Englewood Cliffs, 1963. MR 0157785 |
| Reference:
|
[14] J. A. Gallian: A dynamic survey of graph labelling.Electronic J. Comb., Dynamic Survey 8 (2001, DS6), 1–55. MR 1668059 |
| Reference:
|
[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 |
| Reference:
|
[16] F. Harary: On the notion of balance of a signed graph.Mich. Math. J. 2 (1954), 143–146. Zbl 0056.42103, MR 0067468 |
| Reference:
|
[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 |
| Reference:
|
[18] F. Harary: Graph Theory.Addison-Wesley Publ. Comp., Reading Massachusetts, 1969. Zbl 0196.27202, MR 0256911 |
| Reference:
|
[19] A. Kotzig: On certain vertex valuations of finite graphs.Utilitas Math. 4 (1973), 261–290. Zbl 0277.05102, MR 0384616 |
| Reference:
|
[20] V. Mishra: Graphs Associated with $[0,1]$ and $[0,+1,-1]$ Matrices.Department of Mathematics, Indian Institute of Technology, Bombay, 1974. |
| Reference:
|
[21] F. S. Roberts: Graph Theory and its Application to Problems of Society.SIAM, Philadelphia, 1978. MR 0508050 |
| Reference:
|
[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 |
| Reference:
|
[23] 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:
|
[24] P. J. Slater: On $k$-graceful graphs.Congr. Numer. 36 (1982), 53–57. Zbl 0519.05057, MR 0726049 |
| Reference:
|
[25] T. Sozanski: Enumeration of weak isomorphism classes of signed graphs.J. Graph Theory 4 (1980), 127–144. Zbl 0434.05059, MR 0570348, 10.1002/jgt.3190040202 |
| Reference:
|
[26] T. Zaslavsky: Signed graphs.Discrete Appl. Math. 4 (1982), 47–74. Zbl 0498.05030, MR 0676405, 10.1016/0166-218X(82)90033-6 |
| Reference:
|
[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 |
| . |
