Embedding of signed regular graphs

Deepa Sinha and Anita Kumari Rao
Notes on Number Theory and Discrete Mathematics
Print ISSN 1310–5132, Online ISSN 2367–8275
Volume 24, 2018, Number 3, Pages 131–141
DOI: 10.7546/nntdm.2018.24.3.131-141
Full paper (PDF, 211 Kb)

Details

Authors and affiliations

Deepa Sinha
Department of Mathematics, South Asian University
New Delhi-110021, India

Anita Kumari Rao
Department of Mathematics, South Asian University
New Delhi-110021, India

Abstract

A signed graph is a graph whose edges carry the weight ‘+’ or ‘−’. A signed graph 𝑆 is called signed-regular if 𝑑⁻(𝑣) is same for all 𝑣 ∈ 𝑉 and 𝑑⁺(𝑣) is same for all 𝑣 ∈ 𝑉. The problems of embedding (𝑖, 𝑗)-signed-regular graphs in (𝑖, 𝑗 + 𝑙)-signed-regular graphs is one of the fascinating problems from application point of view, which is dealt in this paper with insertion of least number of vertices in 𝑆.

Keywords

• Signed graph
• Signed regular graph
• Embedding

2010 Mathematics Subject Classification

• 05C22
• 05C60

References

1. Acharya, B. D. (1982) Construction of certain infinite families of graceful graphs from a given graceful graph, Def. Sci. J., 32 (3), 231–236.
2. Acharya, B. D. Personal communication, 2012.
3. Archdeacon, D. (1990) The complexity of the graph embedding problem, in: Topics in Combinatorics and Graph Theory, R. Bodendiek and R. Henn (Eds.), Physica-Verlag, Heidelberg, 1990, 59–64.
4. Behzad, M., & Chartrand, G. (1971) Introduction to the Theory of Graphs, Allyn and Bacon, Inc., Boston.
5. Bollobas, B., & Eldridge, S. E. (1976) Maximal matchings in graphs with given minimal and maximal degrees, Math. Proc. Cambridge Philos. Soc., 79, 221–234.
6. Gardiner, A. (1983) Embedding 𝑘-regular graphs in 𝑘 + 1-regular graphs, J. London Math. Soc., 2, 28, 393–400.
7. Harary, F. (1969) Graph Theory, Addison-Wesley Publ. Comp., Reading, Massachusetts.
8. Kawarabayashi, K., Mohar, B., & Reed, B. (2008) A simpler linear time algorithm for embedding graphs into an arbitrary surface and the genus of graphs of bounded tree-width, FOCS, IEEE 49th Annual IEEE symposium, 771–780.
9. Juvan, M., & Mohar, B. (1997) A linear time algorithm for the 2-M obius band embedding extension problem, SIAM J. Discrete Math., 10 (1), 57–72.
10. Gupta, A. K., Nelson, D., & Wang, H. (2003) Efficient embeddings of ternary trees into hypercubes, J Parallel Distrib Comput, 63, 619–629.
11. Manuel, P., Arockiaraj, M., Rajasingh, I., & Rajan, B. (2011) Embedding hypercubes into cylinders, snakes and caterpillars for minimizing wire length, Discrete Appl. Math., 159, 2109–2116.
12. Mohar, B. (1996) Embedding graphs in an arbitrary surface in linear time, Proceedings of 28th Ann. ACM STOC, Philadelphia, 392–397.
13. Mohar, B. (1999) A linear time algorithm for embedding of graphs in an arbitrary surface, SIAM J. Discrete Math., 12, 6–26.
14. Mohar, B. (1994) Obstructions for the disk and the cylinder embedding extension problems, Comb. Probab. Comput., 3, 375–406.
15. Rajasingh, I., Manuel, P., Arockiaraj, M., & Rajan, B. (2013) Embeddings of circulant networks, J Comb Optim, 26, 135–151.
16. Raman, I., & Choudum, S.A. (2013) Embedding certain height-balanced trees and complete 𝑝𝑚-ary trees into hypercubes, JDA, 22, 53–65.
17. Singh, T., & Acharya, M. (2013) Embedding of sigraphs in graceful sigraphs, ARS Combinatoria, 111, 421–426.
18. Sinha, D., & Garg, P. (2011) On the regularity of some signed graph structures, AKCE International Journal of Graph and Combinatorics, 8 (1), 63–74.
19. Sinha, D., Rao, A. K., & Garg, P. (2016) Embedding of (𝑖, 𝑗)-Regular Signed Graphs in (𝑖 + 𝑘, 𝑗 + 𝑙)-Regular Signed Graphs, Proceedings of IEEE explore, 2016 International Workshop on Computational Intelligence, Dhaka, Bangladesh, 12–13 December 2016,
    10.1109/IWCI.2016.7860368.
20. West, D. B. (1996) Introduction to Graph Theory, Prentice-Hall of India Pvt. Ltd., India.
21. Zaslavsky, T. (1992) Orientation embedding of signed graphs, J. Graph Theory, 16 (5), 399–422.
22. Zaslavsky, T. (1982) Signed graphs, Discrete Math., 4, 47–74.
23. Zaslavsky, T. (1998) Glossary of signed and gain graphs and allied areas, Electron. J. Combin., II Edition, 1083–1224.
24. Zaslavsky, T. (1998) A mathematical bibliography of signed and gain graphs and allied areas, Electron. J. Combin, VII Edition, 157 pp.