A characterization of canonically consistent total signed graphs

Deepa Sinha and Pravin Garg
Notes on Number Theory and Discrete Mathematics, ISSN 1310–5132
Volume 19, 2013, Number 3, Pages 70–77
Full paper (PDF, 164 Kb)

Details

Authors and affiliations

Deepa Sinha
Department of Mathematics, South Asian University, Akbar Bhawan
Chanakyapuri, New Delhi–110021, India

Pravin Garg
Centre for Mathematical Sciences, Banasthali University
Banasthali–304022, Rajasthan, India

Abstract

The canonical marking on a signed graph (or sigraph, in short) S is defined as: for each vertex v ∈ V (S), μ_σ(v) = Π_{ej ∈ Ev}, where E_v is the set of edges e_j incident at v in S. If S is canonically marked, then a cycle Z in S is said to be canonically consistent (C-consistent) if it contains an even number of negative vertices and the given sigraph S is C-consistent if every cycle in it is C-consistent. The total sigraph T(S) of a sigraph S = (V, E, σ) has T(S^e) as its underlying graph and for any edge uv of T(S^e),

In this paper, we establish a characterization of canonically consistent total sigraphs.

Keywords

• Sigraph
• Canonical marking
• Consistent sigraph
• Total sigraph

AMS Classification

• 05C22
• 05C75

References

1. Acharya, B. D. A characterization of consistent marked graphs, Nat. Acad. Sci. Lett., Vol. 6, 1983, No. 12, 431–440.
2. Acharya, B. D. Some further properties of consistent marked graphs, Indian J. Pure Appl. Math., Vol. 15, 1984, No. 8, 837–842.
3. Acharya, B. D. Signed intersection graphs. In preparation.
4. Acharya, B. D., M. Acharya, D. Sinha. Characterization of a signed graph whose signed line graph is s-consistent, Bull. Malays. Math. Sci. Soc., Vol. 32, 2009, No. 3, 335–341.
5. Akiyama, J., T. Hamada. The decompositions of line graphs, middle graphs and total graphs of complete graphs into forests, Discrete Math., Vol. 26, 1979, No. 3, 203–208.
6. Behzad, M., G. Chartrand. Total graphs and traversability, Proc. Edinb. Math. Soc., Vol. 15, 1966, No. 2, 117–120.
7. Behzad, M. A criterion for the planarity of the total graph of a graph, Proc. Cambridge Philos. Soc., Vol. 63, 1967, 679–681.
8. Behzad, M., H. Radjavi. The total group of a graph, Proc. Amer. Math. Soc., Vol. 19, 1968, 158–163.
9. Behzad, M. The connectivity of total graphs, Australian Math. Bull., Vol. 1, 1969, 175–181.
10. Behzad, M., G. T. Chartrand. Line coloring of signed graphs, Elem. Math., Vol. 24, 1969, No. 3, 49–52.
11. Behzad, M., H. Radjavi. Structure of regular total graphs, J. Lond. Math. Soc., Vol. 44, 1969, 433–436.
12. Behzad, M. A characterization of total graphs, Proc. Amer. Math. Soc., Vol. 26, 1970, No. 3, 383–389.
13. Beineke, L. W., F. Harary. Consistency in marked graphs, J. Math. Psych., Vol. 18, 1978, No. 3, 260–269.
14. Beineke, L.W., F. Harary. Consistent graphs with signed points, Riv. Math. per. Sci. Econom. Sociol., Vol. 1, 1978, 81–88.
15. Boza, L., M. T. D´avila, A. M´arquez, R. Moyano, Miscellaneous properties of embeddings of line, total and middle graphs, Discrete Math., Vol. 233, 2001, No. 1–3, 37–54.
16. Chartrand, G. T. Graphs as Mathematical Models, Prindle, Weber and Schmidt, Inc., Boston, Massachusetts, 1977.
17. Cvetkovic, D. M., S. K. Simic, Graph equations for line graphs and total graphs, Discrete Math., Vol. 13, 1975, 315–320.
18. Gavril, F. A recognition algorithm for the total graphs, Networks, Vol. 8, 1978, No. 2, 121– 133.
19. Harary, F. On the notion of balance of a signed graph, Mich. Math. J., Vol. 2, 1953, 143–146.
20. Harary, F. Graph Theory, Addison-Wesley Publ. Comp., Reading, Massachusetts, 1969.
21. Hoede, C. A characterization of consistent marked graphs, J. Graph Theory, Vol. 16, 1992, No. 1, 17–23.
22. Rangarajan, R., M. S. Subramanya, P. S. K. Reddy, Neighborhood signed graphs, Southeast Asian Bull. Math., Vol. 36, 2012, No. 3, 389–397.
23. Rao, S. B. Characterizations of harmonious marked graphs and consistent nets, J. Comb. Inf. & Syst. Sci., Vol. 9, 1984, No. 2, 97–112.
24. Sampathkumar, E. Point-signed and line-signed graphs, Karnatak Univ. Graph Theory Res. Rep., No. 1, 1973 [also see Abstract No. 1 in Graph Theory Newsletter, Vol. 2, 1972, No. 2; National Academy Science Letters, Vol. 7, 1984, 91–93.
25. Sampathkumar, E., P. S. K. Reddy, M. S. Subramanya. The line n-sigraph of a symmetric n-sigraph, Southeast Asian Bull. Math., Vol. 34, 2010, No. 5, 953–958.
26. Sastry, D. V. S., B. S. P. Raju. Graph equations for line graphs, total graphs, middle graphs and quasi-total graphs, Discrete Math., Vol. 48, 1984, No. 1, 113–119.
27. Sinha, D. New frontiers in the theory of signed graph, Ph.D. Thesis, University of Delhi (Faculty of Technology), 2005.
28. Sinha, D., P. Garg, Canonical consistency of signed line structures, Graph Theory Notes N. Y., Vol. 59, 2010, 22–27.
29. Sinha, D., P. Garg, Balance and consistency of total signed graphs, Indian J. Math., Vol. 53, 2011, No. 1, 71–81.
30. Sinha, D., P. Garg, Characterization of total signed graph and semi-total signed graphs, Int. J. Contemp. Math. Sciences, Vol. 6, 2011, No. 5, 221–228.
31. Sinha, D., P. Garg, On the regularity of some signed graph structures, AKCE Int. J. Graphs Comb., Vol. 8, 2011, No. 1, 63–74.
32. Sinha, D., P. Garg, Some results on semi-total signed graphs, Discuss. Math. Graph Theory, Vol. 31, 2011, No. 4, 625–638.
33. West, D. B. Introduction to Graph Theory, Prentice-Hall of India Pvt. Ltd., 1996.
34. Zaslavsky, T. A mathematical bibliography of signed and gain graphs and allied areas, VIII Edition, Electron. J. Combin., #DS8(1998).
35. Zaslavsky, T. Glossary of signed and gain graphs and allied areas, II Edition, Electron. J. Combin., #DS9(1998).
36. Zaslavsky, T. The canonical vertex signature and the cosets of the complete binary cycle space, submitted.