期刊文章分类查询,尽在期刊图书馆
ZHU Wen-hui
(College of Mathematics and Statistics,Hubei Normal University, Huangshi, Hubei 435002, China)
Abstract: For any graph G = (V (G), E(G)), its transformation graphG++- is the graph with vertex set V (G) ∪ E(G),and there is an edge between vertex α and vertex β in G++- if and only if one of the following three cases holds: if {α, β} V (G) , α is adjacent with β in G; if {α, β} E(G), α is adjacent with β in G; α ∈ V (G), β ∈ E(G) ,or α ∈ E(G), β ∈ V (G), α is not incident with β in G.Let G be a connected simple graph ,a cyclic edge-cut of G is an edge-set F E(G),the removal of F separates at least two components with cycles.G is said to be cyclically separable if G has a cyclic edge-cut.For a cyclic edge-connectivity cλ(G) is the minimum cardinality of all cyclic edge-cuts of G. In this paper,we provide the sufficient and essential conditions of transformation graphG++-to be connected and cyclically separated. And furthermore,we obtain the cyclic edge-connectivity’s upper and lower bounds of transformation graphG++- .
Key words: Transformation graph;Cyclic edge-connectivity.
CLC number:A
1.Introduction
Throughout this paper,only simple graphs without loops or multiple edges are considered.For termi-nology and notation not given here,we refer to the book [1].Let G = (V (G), E(G)) be a graph with vertex set V (G) and edge set E(G).|V (G)| and |E(G)| denote the number of the vertex and edge of G.The dG(v) = {|u| : uv ∈ E(G)} denotes the degree of the vertex v. δ(G) and (G) are the minimum and maximum degree of G respectively.The NG(v) = {u : uv ∈ E(G)} denotes the vertex set which is adjacent with v in G, clearly dG(v) = |NG(v)|. If X, Y V (G) and X ∩ Y = ,then [X, Y ] = {e : e = uv ∈ E(G), u ∈ X, v ∈ Y } denotes the number of edges between X and Y .
In order to research the reliability of network,people raise the index of connectivity.The edge-connectivity λ(G) of a graph G is the minimum cardinality of an edge-cut of G.Every graph G satisfies λ ≤ δ[1].As a more refined index than edge-connectivity,conditional edge-connectivity is introduced by Esfahanian and Hakimi [2].In [2],restricted edge-connectivity λ’(G) is introduced especially which is the minimum cardinality over all restricted edge-cuts S,i.e.,those such that there are no isolated vertices in G-S.Each connected graph G of order n(G) ≥ 4 expect a star,satisfies λ’(G) ≤ ξ(G),where ξ(G) denotes the minimum edge-degree of G defined as ξ(G) = min{d(u) + d(v) - 2 : uv ∈ E(G)}.And then,cyclic edge-connectivity cλ(G) which is the minimum cardinality over all cyclic edge-cuts F.The cyclic edge-cuts F means that there are at least two components with cycles in G-F.For any cyclically separated graph G,satisfies cλ(G) ≤ ω(G)[3],where ω(G) = min{ω(X) = [X, ] : X can induces a shortest cycle of G}.Abviously,cλ(G) ≤ ω(G) ≤ ω(C)(C is a shortest cycle of G).
Next we introduce the definition of the total transformation graph which is raised by Wu[4]. Let graph G = (V (G), E(G)) , x, y, z can equal to {+, -}, the vertex set of total transformation graph Gxyz is V (G) ∪ E(G). For any α, β ∈ V (G) ∪ E(G) , α and β are adjacent in Gxyz if and only if one of the following three conditions holds:
1) For any α, β ∈ V (G), if x = +, then α and β are adjacent in G ;If x = -, then α and β are notadjacent in G;
2) For any α, β ∈ E(G), if y = +, then α and β are adjacent in G ;If y = -, then α and β are notadjacent in G;
3) For any α ∈ V (G), β ∈ E(G),or α ∈ E(G), β ∈ V (G), if z = +, then α and β are incident in G;If z = -, then α and β are not incident in G;
According to the definition,there are 8 kinds of total transformation graph,and G+++ is the total graph T(G) ,in this paper G++ - is the main subject that we are concerned about.
The aim of this paper is to provide the sufficient and essential conditions of transformation graph G++- to be connected and cyclically separated, and furthermore,to obtain the cyclic edge-connectivity’s upper and lower bounds of transformation graph G++-.
2.Cyclic Edge-connectivity of Transformation Graph G++-
For the transformation graph G++-, if {α, β} V (G), then α and β are adjacent in G++- if and only if they areadjacent in G;If {α, β} E(G),then α and β are adjacent in G++- if and only if they are adjacent in G;If α ∈ V (G), β ∈ E(G),or α ∈ E(G), β ∈ V (G), α and β are adjacent in G++- if and only if they are not adjacent in G.
To differ from the vertex in transformation graphs,we call the vertex vertex-vertex which is a vertex in original graph,on the other side we call the vertex edge-vertex which is an edge in original graph.For any vertex-vertex v ∈ V (G), dG++- (v) = dG(v) + (|E(G)| - dG(v)) = |E(G)|; For any edge-vertex e = xy ∈ E(G), dG++- (e) = (dG(x) + dG(y) - 2) + (|V (G)| - 2) = |V (G)| - 4 + (dG(x) + dG(y)).
Lemma 1[5] For any graph G,the transformation graph G++- is connected if and only if G contains at least two edges,and G 2K2.
Lemma 2[6] For any graph G, the inequalities hold:(i)κ(L(G)) ≥ λ(G); (ii)λ(L(G)) ≥ 2λ(G) - 2.
Theorem 1 G++- is connected and cyclically separated if and only if G contains at least two edges,G 2K2 and G K1,k ∪ (n- k-1)K1, n = |V (G)| ≥ k + 1,k ≤ 2.
Proof. If G contains two edges vivj and vsvt which have no common vertex, then there are two cycles with disjoint vertices in G++-,i.e.,vivj est and vsvteij . Otherwise,for any two edges in G,they have a common vertex,then G is a union of a star and some isolated vertices.So G = K1,k ∪ (n-k- 1)K1, n = |V (G)|. When k ≤ 2,it can be testable that there are no disjoint cycles in G++-.When
k ≥ 3,for the star,without loss of generality,suppose the set of vertex-vertices is (1, 2, ? ? ? , n) of which d(1) = n-1, d(2) = d(3) = ? ? ? = d(n) = 1,and the set of edge-vertices is (12, 13, ? ? ? , 1n), therefore G++- always contains two disjoint cycles (4, 12, 13) and (1, 3, 14, 2).And every isolated vertex is adjacent with edge-vertices in G++- ,thereby G++- is connected and cyclically separated if and only if G contains at least two edges,G 2K2 and G K1,k ∪ (n-k-1)K1, n = |V (G)| ≥ k + 1,k ≤ 2.
Corollary 1 G++- is connected and cyclically separated if and only if G contains at least three edges,and G 2K2 ∪ mK1, m ≥ 1.
Theorem 2 Let G++- be connected and cyclically separated,so cλ(G++-) ≤ max{3|E(G)| + 6 (G) )-18, 2|E(G)| + |V (G)| - 6}.
Proof. For any cyclically separated graph G,cλ(G) ≤ ω(G) ≤ ω(C)(C is a shortest cycle of G).
Case1 (G) ≥ 3. v0 is one of the maximum degree vertices in G,and NG(v0) = {v1, v2, v3, ? ? ? , v },so C = e01e02e03 is the shortest cycle of G+++,and ω(C) = dG++- (e0i) )- 6 = 3|E(G)| + 3 (G) - 18 + dG(v1) + dG(v2) + dG(v3) ≤ 3|E(G)| + 6 (G) - 18.
Case2 (G) ≤ 2.
Subcase 2.1 If G contains two edges vivj and vsvt which have no common vertex, then there are two cycles with disjoint vertices in G++-,i.e.,vivj est and vsvteij .vivj est and vsvteij are shortest cycles ,so ω(G) = min{ω(C)} ≤ min{dG(vi) + dG(vj ) + dG(est) - 6, dG(vs) + dG(vt) + dG(eij ) - 6} = 2|E(G)| + |V (G)| - 10 + min{dG(vs) + dG(vt), dG(vi) + dG(vj )} ≤ 2|E(G)| + |V (G)| - 10 + 2 (G) ≤ 2|E(G)| + |V (G)| - 6.
Subcase 2.2 For any two edges in G,they have a common vertex,then G is a union of a star and
some isolated vertices.So G = K1,k ∪ (n- k- 1)K1, n = |V (G)|.Because (G) ≤ 2,so k ≤ 2.Depending on Theorem1,this is a contradiction with the condition that G++- is connected and cyclically separated.So cλ(G++-) ≤ max{3|E(G)| + 6 (G) - 18, 2|E(G)| + |V (G)| - 6}.
Theorem 3 Let G++- be connected and cyclically separated,then cλ(G++-) ≥ min{3λ(G) - 4, |E(G)|(|V (G)| - 2), 2λ(G) + 3|V (G)| - 8, λ(G) + |E(G)|}.
Proof. Let F be one minimum edge-cuts of G++- , T1, T2 are two components which contain
cycles in G++- — F .T01 = T1 ∩ G, T00 1 = T1 ∩ L(G), T02 = T2 ∩ G, T002 = T2 ∩ L(G).
Case1 T01, T00 1, T02, T00 2 .In this case, F = [T1, T2] = [T01, T02]∪[T00 1, T00 2 ]∪[T01, T002 ]∪[T 001, T02]. There are no path from T01 to T02 in G - F,and form T 001 to T 002 in L(G) - F,so |[T01, T02]| ≥ λ(G), |[T 00 1, T00 2 ]| ≥λ(L(G)).Let S = [T01, T00 2 ] ∪ [T 00 1, T02], T12 = {e = uv ∈ V (L(G)) : u ∈ V (T01), v ∈ V (T02)}, |Vmin| =min{|V (T02)|, |V (T01)|},the following partition make the edges of S smallest: L(T02) T 00 1, L(T01) T 00 2, T12 and Vmin are in the different connected components of T1, T2. |S| = |V (T01)|(|E(T01)| - 2) +|V (T02)|(|E(T02)| - 2) + (|Vmin| - 1)[E(G) - E(T01) )- E(T02)] ≥ |V (T01)|(|E(T01)| - 2) + |V (T02)|(|E(T02)| -2)+λ(G)(|Vmin|-1),when |Vmin| = 1,without loss of generality let V (T01) ≤ V (T02),then T01 is an isolated vertex, E(T01) = 0,and T02 = P3 is the boundary(If T02 decreases edges or vertices,G++- will not be connected and cyclically separated).So |S| ≥ -2.Hence |F| ≥ λ(G) + λ(L(G)) - 2 ≥ 3λ(G) ) 4.
Case2 T 00 1 = T02 = and T 00 2, T01 . In this case,T1 = G, T2 = L(G), |F| = |[T1, T2]| = |V (L(G))|(|V (G)| - 2) = |E(G)|(|V (G)| - 2).
Case3 T02 = , T01, T00 1, T00 2 . In this case, T01 = G, T2 L(G).F = [T 00 1, T00 2 ] ∪ [G, T00 2]. There is no path from T 00 1 to T 00 2 in L(G) - F,therefore |[T 00 1, T00 2 ]| ≥ λ(L(G)). Because every vertex in V (L(G)) have |V (G)| - 2 vertices that are adjacent with it in G,so |[G, T00 2 ]| = |V (T2)|(|V (G)| - 2). T2 contains at least one cycle,therefore |V (T2)| ≥ 3,because of Lemma 2 λ(L(G)) ≥ 2λ(G))-2,thereby |F| ≥ λ(L(G)) +3(|V (G)| - 2) ≥ 2λ(G) + 3|V (G)| - 8.
Case4 T 00 2 = , T01, T00 1, T02 .In this case, T 00 1 = L(G), T2 G.F = [T01, T2] ∪ [T 00 1, T02] =[T01, T2] ∪ [L(G) - L(T2), T2] ∪ [L(T2), T2]. There is no path from T01 to T2 in G - F, therefore |[T01, T2]| ≥λ(G).Because |[L(T2), T2]| = |E(T2)|(|V (T2)| - 2) and |[L(G) - L(T2), T2]| = |V (T2)| (V (L(G)) )-V (L(T2))) = |V (T2)|(|E(G)| - |E(T2)|),we can get |F| ≥ λ(G) + |V (T2)||E(G)| - 2|E(T2)|. G is simple graph,also is its subgraph T2,hence |E(T2)| ≤ |V (T2)|(|V (T2)|-1)/ 2 .T2 contains at least one cycle,also does G,so 3 ≤ |V (T2)| ≤ |V (G)| - 1 < |E(G)|,thereby |F| ≥ λ(G) + |E(G)|.
We can devote other cases to the four cases discussed above,the proof is complete.
References
[1] Bondy J A,Murty U S R. Graph theory and its applications[M]. New York:Academic Press,1976.
[2] Esfahanian A H,Hakimi S L.On computing a conditional edge connectivity of a graph,inform,Process,Lett,1988,27:195-199.
[3] Wang B,Zhang Z.On cyclic edge connectivity of transitive graphs[J].Disc. Math.,2009,309:4555-4563.
[4] Wu Bao-yin,Meng Ji-xiang.Basic properties of transformation graphs[J].数学研究,2001,34(2):109-116.
[5] Robert L,Lowell W.Line graphs and line digraphs[M].London:Academic press,1978,271-305.
论文作者:ZHU Wen-hui
论文发表刊物:《创新人才教育》2019年第8期
论文发表时间:2019/11/7
标签：期刊论文; 尽在论文; 文章分类论文; 图书馆论文; 数学论文; people论文; index论文; 《创新人才教育》2019年第8期论文;