ON TWO GRAPH TRANSFORMATION

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:

1. V(H)=V(G),
2. 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:

1. V(H)=V(G),
2. 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

1. a) if d(u,v)=2 then r(u,v)=2,
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

1.      a) D2(G)≅D2(H).
2.        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 K_n and K_n-e, where eÎE(K_n), are not isomorphic but their L2-transformations are isomorphic too.

Proposition 2. There exists a graph G such that for each graph H_,

1. the graphs D2(H) and G are not isomorphic (an example: G=K_n).
2. b) the graphs L2(H) and G are not isomorphic (an example: G=K_1,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 K₃ 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 K₃ induced by v₁,v_2,v₃∈V(G), then  the subgraph in L2(G) induced by v₁,v_2,v₃ is K₃ 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 C_n. 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=K_n 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 E₁ be the set of edges in G incident with v. Delete appropriate edges from E(G)-E₁ 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

1. a) K_n,
2. b) K_i,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 K_i,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 T_n={G₁,G₂,… ,G_N } be the set of all pairwise non isomorphic graphs on n vertices.

Using T_n and D2-transformations, we define a directed graph H¹_n(D2) by the following way.

1. a) V(H¹_n)=V(G_i) (i=1,2,…),
2. b) G_iG_jÎE(H¹_n) if D2(G_i)≅G_j, where G_i,G_jÎT_n.

Using T_n and L2 transformations we define a directed graph H¹_n(L2) by the following way.

1. a) V(H¹_n)=V(G_i) (i=1,2,…),
2. b) G_iG_jÎE(H¹_n) if L2(G_i)≅G_j, where G_i,G_jÎT_n.

Theorem 3. If H¹_n(D2) has m₁ connected components and H¹_n(L2) has m₂ connected components, then m₁≤m₂.

Proof. Clearly, each of H¹_n(D2) and H¹_n(L2) has a loop. These loops generate connected components in such graphs. By Lemma 1 and Lemma 2, every graph containing K₃, generates K₃ in H¹_n(L2) as well, which generates connected components. An analogous statement is not true with respect to H¹_n(D2).

References

1. 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» ]