Abstract

Let S be a set of graphs on which a measure of distance (a metric) has been defined. The distance graph D(S) of S is that graph with vertex set S, such that two vertices(graphs) G and H are adjan- cent if and only if the distance between G and H is one. A graph H is obtained from a graph G by an edge rotation if G contains three distinct vertices u,v and w such that uv ∈ E(G), uw ∈/ E(G) and H ∼=G − uv + uw. In this case, G is transformed into H by “rotating” the edge uv of G into uw. A graph H is obtained from a graph G by an edge jump if G contains four distinct vertices u, v, w and x such that uv∈ E(G), wx ∈/ E(G) and H ∼= G − uv + wx. In this paper, I investigate the effect of the above mentioned edge operations viz., rotation and jump on certain graph parameters. I investigate rotations on DDR graphs, rotations on cycles, paths, Eulerian graphs, eccentric digraphs and the planarity property of the connected graph post edge rotation. We also present an algorithm that generates all rotation distance graphs at distance one.

References

• V. Balaz, J Koca, V. Kvasnika and M. Sekanina, “A metric for graphs”, Discrete Mathematics, 1986, 111(4), 1986, 431-433.
• G. Benade, W. Goddard, T. A. Mckee and P. A. Winter, “On distances between iso- morphism classes of graphs”, 1991,Mathematica Bohemica, 116(2)(1991), 160-169.
• F. Buckley and F. Harary, “Distance in Graphs”, Addison Wesley, (1990).
• G. S. Bloom, L. V. Quintas and J. W. Kennedy, “Some problems concerning distance and path degree sequence”, 1983, Lecture Notes in Math, 1018 Springer - Verlag, Berlin, (1983), 179-190.
• G. S. Bloom, L. V. Quintas and J. W. Kennedy, “Distance Degree Regular Graphs”, The Theory and Applications of graphs, Fourth International conference, Western Michigan University, Kalamazoo, MI May 1980, John Wiley and Sons, New York, (1981), 95-108.
• G. Chartrand, F. Saba and H. B. Zou, “Edge rotations and distances in graphs”,1985, Casopis pro pestovani matematiky”, 110(1)(1985), 87-91.
• G. Chartrand, W. Goddard, M. A. Henning, L. Lesniak, H. Swart and C. E. Wall, “Which graphs are distance graphs?”, Ars Combinatoria, 29A(1990), 225-232.
• G. Chartrand, H. Gavlas, H. Hevia, and M. A. Johnson, “Rotation and jump distances between graphs”, 1997,Discussions Mathematicae, Graph theory, 17(1997), 285-300.
• G. Chartrand and Ping Zhang,“Introduction to graph theory”, Tata McGraw Hill, (2006).
• R. J. Faudree, R. H. Schelp, L. Lesniak, A. Gyarfas and J. Lahel, “On the rotation distance of graphs”, 1994, Discrete Mathematics, North Holland, 126(1994), 121-135.
• W. Goddard and H. C. Swart, “Distance between graphs under edge operations”,1996, Discrete Mathematics, 161(1996), 121-132.
• F. Y. Halberstam and L.V. Quintas, “A note on distance of tables and path degree sequence”, 1982, Conference on Combinatorics, University of Waterloo, Waterloo, Canada, Jine 14 - July 21, (1982).
• Medha Itagi Huilgol, H. B. Walikar and B. D. Acharya, “On diameter three Distance Degree Regular Graphs”, 2011, Advances and Application in Discrete Math, 7(1)(2011), 39-61.
• Medha Itagi Huilgol, M. Rajeshwari and S. Syed Asif Ulla, “Distance Degree Regular graphs and their eccentric digraphs”, 2011, International Journal of Math.Sci and Eng Appln., 5(VI)(2011), 405-416.
• Medha Itagi Huilgol, M. Rajeshwari and S. Syed Asif Ulla, 2012, “Products of DDR and DDI graphs” Journal of Discrete Mathematical Sciences and Cryptography, 15(4:5)(2012), 303-314.
• Medha Itagi Huilgol, M. Rajeshwari and S. Syed Asif Ulla, 2013, “Embedding in distance degree regular and distance degree injective graphs”, Malaya Journal of Matematik, 4(1)(2013), 134-141.
• Medha Itagi Huilgol, Chitra Ramaprakash, “On Edge Rotation Distance graphs”, 2014, IOSR Journal of Mathematics, 6(3), (2014), 16-25.
• Medha Itagi Huilgol, Chitra Ramaprakash, “Edge Jump distance Graphs”, 2015, Journal of Advances in Mathematics, 10(7), (2015), 3664 - 3673.
• Medha Itagi Huilgol, Chitra Ramaprakash, “New Results on edge rotation distance Graphs”, 2016, International Journal of Mathematics and Soft computing, Vol 6, no 1, (2016), 81-91
• E. B. Jarrett, “Edge rotation and edge slide distance graphs”, 1997, Computers Math. Applic., 34(11)(1997), 81-87.
• M. Johnson, “An ordering of some metrics defined on the space of graphs”, 1987, Casopis pro pestovani matematiky, 37(1)(1987), 75-85.
• B. Zelinka, “On a certain distance between isomorphism classes of graphs”, 1975, Casopis pro pestovani matematiky, 100(4)(1975), 371-373.
• B. Zelinka, “A distance between isomorphism classes of graphs”, 1983,Casopis pro pestovani matematiky, 33(1)(1983), 126-130.
• B. Zelinka, “Comparision of various distances between isomorphism classes of graphs”,1985, Casopis pro pestovani matematiky, 110(3)(1985), 289-293.
• B. Zelinka, “Edge distance between isomorphism classes of graphs”, 1987,Casopis pro pestovani matematiky, 112(3)(1987), 233-237.
• B. Zelinka, “The distance between a graph and its compliment”, Casopis pro pestovani matematiky, 37(1)(1987), 120-123.
• B. Zelinka, “Contraction distance between isomorphism classes of graphs”,1990, Casopis pro pestovani matematiky, 115(2)(1990), 211-216.
• MK, “Examples and Counterexamples in Graph Theory”, 2005, CPC press, 2005.