On the 2-Rotation Distance Graphs (13).pdf

On the exploration of rotation distance graphs in Graph theory

1. On the 2−Rotation Distance Graphs
Rolando S. Merle
Doctor of Philosophy in Mathematics Education
Batangas State University-The National Engineering University
June, 2024
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

2. The Problem and Its Background
Introduction
Graph theoryis a fundamental branch of mathematics that provides
a powerful framework for modeling relationships and structures in
various domains.
A branch of mathematics concerned with networks of points
connected by lines.
A study of graphs and mathematical structures.
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

3. The Problem and Its Background
Introduction
Graph theoryis a fundamental branch of mathematics that provides
a powerful framework for modeling relationships and structures in
various domains.
A branch of mathematics concerned with networks of points
connected by lines.
A study of graphs and mathematical structures.
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

4. The Problem and Its Background
Introduction
Graph theoryis a fundamental branch of mathematics that provides
a powerful framework for modeling relationships and structures in
various domains.
A branch of mathematics concerned with networks of points
connected by lines.
A study of graphs and mathematical structures.
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

5. The Problem and Its Background
In this paper, one of the fundamental concepts in graph theory is the
concept ofisomorphismon graphs.
We say thatGandHare two graphs of the same order and size, but
this does not always imply thatGandHare isomorphic.
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

6. The Problem and Its Background
One way of graph transformation is using an edge rotation. We say
thatGcan be transformed intoHby an edge rotation, ifGcontains
distinct verticesu,v, andwsuch thatuv∈E(G),uw/∈E(G), and
thereforeH≃G–uv+uw.
A graphGisr−transformedintoHifHis obtained fromGby a
sequence of edge rotation, that is if there is a sequence
G={G0,G1, . . . ,Gr}=H(r≥0) of graphs such thatGi+1is
obtained fromGby an edge rotation.Gis generallyr−transformed
intoHifHis obtained fromGby the sequence of edge rotations.Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

7. The Problem and Its Background
One way of graph transformation is using an edge rotation. We say
thatGcan be transformed intoHby an edge rotation, ifGcontains
distinct verticesu,v, andwsuch thatuv∈E(G),uw/∈E(G), and
thereforeH≃G–uv+uw.
A graphGisr−transformedintoHifHis obtained fromGby a
sequence of edge rotation, that is if there is a sequence
G={G0,G1, . . . ,Gr}=H(r≥0) of graphs such thatGi+1is
obtained fromGby an edge rotation.Gis generallyr−transformed
intoHifHis obtained fromGby the sequence of edge rotations.Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

8. The Problem and Its Background
In the study ofChartrand, (1975), and Banaag (2016), operations
were introduced for measuring the distance between graphs of the
same order and size.
Zelinka (1985)introduced the distance between isomorphism classes of
graphs; it showed that on the family of graphs having a fixed order, the
function of the distance graphs produces a metric space.
The rotation distance between graphsGandHis denoted bydr(G,H), if
there exists a sequence of graphsG1,G2, . . .Gk-1such thatG1is obtained
by an edge rotation onG, and for each 1≤i≤k,Gi+1such thatGi+1is
obtained by an edge rotation onGi, withHobtained fromGk−1by one
edge rotation.
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

9. The Problem and Its Background
In [12] showed that the path, fan, corona of the cycle, and path graph
are rotation distance graphs of the same order and size. In the study
by Chartrand (1997) on rotation distance between graphs, he shows
several graphs are rotation distance graphs, including complete
bipartite graphs, cycles, trees, and Cartesian products of jump
distance graphs.
Similarly, in [6] also showed that complete bipartite graphs, trees, and
wheels are rotation distance graphs. He also introduced the edge slide
rotation on graphs.
All of these studies discussed rotation distance, and rotation distance
graphs, and identified which graphs are rotation distance graphs. All
consider the distance between graphsdr(G,H) = 1. None of which
focused on graphs with the rotation distancedr(G,H)=2.
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

10. The Problem and Its Background
In [12] showed that the path, fan, corona of the cycle, and path graph
are rotation distance graphs of the same order and size. In the study
by Chartrand (1997) on rotation distance between graphs, he shows
several graphs are rotation distance graphs, including complete
bipartite graphs, cycles, trees, and Cartesian products of jump
distance graphs.
Similarly, in [6] also showed that complete bipartite graphs, trees, and
wheels are rotation distance graphs. He also introduced the edge slide
rotation on graphs.
All of these studies discussed rotation distance, and rotation distance
graphs, and identified which graphs are rotation distance graphs. All
consider the distance between graphsdr(G,H) = 1. None of which
focused on graphs with the rotation distancedr(G,H)=2.
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

11. The Problem and Its Background
In this paper, the researcher will introduce an extension of rotation
distance and rotation distance graphs, that will be called the
2-rotation distance graphs.
LetS={G1,G2,G3, ...,Gn}is a set of graph with sizemand ordern.
The 2−rotation distance graph ofS, denoted byD2(S) is the graph
withV(D2(S)) =Sand [Gi,Gj]∈E(D2(S) if and only ifdr(Gi,Gj)
= 2.Formal definition of this concept will be provided in Chapter III.
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

12. The Problem and Its Background
In this paper, the researcher will introduce an extension of rotation
distance and rotation distance graphs, that will be called the
2-rotation distance graphs.
LetS={G1,G2,G3, ...,Gn}is a set of graph with sizemand ordern.
The 2−rotation distance graph ofS, denoted byD2(S) is the graph
withV(D2(S)) =Sand [Gi,Gj]∈E(D2(S) if and only ifdr(Gi,Gj)
= 2.Formal definition of this concept will be provided in Chapter III.
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

13. The Problem and Its Background
Objectives
Specifically, this research aims to:
define 2−rotation distance graphs, and prove that the PathPn, Cycle
Cn, andSkare 2−rotation distance graphs;
identify some classes of graphs, which are 2-rotation distance graphs:
Path graph Cycle graph,Tree graph, Wheel graph, Broom graph,
Ladder graph, Star graph;
determines the condition for the corona of the cycle of order n, and
the cycle of ordern,n≥5,n∈Z
+
, the path of orderk,k∈Z
+
, and
star of orderu,u≥5,u∈Z
+
;
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

14. The Problem and Its Background
Objectives
Specifically, this research aims to:
define 2−rotation distance graphs, and prove that the PathPn, Cycle
Cn, andSkare 2−rotation distance graphs;
identify some classes of graphs, which are 2-rotation distance graphs:
Path graph Cycle graph,Tree graph, Wheel graph, Broom graph,
Ladder graph, Star graph;
determines the condition for the corona of the cycle of order n, and
the cycle of ordern,n≥5,n∈Z
+
, the path of orderk,k∈Z
+
, and
star of orderu,u≥5,u∈Z
+
;
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

15. The Problem and Its Background
Objectives
Specifically, this research aims to:
define 2−rotation distance graphs, and prove that the PathPn, Cycle
Cn, andSkare 2−rotation distance graphs;
identify some classes of graphs, which are 2-rotation distance graphs:
Path graph Cycle graph,Tree graph, Wheel graph, Broom graph,
Ladder graph, Star graph;
determines the condition for the corona of the cycle of order n, and
the cycle of ordern,n≥5,n∈Z
+
, the path of orderk,k∈Z
+
, and
star of orderu,u≥5,u∈Z
+
;
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

16. Preliminary Concepts
This chapter defines some basic concepts in Graph Theory necessary
for exploring the rotation distance graphs of some classes of graphs.
Examples of each definition are included to help understand the
concept. In addition, some known theorems in Graph Theory that are
needed in the next chapter are included for reference purposes.
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

17. AgraphGis an ordered pairG= (V(G),E(G))whereV(G)is a
nonempty set of elements calledvertices, andE(G)is a set of
unordered pair of distinct vertices callededgesedges.
b
....................................
....................................
....................................
....................................
....................................
......................................................................................................................................................................................................................
...................................................................................................................................................................................................................................................................................................................................................................................................................................................................
..............................................................................................................................................................................................................................................................
...............................................................................................................
........................................................................................................
G1:
v1
v2
v3
v4
v5
Figure:
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

18. Preliminary Concepts
Isomorphisms
LetGandHbe graphs. The mappingϕ:V(G)→V(H) is called an
isomorphism if it satisfies the following conditions:
i.ϕisbijective(both one-to-one and onto)
ii.[x,y]∈E(G)→[ϕ(x), ϕ(y)]∈E(H)
iii.[u,v]∈E(H) [ϕ
−1
(u),ϕ
1(v)]
∈E(G)
Isomorphic Graphs
The isomorphism of graphsGandHis a bijection between the vertex
sets ofGandH, that is,f:V(G)→V(H), such that any two
verticesuandvofGare adjacent inGif and only iff(u) andf(v)
are adjacent inH. We indicate that the two graphsGandHare
isomorphic graphs by writingG≃H.
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

19. Preliminary Concepts
Isomorphisms
LetGandHbe graphs. The mappingϕ:V(G)→V(H) is called an
isomorphism if it satisfies the following conditions:
i.ϕisbijective(both one-to-one and onto)
ii.[x,y]∈E(G)→[ϕ(x), ϕ(y)]∈E(H)
iii.[u,v]∈E(H) [ϕ
−1
(u),ϕ
1(v)]
∈E(G)
Isomorphic Graphs
The isomorphism of graphsGandHis a bijection between the vertex
sets ofGandH, that is,f:V(G)→V(H), such that any two
verticesuandvofGare adjacent inGif and only iff(u) andf(v)
are adjacent inH. We indicate that the two graphsGandHare
isomorphic graphs by writingG≃H.
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

20. Preliminary Concepts
Some Known Classes of Graphs
Definition
ThePathofordern, denoted byPnis the graph where the vertex can be
labeled 1,2,3,4,5, . . . ,nand whose edges are [1,2], [2,3],...,[n−1,n].
................................................................................... ................................................................................... ....................................
P3
u1u2u3
................................................................................... ................................................................................... ................................................................................... ....................................
P4
u1u2u3u4
................................................................................... ....................................
P2
u1u2
Figure:
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

21. Preliminary Concepts
Some Known Classes of Graphs
Definition
TheCycle graphis a connected graph of lengthn≥3, denoted byCn, is
the graph obtained fromPnby adding one edge joining the vertices of
degree 1 inPn.
Example 2.2.3The cycle of orders 3, 4 and 5 are shown in Figure 2.6
.................................... ............................................................................................................................................
........................................................................................................
....................................
........................................................................................................
............................................................................................................................................
.................................... ............................................................................................................................................
........................................................................................................
....................................
........................................................................................................
....................................
........................................................................................................
.................................... ............................................................................................................................................
........................................................................................................
....................................
........................................................................................................
....................................
........................................................................................................
............................................................................................................................................
............................................................................................................................................
C3 C4 C5
Figure:
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

22. Preliminary Concepts
Some Known Classes of Graphs
Definition
TheFan graph, denoted byFn, is defined as the graph obtained by
joining all the vertices of a pathPnto another vertex called thecenter.
Example 2.2.4TheFan of orderF2,F3respectively are shown in
Figure 2.7.In Figure 2.7,n={3,4,5}; we start with a path graphP3
with three verticesx1,x2, andx
3
. Then, we introduce a center vertex
x1and connect each vertex ofP3tov1. The resulting graph,P3,
resembles a triangle with its vertex connected to a central point.
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

23. Preliminary Concepts
Some Known Classes of Graphs
Definition
TheBroom graph, denoted byBn,k, is a graph of n vertices, which have a
pathPnwith m vertices and (n−m) pendant vertices. All of these vertices
are adjacent to either the origin u or the terminus v of the pathPn.
.................................... .................................... .................................... ....................................
....................................
....................................
......................................................................................................................................................................... ..................................................................................................................................... ..................................................................................................................................................................................................................................................................................................................
.............................................................................................................................................................................
.....................................................................................................................................................................................................................................................................................
x1 x2 x3 x4
x5
x6
x7
B4,3:
Figure: B4,3
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

24. Preliminary Concepts
Some Known Classes of Graphs
Definition
TheLadder graph,Lnis undirected graph with 2nvertices and 3n-2
edges. The verticesaiandbiare the two paths in the graphV(G). The
verticesaiandbiare the two paths in the graphV(G)={aibj}:i=j,
and the edgeE(G) ={aibi+1,bj,bj+1}
............................................................................................................................................ ............................................................................................................................................ ............................................................................................................................................ ............................................................................................................................................ ....................................
........................................................................................................
....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
........................................................................................................
........................................................................................................
........................................................................................................
........................................................................................................
x1 x2 x3 x4 x5
x6x7x8x9x10
Figure: L5
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

25. Preliminary Concepts
Some Known Classes of Graphs
Definition
AStar graph,Snis complete bipartite graphSn-1, which is a tree with
one internal node andkleaves (but no internal nodes andk+ 1 leaves
whenk≤1, Alternatively,Skto be tree of orderkwith maximum
diameter of 2, in which case a star ofk≥2 hask−1 leaves.
........................................................................................................
....................................
....................................
....................................
....................................................................................................................................................................................................................................................
....................................
........................................................................................................
....................................
........................................................................................................
........................................................................................................
....................................
....................................
....................................
....................................................................................................................................................................................................................................................
....................................
....................................................................................................................................................................................................................................................
....................................
........................................................................................................
....................................
........................................................................................................
S5 S6
Figure:
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

26. Preliminary Concepts
Thecorona of two graphsbetweenG1andG2, denoted byG1◦G2,
is the graphGobtained by taking one copy ofG1(which has vertex
ui) andu1∈G1copies ofG2and then joining theith vertex ofG1to
every vertex in theithcopy ofG2.
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

27. Preliminary Concepts
Edge Rotation
Definition
A graphGcan betransformedintoHby an edge rotation (orGcan be
rotated intoH) ifGcontains distinct verticesu,v,w,x, andysuch that
[u,v]∈E(G), [v,y]/∈E(G) andH≃G-[u,v] +[v,y].
....................................
....................................
....................................
....................................
....................................
v
u
w
x
y
.....................................................................................................................................
..................................................................................................................................................................................................................................................................................................................................................................................
......................................................................................................................
..................................................................................................................................................................
G
....................................
....................................
....................................
....................................
....................................................................................................................................................................................................................................................................................................................
..................................................................................................................................................................................................................................................................................................................................................................................
......................................................................................................................
..................................................................................................................................................................
H
v
u
w
x
y
Figure:
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

28. Preliminary Concepts
Edge Rotation Distance
Definition
For two graphsGandHof the same order and same size, the rotation
distance betweenGandH, denoted bydr(G,H), is defined as the smallest
non negative integernfor which there exists a sequenceG1,G2, ....,Gnof
graphs such thatG1≃G,Gn≃H and Gi+1can be obtained fromGiby an
edge rotation fori= 1,2,3,˙..,n.
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

29. Preliminary Concepts
.................................... ....................................
.................................... ....................................
.................................... ....................................x1
x2
x3 x4
x5
x6
........................................................................................................
...............................................
........................................................................................................
...............................................
........................................................................................................
G:
.................................... ....................................
.................................... ....................................
.................................... ....................................x1
x2
x3 x4
x5
x6
........................................................................................................
...............................................
........................................................................................................
...............................................
........................................................................................................
G1:
.................................... ....................................
.................................... ....................................
.................................... ....................................x1
x2
x3 x4
x5
x6
........................................................................................................
...............................................
........................................................................................................
...............................................
......................................................................................................................
........................................................................................................G2:
Figure:
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

30. Preliminary Concepts
.................................... ....................................
.................................... ....................................
.................................... ....................................x1
x2
x3 x4
x5
x6
........................................................................................................
...............................................
........................................................................................................
...............................................
........................................................................................................
G:
.................................... ....................................
.................................... ....................................
.................................... ....................................x1
x2
x3 x4
x5
x6
........................................................................................................
...............................................
........................................................................................................
...............................................
........................................................................................................
G1:
.................................... ....................................
.................................... ....................................
.................................... ....................................x1
x2
x3 x4
x5
x6
........................................................................................................
...............................................
........................................................................................................
...............................................
......................................................................................................................
........................................................................................................G2:
Figure:
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

31. Preliminary Concepts
.................................... ....................................
.................................... ....................................
.................................... ....................................x1
x2
x3 x4
x5
x6
........................................................................................................
...............................................
........................................................................................................
...............................................
........................................................................................................
G:
.................................... ....................................
.................................... ....................................
.................................... ....................................x1
x2
x3 x4
x5
x6
........................................................................................................
...............................................
........................................................................................................
...............................................
........................................................................................................
G1:
.................................... ....................................
.................................... ....................................
.................................... ....................................x1
x2
x3 x4
x5
x6
........................................................................................................
...............................................
........................................................................................................
...............................................
......................................................................................................................
........................................................................................................G2:
Figure:
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

32. Preliminary Concepts
Rotation Distance Graphs
Definition
LetG1,G2,G3,
˙
..,Gnare graphs with sizemand ordern. Define S =
{G1,G2,G3, ....,Gn}. The rotation distance graph ofS, denoted byD(S),
is the graph whereV(D(S))=Sand [Gi,Gj]∈E(D(S)) if and only if
dr(Gi,Gj)=1.
In Figure 2.18, [x1,x2]∈Grotated to [x2,x5]∈G1. Thus,Gis
adjacent toG1sincedr(G, G1)=1.Next, [x2,x5]∈G1rotated to
[x2,x4]∈G2.
Thus,G2is adjacent toG1sincedr(G1,G2)=1.Lastly, [x1,x2]∈G
rotated to [x2,x4]∈G2. Therefore,Gis adjacent toG2since,
dr(G,G2)=1.
Thus,G1is adjacent toGsincedr(G,G1) = 1. The graphG1is adjacent
toG2sincedr(G1,G2)=1.For graphsGandG2, observe thatdr(G,
G2)=1,soG≃G2. Thus,Gis adjacent toG2.
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

33. Preliminary Concepts
Rotation Distance Graphs
Definition
LetG1,G2,G3,
˙
..,Gnare graphs with sizemand ordern. Define S =
{G1,G2,G3, ....,Gn}. The rotation distance graph ofS, denoted byD(S),
is the graph whereV(D(S))=Sand [Gi,Gj]∈E(D(S)) if and only if
dr(Gi,Gj)=1.
In Figure 2.18, [x1,x2]∈Grotated to [x2,x5]∈G1. Thus,Gis
adjacent toG1sincedr(G, G1)=1.Next, [x2,x5]∈G1rotated to
[x2,x4]∈G2.
Thus,G2is adjacent toG1sincedr(G1,G2)=1.Lastly, [x1,x2]∈G
rotated to [x2,x4]∈G2. Therefore,Gis adjacent toG2since,
dr(G,G2)=1.
Thus,G1is adjacent toGsincedr(G,G1) = 1. The graphG1is adjacent
toG2sincedr(G1,G2)=1.For graphsGandG2, observe thatdr(G,
G2)=1,soG≃G2. Thus,Gis adjacent toG2.
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

34. Preliminary Concepts
Rotation Distance Graphs
Definition
LetG1,G2,G3,
˙
..,Gnare graphs with sizemand ordern. Define S =
{G1,G2,G3, ....,Gn}. The rotation distance graph ofS, denoted byD(S),
is the graph whereV(D(S))=Sand [Gi,Gj]∈E(D(S)) if and only if
dr(Gi,Gj)=1.
In Figure 2.18, [x1,x2]∈Grotated to [x2,x5]∈G1. Thus,Gis
adjacent toG1sincedr(G, G1)=1.Next, [x2,x5]∈G1rotated to
[x2,x4]∈G2.
Thus,G2is adjacent toG1sincedr(G1,G2)=1.Lastly, [x1,x2]∈G
rotated to [x2,x4]∈G2. Therefore,Gis adjacent toG2since,
dr(G,G2)=1.
Thus,G1is adjacent toGsincedr(G,G1) = 1. The graphG1is adjacent
toG2sincedr(G1,G2)=1.For graphsGandG2, observe thatdr(G,
G2)=1,soG≃G2. Thus,Gis adjacent toG2.
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

35. Preliminary Concepts
.................................... .........................................................................................................................................................................................................................................................................................................................
.....................................................................................................................................................................................................................................................................................
....................................
.....................................................................................................................................................................................................................................................................................
....................................
.....................................................................................................................................................................................................................................................................................
G
G1 G2
D(S) :
Figure: G,G1andG2
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

36. Preliminary Concepts
Definition
A graphGis a rotation distance graph ifG≃D(S) for some setSof
graphs of the same order and size whereSis defined as that graph with
vertex setSsuchG1andG2are adjacent inDr(S) if and only if
dr(G1,G2) = 1.
Example 2.5.4
LetS={G,G1,G2}whereG,G1,G2, are the graphs
whose pictorial representation are shown in Figure 2.18. Consider the
graphG,G1andG2in Figure 2.18.Thus, a cycleC3is a rotation
distance graph since there exist a graph as shown in Figure 2.18
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

37. Preliminary Concepts
Definition
A graphGis a rotation distance graph ifG≃D(S) for some setSof
graphs of the same order and size whereSis defined as that graph with
vertex setSsuchG1andG2are adjacent inDr(S) if and only if
dr(G1,G2) = 1.
Example 2.5.4
LetS={G,G1,G2}whereG,G1,G2, are the graphs
whose pictorial representation are shown in Figure 2.18. Consider the
graphG,G1andG2in Figure 2.18.Thus, a cycleC3is a rotation
distance graph since there exist a graph as shown in Figure 2.18
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

38. Preliminary Concepts
Some Known Results on Rotation Distance Graphs
In [12], found that path ofordern,Pnand fan graph ofordern,Fn
are rotation distance graphs. In addition, the study proved that corana
Cn◦Pn,n≥3 ,n,k∈Z
+
, and corona Pk◦Cnwheren= 3,k∈Z
+
.
In [1] he introduced that a graphGisrotation distance graphif there
exists a setSof graphs of the sameorderandsizesuch that
G=Dr(S). Complete graphs, trees, cycles, complete bipartite
graphs, and line graphs are rotation distance graphs.He found that for
every two graphsGandHof the sameorderandsize, the jump
distancedj(G,H) betweenGandHis defined as the minimum
number of edge jumps required toj-transformedGintoH.
In [2], showed that the rotation distance between graphsGandHis
the minimum number of rotations necessary to transformGintoH.
Lower and upper bounds are given on the rotation distance graphs in
terms of their greatest common subgraphs and their partial rotating
link of largest cardinality.
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

39. Preliminary Concepts
Some Known Results on Rotation Distance Graphs
In [6], a theorem is developed which states that: IfGandHare two
graphs having the same order and same size, thendr(G,H) =
dr(¯G,¯H).
In [5] showed that ladder graph, triangular snake,generalized Petersen
graph,Gp(n,1), the generalized star,K
(1,n) are edge rotation
distance graphs.
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

40. Results and Discussion
Introduction on the 2−Rotation Distance Graphs
2−Rotation Distance Graphs
LetS={G1,G2,G3, ...,Gn}be a set of graphs with sizemand order
n. The 2−Rotation Distance Graph ofS, denoted byD2(S) is the
graph withV(D2(S)) = Sand[Gi,Gj]∈E(D2(S)) and if and only if
dr(Gi,Gj)= 2.
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

41. Results and Discussion
Introduction on the 2−Rotation Distance Graphs
2−Rotation Distance Graphs
LetS={G1,G2,G3, ...,Gn}be a set of graphs with sizemand order
n. The 2−Rotation Distance Graph ofS, denoted byD2(S) is the
graph withV(D2(S)) = Sand[Gi,Gj]∈E(D2(S)) and if and only if
dr(Gi,Gj)= 2.
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

42. Results and Discussion
....................................
....................................
....................................
....................................
........................................................................
x1
x2
x3
x4
x5x6
...........................................................................................
......................................................................................................................................................................................
..........................................................................................................................................................................................................................................................................
...........................................................................................
G:
....................................
....................................
....................................
....................................
........................................................................
G1:
x1
x2
x3
x4
x5x6
......................................................................................................................................................................................
......................................................................................................................................................................................
..................................................................................................................................... .....................................................................................................................................
Figure: G,G1andG2
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

43. Results and Discussion
....................................
....................................
....................................
....................................
........................................................................
G1:
x1
x2
x3
x4
x5x6
......................................................................................................................................................................................
......................................................................................................................................................................................
..................................................................................................................................... .....................................................................................................................................
....................................
....................................
....................................
....................................
........................................................................
G2:
x1
x2
x3
x4
x5x6
.....................................................................................................................................
...........................................................................................
...........................................................................................
...........................................................................................
..................................................................................................................................... .....................................................................................................................................
Figure: G,G1andG2
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

44. Results and Discussion
....................................
....................................
....................................
....................................
........................................................................
G:
x1
x2
x3
x4
x5x6
...........................................................................................
........................................................................................... ...........................................................................................
.....................................................................................................................................
...........................................................................................
.....................................................................................................................................
....................................
....................................
....................................
....................................
........................................................................
G2:
x1
x2
x3
x4
x5x6
.....................................................................................................................................
...........................................................................................
...........................................................................................
...........................................................................................
..................................................................................................................................... .....................................................................................................................................
Figure: G,G1andG2
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

45. Results and Discussion
In Figure 3.19, let us consider the graphsG,G1, andG2with the
same sizemand ordernand distinct vertices.Gis transformed toG1
by an edge rotation, that is [x2,x3]∈E(G) rotated to [x2,x6]∈G1,
[x3,x4]∈E(G) rotated to [x4,x6]∈G1.
Thus,G1≃G−[x2,x3]−[x3,x4]+[x2,x6]+[x4,x6] with a distance of
dr(G,G1)=2.G1is transformed intoG2by an edge rotation, that is,
[x1,x6]∈G1rotated to [x3,x6]∈G2.Thus,G2≃G1−[x1,x2]−
[x4,x6]+[x2,x4] + [x3,x4] with a rotation distancedr(G1,G2)=2.
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

46. Results and Discussion
In Figure 3.19, let us consider the graphsG,G1, andG2with the
same sizemand ordernand distinct vertices.Gis transformed toG1
by an edge rotation, that is [x2,x3]∈E(G) rotated to [x2,x6]∈G1,
[x3,x4]∈E(G) rotated to [x4,x6]∈G1.
Thus,G1≃G−[x2,x3]−[x3,x4]+[x2,x6]+[x4,x6] with a distance of
dr(G,G1)=2.G1is transformed intoG2by an edge rotation, that is,
[x1,x6]∈G1rotated to [x3,x6]∈G2.Thus,G2≃G1−[x1,x2]−
[x4,x6]+[x2,x4] + [x3,x4] with a rotation distancedr(G1,G2)=2.
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

47. Results and Discussion
Definition
LetGbe a graph. The graphGis a 2−Rotation Distance Graph if there
existsS={G1,G2, ....,Gk}such thatG≃D2(S),
.................................... .........................................................................................................................................................................................................................................................................................................................
.....................................................................................................................................................................................................................................................................................
....................................
.....................................................................................................................................................................................................................................................................................
....................................
.....................................................................................................................................................................................................................................................................................
G
G1 G2
D2(S) :
Figure: −rotation distance graphs
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

48. Results and Discussion
Since there exist graphs in Figure 3.20 , whereS={G,G1,G2)},
which shows thatD2(S) = G is a 2−rotation distance graph.Thus,
a cycleC3is a2−rotation distance graph.
A graphGis a 2−rotation distance graph ifG≃D2(S) for some set
Sof graphs and if and only ifdr(G,H)=2. This study introduced a
set of graphs called 2−rotation distance graphs. IfV(D2(S))=Sand
[Gi,Gj]∈E(D2(S)) if and only ifdr(Gi,Gj)=2.
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

49. Results and Discussion
Since there exist graphs in Figure 3.20 , whereS={G,G1,G2)},
which shows thatD2(S) = G is a 2−rotation distance graph.Thus,
a cycleC3is a2−rotation distance graph.
A graphGis a 2−rotation distance graph ifG≃D2(S) for some set
Sof graphs and if and only ifdr(G,H)=2. This study introduced a
set of graphs called 2−rotation distance graphs. IfV(D2(S))=Sand
[Gi,Gj]∈E(D2(S)) if and only ifdr(Gi,Gj)=2.
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

50. Chartrand,G.,Saba,F., and Zou,H.B. ( 1985). Edge Rotation and Distance
Between Graphs. Sasopis pro pesovani matematiky, 110(1), pp. 87-91
Faudree, R.J. and Schelp R.H.( 1994).On The Rotation Distance of
Graphs, Discrete Mathematics, 126(1-3), pp. 121-135
Faudree, R. J. (1966). Subgroups of the Multiplicative Group of a Division
Ring. Trans. Amer. Math. Soc. 124: 41–48.
Faudree, Ralph; Flandrin, Evelyne; Ryj´aˇcek, Zdenˇek (1997), ”Claw-free
graphs — A survey”, Discrete Mathematics, 164 (1–3): 87–147,
doi:10.1016/S0012-365X(96)00045-3, MR 1432221.
Huilgol, Medha I., Ramaprakash, C. (2016). ” New results on edge rotation
distance graphs” International Journal for Mathematics and Soft
Computing vol.6, No.1,81-91
Jarrett, E. B. (1997). Edge rotation and edge slide distance graphs.
Computers Mathematics with Applications, 34(11), 81-87.
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

51. Zelinka, E. B. (1985). Comaprison of various distances between
isomorphism classes of graphs,Casopis pro pestovani matematiky,
110(3), 289-293
Zelinka, E. B. (1975). On a certain distance between isomorphism classes
of graphs, Casopis pro pestovani matematiky, 33(1),126-130.
Benjamin, A., Chartrand, G., & Zhang, P. (2017). The Fascinating World
of Graph Theory. Princeton University Press.
Harris, J.M et. al. (2008). Combinatorics and Graph Theory.
Sirug, W.S et. al. (2012). Fundamentals of Discrete Mathematics.
Banaag, C. G.,(2016). On the Rotation Distance Graphs. [Unpublished
undergraduate thesis]. Batangas State University, Batangas- The
National Engineering University.
Doria, L., and Guda, A. (2022). On The Central Graph of Sunlet Graph
[Unpublished undergraduate thesis]. Batangas State University - The
National Engineering University.
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024

52. Jahfar, T. K. & Chithra, A. V. Spectra of New Graph Operations based on
Central Graph. ArXiv:2107.00854.
Mame, Neil M. (2011). Generator Subgraphs of Some Classes of Graphs.
(Unpublished doctoral dissertation). De La Salle University, Manila,
Philippines.
Sudha, S., & Manikandan, K. (2017). Total Coloring of Central Graphs of
a Path, a Cycle, and a Star. International Journal of Scientific and
Innovative Mathematical Research, 5(10), 15–22.
https://www.arcjournals.org/international-journal-of-scientific-and-
innovative-mathematical-research/volume-5-issue-10/3.
Graph theory and its uses with 5 examples of real-life problems.
www.xomnia.com. https://www.xomnia.com/post/graph-theory-and-
its-uses-with-examples-of-real-life-problems/
Weisstein, E. W. Graph Subdivision.
https://mathworld.wolfram.com/GraphSubdivision.html
‌
Rolando S. Merle Doctor of Philosophy in Mathematics Education (Batangas State University-The National Engineering University)On the 2−Rotation Distance Graphs June, 2024