On conditional edge-connectivity of graphs

1. IntroductionIn this paper, a graph G ~ (V,E) always means a simple graph (without loops andmultiple edges) with the vertex-set V and the edge-set E. We follow [1] for graph-theoreticalterllilnology and notation not defined here.It is well known that when the underlying topology of a computer interconnectionnetwork is modeled by a graph G, the edge-connectivity A(G) of G is an important measurefor fault-tolerance of the network. However, it has many deficiencies (see [2]). MotiVatedby t…     

Structures and Chromaticity of Extremal 3-Colourable Sparse Graphs

 Assume that G is a 3-colourable connected graph with e(G) = 2v(G) −k, where k≥ 4. It has been shown that s ₃(G) ≥ 2 ^{k −3}, where s _r (G) = P(G,r)/r! for any positive integer r and P(G, λ) is the chromatic polynomial of G. In this paper, we prove that if G is 2-connected and s ₃(G) < 2 ^{k −2}, then G contains at most v(G) −k triangles; and the upper bound is attained only if G is a graph obtained by replacing each edge in the k-cycle C _k by a 2-tree. By using this result, we settle the problem of determining if W(n, s) is χ-unique, where W(n, s) is the graph obtained from the wheel W _n by deleting all but s consecutive spokes. Received: January 29, 1999 Final version received: April 8, 2000     

Tiling Transitive Tournaments and Their Blow-ups

Let TT _k denote the transitive tournament on k vertices. Let TT(h,k) denote the graph obtained from TT _k by replacing each vertex with an independent set of size h≥1. The following result is proved: Let c ₂=1/2, c ₃=5/6 and c _k =1−2^{−k−log k} for k≥4. For every ∈>0 there exists N=N(∈,h,k) such that for every undirected graph G with n>N vertices and with δ(G)≥c _k n, every orientation of G contains vertex disjoint copies of TT(h,k) that cover all but at most ∈n vertices. In the cases k=2 and k=3 the result is asymptotically tight. For k≥4, c _k cannot be improved to less than 1−2^{−0.5k(1+o(1))}. This revised version was published online in June 2006 with corrections to the Cover Date.     

Super Connectivity and Super Edge Connectivity of the Mycielskian of a Graph

Mycielski introduced a new graph transformation μ(G) for graph G, which is called the Mycielskian of G. A graph G is super connected or simply super-κ (resp. super edge connected or super-λ), if every minimum vertex cut (resp. minimum edge cut) isolates a vertex of G. In this paper, we show that for a connected graph G with |V(G)| ≥ 2, μ(G) is super-κ if and only if δ(G) < 2κ(G), and μ(G) is super-λ if and only if G\ncong K₂{G\ncong K_2}.     

Up-Embeddability of a Graph by Order and Girth

Let G be a connected graph of order n and girth g. If d_G(u) + d_G(v) ≥ n − 2g + 5 for any two non-adjacent vertices u and v, then G is up-embeddable. Further more, the lower bound is best possible. Similarly the result of k-edge connected simple graph with girth g is also obtained, k = 2,3. Partially supported by the Postdoctoral Seience Foundation of Central South University and NNSFC under Grant No. 10751013.     

A sufficient degree condition for a graph to contain all trees of size <Emphasis Type="Italic">k</Emphasis>

The Erdős-Sós conjecture says that a graph G on n vertices and number of edges e(G) > n(k− 1)/2 contains all trees of size k. In this paper we prove a sufficient condition for a graph to contain every tree of size k formulated in terms of the minimum edge degree ζ(G) of a graph G defined as ζ(G) = min{d(u) + d(v) − 2: uv ∈ E(G)}. More precisely, we show that a connected graph G with maximum degree Δ(G) ≥ k and minimum edge degree ζ(G) ≥ 2k − 4 contains every tree of k edges if d _G (x) + d _G (y) ≥ 2k − 4 for all pairs x, y of nonadjacent neighbors of a vertex u of d _G (u) ≥ k.     

Super Connectivity of Line Graphs and Digraphs

The h-super connectivity κh and the h-super edge-connectivity λh are more refined network reliability indices than the conneetivity and the edge-connectivity. This paper shows that for a connected balanced digraph D and its line digraph L, if D is optimally super edge-connected, then κ1（L） = 2λ1 （D）, and that for a connected graph G and its line graph L, if one of κ1 （L） and λ（G） exists, then κ1（L） = λ2（G）. This paper determines that κ1（B（d, n） is equal to 4d- 8 for n = 2 and d ≥ 4, and to 4d-4 for n ≥ 3 and d ≥ 3, and that κ1（K（d, n）） is equal to 4d- 4 for d 〉 2 and n ≥ 2 except K（2, 2）. It then follows that B（d,n） and K（d, n） are both super connected for any d ≥ 2 and n ≥ 1.     

The k-Restricted Edge Connectivity of Balanced Bipartite Graphs

For a connected graph G = (V, E), an edge set S ì E{S\subset E} is called a k-restricted edge cut if G − S is disconnected and every component of G − S contains at least k vertices. The k-restricted edge connectivity of G, denoted by λ _k (G), is defined as the cardinality of a minimum k-restricted edge cut. For two disjoint vertex sets U₁,U₂ ì V(G){U_1,U_2\subset V(G)}, denote the set of edges of G with one end in U ₁ and the other in U ₂ by [U ₁, U ₂]. Define x_k(G)=min{|[U,V(G)\ U]|: U{\xi_k(G)=\min\{|[U,V(G){\setminus} U]|: U} is a vertex subset of order k of G and the subgraph induced by U is connected}. A graph G is said to be λ _k -optimal if λ _k (G) = ξ _k (G). A graph is said to be super-λ _k if every minimum k-restricted edge cut is a set of edges incident to a certain connected subgraph of order k. In this paper, we present some degree-sum conditions for balanced bipartite graphs to be λ _k -optimal or super-λ _k . Moreover, we demonstrate that our results are best possible.     

(3,k)-Factor-Critical Graphs and Toughness

 A graph is (r,k)-factor-critical if the removal of any set of k vertices results in a graph with an r-factor (i.e. an r-regular spanning subgraph). Let t(G) denote the toughness of graph G. In this paper, we show that if t(G)≥4, then G is (3,k)-factor-critical for every non-negative integer k such that n+k even, k<2 t(G)−2 and k≤n−7. Revised: September 21, 1998     

Connected Domination Number of a Graph and its Complement

A set S of vertices in a graph G is a connected dominating set if every vertex not in S is adjacent to some vertex in S and the subgraph induced by S is connected. The connected domination number γ _c (G) is the minimum size of such a set. Let d^*(G)=min{d(G),d([`(G)])}{\delta^*(G)={\rm min}\{\delta(G),\delta({\overline{G}})\}} , where [`(G)]{{\overline{G}}} is the complement of G and δ(G) is the minimum vertex degree. We prove that when G and [`(G)]{{\overline{G}}} are both connected, g<sub>c</sub>(G)+g<sub>c</sub>([`(G)]) ￡ d^*(G)+4-(g_c(G)-3)(g_c([`(G)])-3){{\gamma_c}(G)+{\gamma_c}({\overline{G}})\le \delta^*(G)+4-({\gamma_c}(G)-3)({\gamma_c}({\overline{G}})-3)} . As a corollary, g<sub>c</sub>(G)+g<sub>c</sub>([`(G)]) ￡ \frac3n4{{\gamma_c}(G)+{\gamma_c}({\overline{G}})\le \frac{3n}{4}} when δ*(G) ≥ 3 and n ≥ 14, where G has n vertices. We also prove that g_c(G)+g_c([`(G)]) ￡ d<sup>*</sup>(G)+2{{\gamma_c}(G)+{\gamma_c}({\overline{G}})\le \delta^*(G)+2} when g<sub>c</sub>(G),g<sub>c</sub>([`(G)]) 3 4{{\gamma_c}(G),{\gamma_c}({\overline{G}})\ge 4} . This bound is sharp when δ*(G) = 6, and equality can only hold when δ*(G) = 6. Finally, we prove that g_c(G)g_c([`(G)]) ￡ 2n-4{{\gamma_c}(G){\gamma_c}({\overline{G}})\le 2n-4} when n ≥ 7, with equality only for paths and cycles.     

Some results on distance two labelling of outerplanar graphs

Let G be an outerplanar graph with maximum degree △. Let χ（G^2） and A（G） denote the chromatic number of the square and the L（2, 1）-labelling number of G, respectively. In this paper we prove the following results： （1） χ（G^2） = 7 if △= 6; （2） λ（G） ≤ △ ＋5 if △ ≥ 4, and ）,（G）≤ 7 if △ = 3; and （3） there is an outerplanar graph G with △ = 4 such that ）λ（G） = 7. These improve some known results on the distance two labelling of outerplanar graphs.     

Commutative rings whose zero-divisor graph is a proper refinement of a star graph

A graph is called a proper refinement of a star graph if it is a refinement of a star graph, but it is neither a star graph nor a complete graph. For a refinement of a star graph G with center c, let G _c ^* be the subgraph of G induced on the vertex set V (G)\ {c or end vertices adjacent to c}. In this paper, we study the isomorphic classification of some finite commutative local rings R by investigating their zero-divisor graphs G = Γ(R), which is a proper refinement of a star graph with exactly one center c. We determine all finite commutative local rings R such that G _c ^* has at least two connected components. We prove that the diameter of the induced graph G _c ^* is two if Z(R)² ≠ {0}, Z(R)³ = {0} and G _c ^* is connected. We determine the structure of R which has two distinct nonadjacent vertices α, β ∈ Z(R)* \ {c} such that the ideal [N(α) ∩ N(β)]∪ {0} is generated by only one element of Z(R)*\{c}. We also completely determine the correspondence between commutative rings and finite complete graphs K _n with some end vertices adjacent to a single vertex of K _n .     

图和线图的谱性质

Let G be a simple connected graph with n vertices and m edges,Lo be the line graph of G and λ1(LG)≥λ2 (LG)≥...≥λm(LG) be the eigenvalues of the graph LG,.. In this paper, the range of eigenvalues of a line graph is considered. Some sharp upper bounds and sharp lower bounds of the eigenvalues of Lc. are obtained. In oarticular,it is oroved that-2cos(π/n)≤λn-1(LG)≤n-4 and λn(LG)=-2 if and only if G is bipartite.     

On the total domination subdivision numbers in graphs

A set S of vertices of a graph G = (V, E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γ _t (G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sd_γt (G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. Karami, Khoeilar, Sheikholeslami and Khodkar, (Graphs and Combinatorics, 2009, 25, 727–733) proved that for any connected graph G of order n ≥ 3, sd_{γ t} (G) ≤ 2γ _t (G) − 1 and posed the following problem: Characterize the graphs that achieve the aforementioned upper bound. In this paper we first prove that sd_{γ t} (G) ≤ 2α′(G) for every connected graph G of order n ≥ 3 and δ(G) ≥ 2 where α′(G) is the maximum number of edges in a matching in G and then we characterize all connected graphs G with sd_{γ t} (G)=2γ _t (G)−1.     

The Decomposition Dimension of Graphs

 For an ordered k-decomposition ? = {G ₁, G ₂,…,G _k } of a connected graph G and an edge e of G, the ?-representation of e is the k-tuple r(e|?) = (d(e, G ₁), d(e, G ₂),…,d(e, G _k )), where d(e, G _i ) is the distance from e to G _i . A decomposition ? is resolving if every two distinct edges of G have distinct representations. The minimum k for which G has a resolving k-decomposition is its decomposition dimension dec(G). It is shown that for every two positive integers k and n≥ 2, there exists a tree T of order n with dec(T) = k. It is also shown that dec(G) ≤n for every graph G of order n≥ 3 and that dec(K _n ) ≤⌊(2n + 5)/3⌋ for n≥ 3. Received: June 17, 1998 Final version received: August 10, 1999     

Adjacent strong edge colorings and total colorings of regular graphs

It is conjectured that χas(G) = χt(G) for every k-regular graph G with no C5 component (k 2). This conjecture is shown to be true for many classes of graphs, including: graphs of type 1; 2-regular, 3-regular and (|V (G)| - 2)-regular graphs; bipartite graphs; balanced complete multipartite graphs; k-cubes; and joins of two matchings or cycles.     

Sparse Graphs which Decompose into Closed Trails of Arbitrary Lengths

A simple, connected even graph G with vertex set V(G) and edge set E(G) is said to be ADCT (Arbitrarily Decomposable into Closed Trails) if for any collection of positive integers x ₁, x ₂,...,x _m with and x _i ≥ 3 for 1 ≤ i ≤ m, there exists a decomposition of G into closed trails (circuits) of lengths x ₁, x ₂,...,x _m . In this note we construct an 8-regular ADCT graph on 6n vertices, for each each n ≥ 3. On the other hand, we also show that there are only finitely many 4-regular graphs which are ADCT. Received July 26, 2006. Final version received: March 5, 2008.     

Injective (Δ + 1)-coloring of planar graphs with girth 6

A vertex coloring of a graph G is called injective if every two vertices joined by a path of length 2 get different colors. The minimum number χ _i (G) of the colors required for an injective coloring of a graph G is clearly not less than the maximum degree Δ(G) of G. There exist planar graphs with girth g ≥ 6 and χ _i = Δ+1 for any Δ ≥ 2. We prove that every planar graph with Δ ≥ 18 and g ≥ 6 has χ _i ≤ Δ + 1.     

An Upper Bound for the Total Domination Subdivision Number of a Graph

A set S of vertices of a graph G = (V, E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γ _t (G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sd_gt(G){{\rm sd}_{\gamma_t}(G)} is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. In this paper, we prove that sd_gt(G) ￡ 2g_t(G)-1{{\rm sd}_{\gamma_t}(G)\leq 2\gamma_t(G)-1} for every simple connected graph G of order n ≥ 3.     

Zero-Sum Flows in Regular Graphs

For an undirected graph G, a zero-sum flow is an assignment of non-zero real numbers to the edges, such that the sum of the values of all edges incident with each vertex is zero. It has been conjectured that if a graph G has a zero-sum flow, then it has a zero-sum 6-flow. We prove this conjecture and Bouchet’s Conjecture for bidirected graphs are equivalent. Among other results it is shown that if G is an r-regular graph (r ≥ 3), then G has a zero-sum 7-flow. Furthermore, if r is divisible by 3, then G has a zero-sum 5-flow. We also show a graph of order n with a zero-sum flow has a zero-sum (n + 3)²-flow. Finally, the existence of k-flows for small graphs is investigated.