Let G=G(V,E) be an undirected graph on n vertices with vertex set V=V(G) and edge set E=E(G). The distance between u,vÎV will be denoted by d(u,v). We write r(u,v)=2 when the vertices u and v are connected by a path of length (the number of edges) two. We use Bondy and Murty [1] for terminology and notation not defined here.
In this paper two distinct graph transformations are considered and their properties are investigated based on special pairs of vertices u, v of a graph G such that a) d(u,v)=2 or b) r(u,v)=2.
Definition 1: Define a transformation D2(G)=H of a graph G by the following way:
- V(H)=V(G),
- uv ÎE(H) if and only if d(u,v)=2 in G.
Analogous transformations can be defined when d(u,v)>2.
Definition 2. Define a transformation L2(G)=H of a graph G by the following way:
- V(H)=V(G),
- uv ÎE(H) if and only if r(u,v)=2 in G:
Let G be a graph and u,vÎV(H): It is easy to see that
- a) if d(u,v)=2 then r(u,v)=2,
- b) if r(u,v)=2 then either d(u,v)=2 or d(u,v)=1. (1)
In addition, it is easy to check that D2(G)≅D2(H) and L2(G)≅ L2(H) if G≅H.
Proposition 1. There exist non isomorphic graphs G and H such that
- a) D2(G)≅D2(H).
- b) L2(G)≅L2(H).
Examples. The empty graph on n vertices and the graph on n vertices with exactly one edge are not isomorphic but their D2-transformations are isomorphic. On the other hand, the complete graph Kn and Kn-e, where eÎE(Kn), are not isomorphic but their L2-transformations are isomorphic too.
Proposition 2. There exists a graph G such that for each graph H,
- the graphs D2(H) and G are not isomorphic (an example: G=Kn).
- b) the graphs L2(H) and G are not isomorphic (an example: G=K1,n-1).
The following can be proved easily.
Proposition 3. If G is a graph with p connected components, then D2(G) and L2(G) are graphs with at least p connected components.
Using (1), we can prove the following.
Lemma 1. If G is a graph without K3 as a subgraph, then D2(G)≅L2(G).
The next proposition follows from the definition of L2(G).
Lemma 2. If G is a graph with a subgraph K3 induced by v1,v2,v3∈V(G), then the subgraph in L2(G) induced by v1,v2,v3 is K3 as well.
The following can be proved using the definition of D2-transformation.
Proposition 4. Let G be a simple cycle on n vertices, denoted by Cn. If n=2k+1 then D2(G)≅G; and if n=2k then D2(G) consists of two disjoint simple cycles on k vertices.
Theorem 1. If G is a complete graph on n vertices, then by deleting at most n-3 edges from G, we get a graph H such that L2(H) is a complete graph as well.
Proof. For each u,vÎV(G), we have uv∈E(L2(G)) if there is a vertex w∈V(G) such that uw,vw∈E(G), i.e. r(u,v)=2, by the definition. Since there are n-2 analogous vertices w in the complete graph G, then by deleting at most n-3 appropriate edges of the type uw or vw, we can get a graph H such that L2(H) is a complete graph.
Theorem 2. If G=Kn then by deleting (n-1)(n-2)/2-ën/2û appropriate edges from G, we can obtain a graph H such that L2(H) is a complete graph as well.
Proof. Let v∈G and let E1 be the set of edges in G incident with v. Delete appropriate edges from E(G)-E1 such that if n=2k+1 then every vertex other than v has a degree 2; and if n=2k then every vertex other than v has a degree 2 except a single vertex of degree 3.
Proposition 5. There is no a graph G on n vertices such that D2(G) is isomorphic to
- a) Kn,
- b) Ki,n-i for each 1 ≤ i ≤ n/2.
Proposition 6. There is no a graph G on n vertices such that L2(G) is isomorphic to Ki,n-i for each 1 ≤ i ≤ n/2.
Problem 1. Extend the list of examples in Propositions 5 and 6.
Problem 2. Give the full characterization of all graph examples in Problem 1.
Let Tn={G1,G2,… ,GN } be the set of all pairwise non isomorphic graphs on n vertices.
Using Tn and D2-transformations, we define a directed graph H1n(D2) by the following way.
- a) V(H1n)=V(Gi) (i=1,2,…),
- b) GiGjÎE(H1n) if D2(Gi)≅Gj, where Gi,GjÎTn.
Using Tn and L2 transformations we define a directed graph H1n(L2) by the following way.
- a) V(H1n)=V(Gi) (i=1,2,…),
- b) GiGjÎE(H1n) if L2(Gi)≅Gj, where Gi,GjÎTn.
Theorem 3. If H1n(D2) has m1 connected components and H1n(L2) has m2 connected components, then m1≤m2.
Proof. Clearly, each of H1n(D2) and H1n(L2) has a loop. These loops generate connected components in such graphs. By Lemma 1 and Lemma 2, every graph containing K3, generates K3 in H1n(L2) as well, which generates connected components. An analogous statement is not true with respect to H1n(D2).
References
- A. Bondy and U.S.R. Murty, Graph Theory with Applications, Macmillan, London and Elsevier, New York (1976).[schema type=»book» name=»ON TWO GRAPH TRANSFORMATION» description=»Two distinct graph transformations (so called D2 and L2-transformations) are considered and their properties are investigated based on special pairs of vertices u, v of a graph G such that a) d(u,v)=2 for D2-transformations and b) there is a path uwv for some third vertex w for L2-transformations. » author=»Sardaryan Gagik Razmik» publisher=»БАСАРАНОВИЧ ЕКАТЕРИНА» pubdate=»2016-12-26″ edition=»euroasia-science.ru_26-27.02.2016_2(23)» ebook=»yes» ]