Monophonic Wirelength in Graph Embedding
Abstract
In this paper we consider the monophonic embedding of
circulant networks into cycles and we produce an algorithm
to get the monophonic wirelength of the same.Further we
nd that the monophonic wirelength of some family of cir-
In this paper, we define the monophonic embedding of graph G into another graph H and this paper presents a monophonic algorithm to find the monophonic wirelength of circulant networks G[n, ±S], where S ⊆ {1,2,3,…,n/2} into the family of Cycle Cn, n≥ 4. The mono-phonic embedding of a graph G into a graph H is an embedding denoted by fmis a bijective map from the vertex set of G into the vertex set of H and fm is a one-one mapping from the edge set (x, y) of G into Pm(H) where Pm(H) is the set of monophonic paths between fm(x) and fm(y) for every fm(x), fm(y) ∈ H. The monophonic wirelength of fm of G into H is the sum of distances of monophonic paths between two vertices fm(x) and fm(y) in H such that (x, y) ∈ E(G). In addition, the eccentricity, radius and diameter of an embedding of G into H are defined. The average wirelength of an embedding is defined and the bounds of average wirelength of some embeddings have been found.
About this article
Keywords
- Circulant Networks
- Congestion
- Cycles
- Embedding
- Wirelength.
References
[1] F. Buckley and F. Harary, Distance in Graph, Addison- Wesley, California, 1990.
[2] A.P. Santhakumaran and P. Titus, “Monophonic Distance in Graphs”, Discrete Mathematics Algorithms Application, Vol.3, No.2, (2011), pp.159-169, https://doi.org/10.1142/S1793830911001176.
[3] P. Maya and T. Nicholas, “Some Results on Integer Edge Cordial Graph”, DJ Journal of Engineering and Applied Mathematics, Vol.3, No.1, (2017), pp. 1-12, https://doi.org/10.18831/djmaths.org/2017011001.
[4] P. Manuel, “Minimum Average Congestion of Enhanced and Augmented Byper-Cube into Complete Binary Tree”, Discrete Applied Mathematics, Vol.159, No.5, (2010), pp.360-366, https://doi.org/10.1016/j.dam.2010.12.001.
[5] IndraRajasingh, Paul Manuel, M. Arockiaraj and BharatiRajan, “Embeddings of Circulant Networks”, Journal of Combinatorial Optimization, Vol.26, No.1, (2013), pp.135-151, https://doi.org/10.1007/s10878-011-9443-x.
[6] P. Manuel, I. Rajasingh, B. Rajan and H. Mercy, “Exact Wirelength of Hypercube on a Grid”, Discrete Applied Mathematics, Vol.157, No.7, (2009), pp.1486-1495.https://doi.org/10.1016/j.dam.2008.09.013.
[7] Jess Mathew, “Subdivided Stars Super (b, d) - Edge-Antimagic Total Graph Labelling”, DJ Journal of Engineering and Applied Mathematics, Vol.1, No.1, (2015), pp.30-34, https://doi.org/10.18831/djmaths.org/2015011005.
[8] S.L. Bezrukov, J.D. Chavez, L. H. Harper, M. Rottger and U. P.Schroeder, “Embedding of Hypercubes into Grids”, International Symposium on Mathematical Foundations of Computer Science, Vol.1450, (1998), pp.693-701, https://doi.org/10.1007/BFb0055820.
[9] L. Bezrukov, “Embedding Complete Trees into the Hypercube”, Discrete Applied Mathematics, Vol.110, No.2-3, (2001), pp.101-119,https://doi.org/10.1016/S0166-218X(00)00256-0.
[10] JasinthaQuadras, S. Sarah Surya, “Linear Wirelength of Circulant Networks”, International Journal of Pure and Applied Mathematics, Vol.86, No.6, (2013), pp.883-891,
[11] P. Manuel, M. Arockiaraj, I. Rajasingh and B. Rajan, “Embedding Hypercubes into Cylinders, Snakes and Caterpillars for Minimizing Wirelength”, Discrete Applied Mathmetics, Vol.159, No.17, (2011), pp.2109-2116, https://doi.org/10.1016/j.dam.2011.07.003.
[12] I. Rajasingh, J. Quadras, P.Manuel and A.William, “Embedding of Cycles and Wheels into Arbitrary Trees”, Networks, Vol.44, (2004), pp.173-178, https://doi.org/10.1002/net.20027.
[13] Arokiaraj, Paul Manuel, IndraRajasingh and BharatiRajan, “Wirelength of 1-Fault Hamiltonian Graphs into Wheels and Fans”, Information Processing Letters, Vol.111, No.18, (2011), pp.921-925,https://doi.org/10.1016/j.ipl.2011.06.011.
[14] F. Harary, Graph Theory, Addison- Wesley, 1969.https://doi.org/10.21236/AD0705364.