Реберный $C_k$-граф графа

For graph theory terminology and notation in this paper we follow the book [3]. All graphs considered in this paper are finite, unoriented, without loops and multiple edges.

Graph theory [3] is an established area of research in combinatorial mathematics. It is also one of the most active areas of mathematics that has found large number of applications in diverse areas including not only computer science, but also chemistry, physics, biology, anthropology, psychology, geography, history, economics, and many branches of engineering. Graph theory has been especially useful in computer science, since after all, any data structure can be represented by a graph. Furthermore, there are applications in networking, in the design of computer architectures, and in general, in virtually every branch of computer science. However, to date most of the research in graph theory has only considered graphs that remain static, i.e., they do not change with time. A wealth of such literature has been developed for static graph theory. Our purpose is to classify dynamic graphs, i.e., graphs that change with time. Dynamic graphs appear in almost all fields of science. This is especially true of computer science, where almost always the data structures (modeled as graphs) change as the program is executed. Very little is known about the properties of dynamic graphs.

The study of graph dynamics has been receiving wide attention, since Ore’s work on the line graph opera I,or L(G) (see [5. 6]). The edge Ck epeetph Ek (G) of a grapli G is defined in [5] as follows: The edge Ck graph of' a graph G = (V, E ) is a grapli Ek (G) = (V ⁰, E) with vertex set V⁰ = E (G) such that two vertices e and f are adjacent if, and only if, the corresponding edges in G either incident or opposite edges of some cycle Ck. So for any two edges in G are adjacent if, and only if, they belongs to a common P 3 оr Ck in G. When k = 3, the definition coincides with triangular line graph of a graph [2], and when k = 4, the definition coincides with E4-grapli of a graph [4].

Throughout this paper we denote by P_n (respectively Cn), a path (respectively cycle) on n vertices. The graph obtained by deleting any edge of K_n is dene)ted by K_n — e. A graph G is H-free if G does not contain H as an induced subgraph. A graph H is a forbidden subgraph for a property P of graphs if no graph having property P contains an induced subgraph isomorphic to H. The cross product G1 x G2 of two graphs G1 aiid G2 is a simple graph with V(G 1 ) x V(G2) as its vertex set and two vertices (u 1 , v 1 ) and (u ₂ , v ₂ ) are adj;icerit in G1 x G2 if. and only if. either u1 = u₂ aiid v 1 is adjacent to v ₂ i 11 G2. c>r u1 is adjacent to u₂ iii G1 and v i = v ₂-

Clearly, the edge Ck graph coincides with the line graph for any acyclic graph. But they differ in many properties. As a case, for a connected graph G, Ek (G) = G if, and only if, G = Cn, n = k. Also Beineke has proved in [1] that the line graph has nine forbidden subgraphs. In this paper, we see that Ek (G) has no forbidden subgraphs.

In the following sections, we presented the characterizations for the edge Ck graph of a graph G is connected, complete, bipartite etc. We have also proved that, the edge C4 graph has no forbidden subgraph characterization. The dynamical behavior such as convergence, periodicity, mortality and touching number of Ek (G) are also studied.

• 2.    Edge Ck Graph of a Graph

The edge Ck gniph Ek(G) of a graph G is defined in [5] as follows: The edge Ck graph of a graph G = (V, E) is a _<graph Ek(G) = (V 0,E0 ). with rvrtex set,. V0 = E (G) such that two vertices e arid f are adjacent, if. arid only if. the corresponding edges in G either incident, or opposite edges of some cycle Ck. So for any two edges in G are adjacent if, and only if, they belongs to a common P3 оr C_k in G. When k = 3, the definition coincides with triangular line graph of a graph [2], and when k = 4, the definition coincides with E4-graph of a graph [4]. Clearly the edge C_k graph coincides with the line graph for any acyclic graph. But they differ in many properties. As a case, for a connected graph G, Ek ( G ) = G if and only if G = C n, n = k. The following result characterizes graphs whose Ek graph is isomorphic to their line graph.

Theorem 1. For a graph G, E_k (G) = L(G) if, and only if, G is C_k-free.

Theorem 2. For any graph G, E_k(G) is connected if, and only if, exactly one component of G contains edges.

Theorem 3. For any graph G. the edge E_k graph is coinplete then diam(G) 6 [ k J.

C Since E_k (G) is complete then bу the definition of E_k (G) any two edges must either incident or belongs to a cycle of length k. Suppose that diam(G) > [2J. That is there exists two vertices u and v in G with d(u, v) > [2J. Ciearly u and v can not be in the some cycle of length [2J. Let u⁰ aiid v⁰ lie any two vertices adjacent, to u and v respectively. Then Ilie edges uu⁰ aiid vv⁰ are not adjacent, and does not. belongs to a cycle of length k. This proves, a contradiction. B

Remark. The converse need not be true for example C5 has diameter 2 but E4(G) is not complete.

In [4], the authors prove that: For a connected graphG, E4(G) is complete if, and only if. G is complete multipartite. But the same can riot lie generalized for k >  5. For example for the peterson graph P, E5(P ) is clearly complete graph K15. Вut P is not complete bipartite. However, we have the following:

Theorem 4. For a. connected graph G. E_k (G) is complete if. and t mly if. every edge of'G belongs to a Ck.

Corollary 5. Let G be a complete r-multipartite graph for some r > 2, Ek(G) is complete.

In [4], the authors proved that the edge C4 graph E4(G) has no forbidden subgraphs. We now prove that the edge C_k graph Ek(G) also have no forbidden subgraph characterization.

Theorem 6. There is no forbidden subgraph characterization for Ek (G) for any k >  3.

• <1 We can assume that k >  5, since the edge C3 of a graph is nothing but triangular line graph and when k = 4, the result follows from the above result. We shall prove that given any graph G. we can find a graph H such that G is an induced subgraph of Ek(H ). For any graph G. lei, H = G x K2 CTearlv H contains 2 copies of G say G and G'. Norv let H ' lie the graph obtained from H by subdivide each edge of one copy of G in H into k — 4 edges.

We claim that, G is induced subgraph of Ek(H'). For any v E V(G) Ek ( G ) contains vertices of the form vv', where v' is the corresponding vertex in G'. Now for any two adjacent vortices u and v. the corresponding vertices uu' aiid vv' are also adjacent in Ek(G) since the vertices u, u',u1,u2, ••• , u k_{- 4},v', v forms a cycle of length k in H '. Now if u and v are поп adjacent adjacent vertices of G then uu' and vv' are also non adjacent vertices in Ek(H '). Thus the subgraph induced by the set {uu' : u E G} of vert ices in H G) contains G as a induced subgraph. This completes the proof. B

Theorem 7. For a connected graph G. E_k(G) is bipartite if ’. and only if G is either a path or an even cycle of length r = k.

• < Supposc that, Ek(G) is bipartite. Suppose that, G has a vertex of degree at least 3. then G contains a cy "de of length 3. Hence, the degree of every vertex is at least 2. Si rice G connected. G must, be a. path or a. cycle. Now. if G is an odd cycle of length r. then r can not be odd or equal to k. since, if r is odd then L(G) is also a cycle which is a subgraph of Ek(G) and if r = k, then Ek(G) = K_r and hence Ek(G) cannot be bipartite in both cases. Finally if r is even and r = k then Ek ( G ) = G. which is bipartite.

• 3.    Dynamical Properties

Conversely, suppose that G is either a path or an even cycle of length r = k, then Ek(G) is either a path or an even cycle respectively. Hence Ek (G) is bipartite. B

Corollary 8. For a connected graph G, E_k (G) is a tree if, and only if, G is a path.

First we recall some graph dynamical terminologies from [6]. Let G be any graph. The nth-iterated graph is iteratively defined as follows: E0(G) = G, Ek(G) = E_k(G), E_k(G) = Ek (En—1(G)), n >  2. We say that G is convergent under Ek if {En(G) : n E N } is finite. If G is riot, convergent under E_k. tlieri G is divergent under E_k. A grapli G is periodic if there is some natural number n with G = E^Tn(G) The smallest such number is called the period of G. The transition number t(x) of a convergent graph G is defined as zero if G is periodic and as the smallest number n such that En(G) is periodic. A graph G is mortal if for some n > N. Ek(G) = ф the empty graph.

Theorem 9. The graphs P_n, K13 C_n (n = k) are the only E_k convergent graphs.

• < If G contains a vertex of degree > 3. then Ek ( G ) coni,ains K4. In I,lie subsequent iterations the clique size goes on increasing and hence G diverges. So, for convergent graphs no) 6 3

If G is a tree which is neither P_n nor Ki,3, then K4 is contained at least in the third iterated graph and hence G cannot converge. B

Corollary 10. For E_k(G). the only periodic graphs are the cycles C_n. n = k and they have period one.

C The paths P_n converge to and K1,3 converges to the triangle. Consider the graphs which are not trees. If G is not a cycle, then G contains a cycle with a pendant edge as a subgraph (need not be induced). Then K4 is a subgraph at least in the second iteration and hence in the subsequent iterations the clique size will go on increasing and hence cannot converge. All cycles except Ck are fixed under Ek and Ck is not convergent. Thus, the proof follows from the fact that a graph G is convergent if, and only if, G is either periodic or there is some positive integer n with En(G) peri*>dic. B

Corollary 11. The transition number t(K1,3 ) = 1 and for n = k, t(C_n) = 0.

Corollary 12. For Ek (G). the paths are the only mortal graphs.

C Among the convergent graphs, cycles other than Ck are fixed and K1,3 converges to K3. The paths are the only graphs converging to ф. B