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

Автор: Сива Кота редди П., Нагарайя К.М., Сиддалингасвами В.М.

Журнал: Владикавказский математический журнал @vmj-ru

Статья в выпуске: 4 т.16, 2014 года.

Бесплатный доступ

Для любого целого $k \geq 4$ реберный $C_k$-граф $E_k(G)$ графа $G$ содержит все ребра графа $G$ в качестве вершин, при этом две вершины смежны в $E_k(G)$, если соответствующие им ребра в графе $G$ либо инцидентны, либо принадлежат копии $C_k$. В статье установлено, что реберный $C_k$-граф графа $G$ является связным, полным, двудольным и т.~д. Доказано также, что реберный $C_4$-граф не имеет характеризаций запрещенными подграфами. Кроме того, исследованы такие характеристики динамических графов как сходимость, периодичность, мортальность и число переходов графа $E_k(G)$.

Короткий адрес: https://sciup.org/14318480

IDR: 14318480

Текст научной статьи Реберный $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 0, E) with vertex set V0 = 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 Pn (respectively Cn), a path (respectively cycle) on n vertices. The graph obtained by deleting any edge of Kn is dene)ted by Kn — 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 2 , v 2 ) are adj;icerit in G1 x G2 if. and only if. either u1 = u2 aiid v 1 is adjacent to v 2 i 11 G2. c>r u1 is adjacent to u2 iii G1 and v i = v 2-

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 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-graph of a graph [4]. 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 = C n, n = k. The following result characterizes graphs whose Ek graph is isomorphic to their line graph.

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

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

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

C Since Ek (G) is complete then bу the definition of Ek (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 u0 aiid v0 lie any two vertices adjacent, to u and v respectively. Then Ilie edges uu0 aiid vv0 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. Ek (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 Ck 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. Ek(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) = Kr 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, Ek (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) = Ek(G), Ek(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 Ek. tlieri G is divergent under Ek. A grapli G is periodic if there is some natural number n with G = ETn(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 Pn, K13 Cn (n = k) are the only Ek 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 Pn nor Ki,3, then K4 is contained at least in the third iterated graph and hence G cannot converge. B

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

C The paths Pn 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(Cn) = 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

Список литературы Реберный $C_k$-граф графа

  • Beineke L. W. Characterizations of derived graphs//J. Combinatorial Theory.-1970.-Vol. 9.-P. 129-135.
  • Jarrett E. B. Transformations of graphs and digraphs. Ph.D. Thesis.-Western Michigan University, 1991.
  • Harary F. Graph Theory.-Addison-Wesley Publ. Co., 1969.
  • Menon Manju K., Vijayakumar A. The edge $C_4$ graph of a graph//Ramanujan Math. Soc. Proc. of ICDM (Bangalore, India, December 15-18, 2006).-2008.-P. 245-248.-(Lecture Notes Series, № 7).
  • Prisner E. Graph Dyanamics.-Longman, 1995.
  • Ore O. Theory of Graphs.-Providence (R.I.): Amer. Math. Soc., 1962.-Vol. 38.
Статья научная