Monophonic Wirelength in Graph Embedding

  • Authors

    • Sindhuja G. Michael Assistant Professor, Department of Mathematics, Ponjesly College ofEngineering, Nagercoil, 629003, India
    • K Uma Samundesvari
    2018-06-23
    https://doi.org/10.14419/ijet.v7i3.12603
  • Circulant Networks, Congestion, Cycles, Embedding, Wirelength.

  • 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.

     

     

  • References

    1. [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.

  • Downloads

  • How to Cite

    G. Michael, S., & Uma Samundesvari, K. (2018). Monophonic Wirelength in Graph Embedding. International Journal of Engineering & Technology, 7(3), 1150-1153. https://doi.org/10.14419/ijet.v7i3.12603

    Received date: 2018-05-08

    Accepted date: 2018-05-19

    Published date: 2018-06-23