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

**Download 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

- Acharya, B. D. (1982) Construction of certain infinite families of graceful graphs from a given graceful graph, Def. Sci. J., 32 (3), 231–236.
- Acharya, B. D. Personal communication, 2012.
- 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.
- Behzad, M., & Chartrand, G. (1971) Introduction to the Theory of Graphs, Allyn and Bacon, Inc., Boston.
- Bollobas, B., & Eldridge, S. E. (1976) Maximal matchings in graphs with given minimal and maximal degrees, Math. Proc. Cambridge Philos. Soc., 79, 221–234.
- Gardiner, A. (1983) Embedding 𝑘-regular graphs in 𝑘 + 1-regular graphs, J. London Math. Soc., 2, 28, 393–400.
- Harary, F. (1969) Graph Theory, Addison-Wesley Publ. Comp., Reading, Massachusetts.
- 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.
- 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.
- Gupta, A. K., Nelson, D., & Wang, H. (2003) Efficient embeddings of ternary trees into hypercubes, J Parallel Distrib Comput, 63, 619–629.
- 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.
- Mohar, B. (1996) Embedding graphs in an arbitrary surface in linear time, Proceedings of 28th Ann. ACM STOC, Philadelphia, 392–397.
- Mohar, B. (1999) A linear time algorithm for embedding of graphs in an arbitrary surface, SIAM J. Discrete Math., 12, 6–26.
- Mohar, B. (1994) Obstructions for the disk and the cylinder embedding extension problems, Comb. Probab. Comput., 3, 375–406.
- Rajasingh, I., Manuel, P., Arockiaraj, M., & Rajan, B. (2013) Embeddings of circulant networks, J Comb Optim, 26, 135–151.
- Raman, I., & Choudum, S.A. (2013) Embedding certain height-balanced trees and complete 𝑝𝑚-ary trees into hypercubes, JDA, 22, 53–65.
- Singh, T., & Acharya, M. (2013) Embedding of sigraphs in graceful sigraphs, ARS Combinatoria, 111, 421–426.
- Sinha, D., & Garg, P. (2011) On the regularity of some signed graph structures, AKCE International Journal of Graph and Combinatorics, 8 (1), 63–74.
- 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. - West, D. B. (1996) Introduction to Graph Theory, Prentice-Hall of India Pvt. Ltd., India.
- Zaslavsky, T. (1992) Orientation embedding of signed graphs, J. Graph Theory, 16 (5), 399–422.
- Zaslavsky, T. (1982) Signed graphs, Discrete Math., 4, 47–74.
- Zaslavsky, T. (1998) Glossary of signed and gain graphs and allied areas, Electron. J. Combin., II Edition, 1083–1224.
- Zaslavsky, T. (1998) A mathematical bibliography of signed and gain graphs and allied areas, Electron. J. Combin, VII Edition, 157 pp.

## Related papers

## Cite this paper

Sinha, D., & Kumari Rao, A. (2018). Embedding of signed regular graphs. Notes on Number Theory and Discrete Mathematics, 24(3), 131-141, doi: 10.7546/nntdm.2018.24.3.131-141.