27 Фев

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 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,

  1. the graphs D2(H) and G are not isomorphic (an example: G=Kn).
  2. 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

  1. a) Kn,
  2. 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.

  1. a) V(H1n)=V(Gi) (i=1,2,…),
  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.

  1. a) V(H1n)=V(Gi) (i=1,2,…),
  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

  1. A. Bondy and U.S.R. Murty, Graph Theory with Applications, Macmillan, London and Elsevier, New York (1976).
    ON TWO GRAPH TRANSFORMATION
    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.
    Written by: Sardaryan Gagik Razmik
    Published by: БАСАРАНОВИЧ ЕКАТЕРИНА
    Date Published: 12/26/2016
    Edition: euroasia-science.ru_26-27.02.2016_2(23)
    Available in: Ebook