Graceful signed graphs: II. The case of signed cycles with connected negative sections

Mukti Acharya; Tarkeshwar Singh

Czechoslovak Mathematical Journal (2005)

  • Volume: 55, Issue: 1, page 25-40
  • ISSN: 0011-4642

Abstract

top
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 , ⋯ , q = m + n such that when to each edge u v of S one assigns the absolute difference | f ( u ) - f ( v ) | the set of integers received by the positive edges of S is { 1 , 2 , ⋯ , m } and the set of integers received by the negative edges of S is { 1 , 2 , ⋯ , n } . Considering the conjecture therein that all signed cycles Z k , of admissible length k ≥ 3 and signed structures, are graceful, we establish in this paper its truth for all possible signed cycles of lengths 0 , 2 or 3 ( m o d 4 ) in which the set of negative edges forms a connected subsigraph.

How to cite

top

Acharya, Mukti, and Singh, Tarkeshwar. "Graceful signed graphs: II. The case of signed cycles with connected negative sections." Czechoslovak Mathematical Journal 55.1 (2005): 25-40. <http://eudml.org/doc/30925>.

@article{Acharya2005,
abstract = {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.},
author = {Acharya, Mukti, Singh, Tarkeshwar},
journal = {Czechoslovak Mathematical Journal},
keywords = {graceful signed graphs; signed cycles; graceful signed graphs; signed cycles},
language = {eng},
number = {1},
pages = {25-40},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Graceful signed graphs: II. The case of signed cycles with connected negative sections},
url = {http://eudml.org/doc/30925},
volume = {55},
year = {2005},
}

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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 55
IS - 1
SP - 25
EP - 40
AB - 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.
LA - eng
KW - graceful signed graphs; signed cycles; graceful signed graphs; signed cycles
UR - http://eudml.org/doc/30925
ER -

References

top
  1. 10.1002/bs.3830030102, Behav. Sci. 3 (1958), 1–13. (1958) DOI10.1002/bs.3830030102
  2. Spectral criterion for cycle balance in networks, J.  Graph Theory 4 (1981), 1–11. (1981) MR0558448
  3. 10.14429/dsj.32.6301, Def. Sci. J. 32 (1982), 231–236. (1982) Zbl0516.05055DOI10.14429/dsj.32.6301
  4. 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. (1984) MR0761019
  5. New algebraic models of social systems, Indian J.  Pure Appl. Math. 17 (1986), 150–168. (1986) MR0830552
  6. 10.1002/jgt.3190140302, J.  Graph Theory 14 (1990), 275–299. (1990) MR1060857DOI10.1002/jgt.3190140302
  7. On certain vertex valuations of a graph, Indian J.  Pure Appl. Math. 22 (1991), 553–560. (1991) MR1124027
  8. ( 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. 10.1023/B:CMAJ.0000042369.18091.15, Czechoslovak Math. J. 54(129) (2004), 291–302. (2004) MR2059251DOI10.1023/B:CMAJ.0000042369.18091.15
  10. Line coloring of signed graphs, Elem. Math. 24 (1969), 49–52. (1969) MR0244098
  11. 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. (1978) 
  12. Graphs as Mathematical Models, Prindle, Weber and Schmidt, Boston, Masschusetts, 1977. (1977) Zbl0384.05029MR0490611
  13. Application of Graph Theory to Group structures, Prentice Hall, Englewood Cliffs, 1963. (1963) MR0157785
  14. A dynamic survey of graph labelling, Electronic J.  Comb., Dynamic Survey 8 (2001, DS6), 1–55. (2001, DS6) MR1668059
  15. How to number a graph? In: Graph Theory and Computing, R. C. Read (ed.), Academic Press, New York, 1972, pp. 23–37. (1972) MR0340107
  16. On the notion of balance of a signed graph, Mich. Math.  J. 2 (1954), 143–146. (1954) Zbl0056.42103MR0067468
  17. Structural Models: An Introduction to the Theory of Directed graphs, Wiley, New York, 1965. (1965) MR0184874
  18. Graph Theory, Addison-Wesley Publ. Comp., Reading Massachusetts, 1969. (1969) Zbl0196.27202MR0256911
  19. On certain vertex valuations of finite graphs, Utilitas Math. 4 (1973), 261–290. (1973) Zbl0277.05102MR0384616
  20. Graphs Associated with [ 0 , 1 ] and [ 0 , + 1 , - 1 ] Matrices, Department of Mathematics, Indian Institute of Technology, Bombay, 1974. (1974) 
  21. Graph Theory and its Application to Problems of Society, SIAM, Philadelphia, 1978. (1978) MR0508050
  22. 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. (1968) MR0223271
  23. 10.1016/0012-365X(81)90066-2, Discrete Math. 34 (1981), 185–193. (1981) Zbl0461.05053MR0611431DOI10.1016/0012-365X(81)90066-2
  24. On k -graceful graphs, Congr. Numer. 36 (1982), 53–57. (1982) Zbl0519.05057MR0726049
  25. 10.1002/jgt.3190040202, J.  Graph Theory 4 (1980), 127–144. (1980) Zbl0434.05059MR0570348DOI10.1002/jgt.3190040202
  26. 10.1016/0166-218X(82)90033-6, Discrete Appl. Math. 4 (1982), 47–74. (1982) Zbl0498.05030MR0676405DOI10.1016/0166-218X(82)90033-6
  27. A mathematical bibliography of signed and gain graphs and allied areas (manuscript prepared with Marge Pratt), Electronic J. Combinatorics 8 (1998). (1998) MR1744869

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.