Removable edges in cycles of a <Emphasis Type="Italic">k</Emphasis>-connected graph

An edge e of a k-connected graph G is said to be a removable edge if G ⊖ e is still k-connected, where G ⊖ e denotes the graph obtained from G by deleting e to get G − e, and for any end vertex of e with degree k − 1 in G − e, say x, delete x, and then add edges between any pair of non-adjacent vertices in N _G−e (x). The existence of removable edges of k-connected graphs and some properties of 3-connected graphs and 4-connected graphs have been investigated. In the present paper, we investigate some properties of k-connected graphs and study the distribution of removable edges on a cycle in a k-connected graph (k ≥ 4).     

Removable Edges in Longest Cycles of 4-Connected Graphs

Let G be a 4-connected graph. For an edge e of G, we do the following operations on G: first, delete the edge e from G, resulting the graph G–e; second, for all vertices x of degree 3 in G–e, delete x from G–e and then completely connect the 3 neighbors of x by a triangle. If multiple edges occur, we use single edges to replace them. The final resultant graph is denoted by Ge. If Ge is 4-connected, then e is called a removable edge of G. In this paper we obtain some results on removable edges in a longest cycle of a 4-connected graph G. We also show that for a 4-connected graph G of minimum degree at least 5 or girth at least 4, any edge of G is removable or contractible.Acknowledgment. The authors are greatly indebted to a referee for his valuable suggestions and comments, which are very helpful to improve the proof of our main result Lemma 3.3.Research supported by National Science Foundation of China AMS subject classification (2000): 05C40, 05C38, 05C75Final version received: March 10, 2004     

Heavy cycles in k-connected weighted graphs with large weighted degree sums

A weighted graph is one in which every edge e is assigned a nonnegative number w(e), called the weight of e. The weight of a cycle is defined as the sum of the weights of its edges. The weighted degree of a vertex is the sum of the weights of the edges incident with it. In this paper, we prove that: Let G be a k-connected weighted graph with k?2. Then G contains either a Hamilton cycle or a cycle of weight at least 2m/(k+1), if G satisfies the following conditions: (1) The weighted degree sum of any k+1 pairwise nonadjacent vertices is at least m; (2) In each induced claw and each induced modified claw of G, all edges have the same weight. This generalizes an early result of Enomoto et al. on the existence of heavy cycles in k-connected weighted graphs.     

Neighborhoods and Covering Vertices by Cycles

G =(V,E) is a 2-connected graph, and X is a set of vertices of G such that for every pair x,x' in X, , and the minimum degree of the induced graph <X> is at least 3, then X is covered by one cycle. This result will be in fact generalised by considering tuples instead of pairs of vertices. Let be the minimum degree in the induced graph <X>. For any , . If , and , then X is covered by at most (p-1) cycles of G. If furthermore , (p-1) cycles are sufficient. So we deduce the following: Let p and t () be two integers. Let G be a 2-connected graph of order n, of minimum degree at least t. If , and , then V is covered by at most cycles, where k is the connectivity of G. If furthermore , (p-1) cycles are sufficient. In particular, if and , then G is hamiltonian. Received April 3, 1998     

Non-Separating Paths in 4-Connected Graphs

In 1975, Lovász conjectured that for any positive integer k, there exists a minimum positive integer f(k) such that, for any two vertices x, y in any f(k)-connected graph G, there is a path P from x to y in G such that G–V(P) is k-connected. A result of Tutte implies f(1) = 3. Recently, f(2) = 5 was shown by Chen et al. and, independently, by Kriesell. In this paper, we show that f(2) = 4 except for double wheels.Received October 17, 2003     

Edge degrees and dominating cycles

The edge degree d(e) of the edge e=uv is defined as the number of neighbours of e, i.e., |N(u)∪N(v)|-2. Two edges are called remote if they are disjoint and there is no edge joining them. In this article, we prove that in a 2-connected graph G, if d(e₁)+d(e₂)>|V(G)|-4 for any remote edges e₁,e₂, then all longest cycles C in G are dominating, i.e., G-V(C) is edgeless. This lower bound is best possible.As a corollary, it holds that if G is a 2-connected triangle-free graph with σ₂(G)>|V(G)|/2, then all longest cycles are dominating.     

Dominating sets of the comaximal and ideal-based zero-divisor graphs of commutative rings

Abstract

Let R be a commutative ring with nonzero identity, and let I be an ideal of R. The ideal-based zero-divisor graph of R, denoted by Γ_I (R), is the graph whose vertices are the set {x ∈ R \ I| xy ∈ I for some y∈ R \ I} and two distinct vertices x and y are adjacent if and only if xy ∈ I. Define the comaximal graph of R, denoted by CG(R), to be a graph whose vertices are the elements of R, where two distinct vertices a and b are adjacent if and only if Ra+Rb=R. A nonempty set S ? V of a graph G=(V, E) is a dominating set of G if every vertex in V is either in S or is adjacent to a vertex in S. The domination number γ(G) of G is the minimum cardinality among the dominating sets of G. The main object of this paper is to study the dominating sets and domination number of Γ_I (R) and the comaximal graph CG₂(R) \ J (R) (or CGJ (R) for short) where CG₂(R) is the subgraph of CG(R) induced on the nonunit elements of R and J (R) is the Jacobson radical of R.     

ON 3-CHOOSABILITY OF PLANE GRAPHS WITHOUT 6-,7- AND 9-CYCLES

The choice number of a graph G,denoted by X1(G),is the minimum number k such that if a list of k colors is given to each vertex of G,there is a vertex coloring of G where each vertex receives a color from its own list no matter what the lists are. In this paper,it is showed that X1 (G)≤3 for each plane graph of girth not less than 4 which contains no 6-, 7- and 9-cycles.     

A note on Z 3-connected graphs with degree sum condition

A graph G satisfies the Ore-condition if d(x) + d(y) ≥ | V (G) | for any xy ■ E(G). Luo et al. [European J. Combin., 2008] characterized the simple Z3-connected graphs satisfying the Ore-condition. In this paper, we characterize the simple Z3-connected graphs G satisfying d(x) + d(y) ≥ | V (G) |-1 for any xy ■ E(G), which improves the results of Luo et al.     

On the structure of unbreakable graphs

A nonempty set C of vertices is a star-cutset in a graph G if G – C is disconnected and some vertex in C is adjacent to all the remaining vertices in C. Va?ek Chvátal proposed to call a graph G unbreakable if neither G nor its complement G has a star-cutset. A path with four vertices and three edges will be termed a P₄. An edge uv of a graph G is called a wing, if for some vertices x, y, {u,v,x,y} induces a P₄ in G. We define recursively the coercion class C_uv of a wing uv as follows:

• 1 uv ∈ C_uv, and
• 1 if xy ∈ C_uv and xy, x'y' are wings of a same P₄ in G, then x'y' ∈ C_uv.

The purpose of this work is to present new results concerning unbreakable graphs, using the notion of coercion class. These results include a theorem asserting that every unbreakable graph contains at most two distinct coercion classes and a structure theorem for those unbreakable graphs that contain precisely two coercion classes. These results generalize several previously known results about unbreakable graphs.     

Removable edges of cycles in 5-connected graphs

Let G be a 5-connected graph. For an edge e of G, we do the following operations on G: first, delete the edge e from G, resulting the graph G?e; second, for each vertex x of degree 4 in G?e, delete x from G?e and then completely connect the 4 neighbors of x by K ₄. If multiple edges occur, we use single edge to replace them. The final resultant graph is denoted by G ? e. If G ? e is still 5-connected, then e is called a removable edge of G. In this paper, we investigate the distribution of removable edges in a cycle of a 5-connected graph. And we give examples to show some of our results are best possible in some sense.     

On the Szeged and the Laplacian Szeged spectrum of a graph

For a given graph G its Szeged weighting is defined by w(e)=n_u(e)n_v(e), where e=uv is an edge of G,n_u(e) is the number of vertices of G closer to u than to v, and n_v(e) is defined analogously. The adjacency matrix of a graph weighted in this way is called its Szeged matrix. In this paper we determine the spectra of Szeged matrices and their Laplacians for several families of graphs. We also present sharp upper and lower bounds on the eigenvalues of Szeged matrices of graphs.     

Cycles in weighted graphs

A weighted graph is one in which each edgee is assigned a nonnegative numberw(e), called the weight ofe. The weightw(G) of a weighted graphG is the sum of the weights of its edges. In this paper, we prove, as conjectured in [2], that every 2-edge-connected weighted graph onn vertices contains a cycle of weight at least 2w(G)/(n–1). Furthermore, we completely characterize the 2-edge-connected weighted graphs onn vertices that contain no cycle of weight more than 2w(G)/(n–1). This generalizes, to weighted graphs, a classical result of Erds and Gallai [4].     

Hamiltonian cycles in Dirac graphs

We prove that for any n-vertex Dirac graph (graph with minimum degree at least n/2) G=(V,E), the number, Ψ(G), of Hamiltonian cycles in G is at least

$exp_2 [2h(G) - n\log e - o(n)],$

where h(G)=maxΣ _e x _e log(1/x _e ), the maximum over x: E → ?⁺ satisfying Σ _e?υ x _e = 1 for each υ ∈ V, and log =log₂. (A second paper will show that this bound is tight up to the o(n).)

We also show that for any (Dirac) G of minimum degree at least d, h(G) ≥ (n/2) logd, so that Ψ(G) > (d/(e + o(1))) ⁿ . In particular, this says that for any Dirac G we have Ψ(G) > n!/(2 + o(1)) ⁿ , confirming a conjecture of G. Sárközy, Selkow, and Szemerédi which was the original motivation for this work.     

Edges not contained in triangles and the distribution of contractible edges in a 4-connected graph

We prove results concerning the distribution of 4-contractible edges in a 4-connected graph G in connection with the edges of G not contained in a triangle. As a corollary, we show that if G is 4-regular 4-connected graph, then the number of 4-contractible edges of G is at least one half of the number of edges of G not contained in a triangle.     

On a Max-min Problem Concerning Weights of Edges

The weight w(e) of an edge e = uv of a graph is defined to be the sum of degrees of the vertices u and v. In 1990 P. Erdős asked the question: What is the minimum weight of an edge of a graph G having n vertices and m edges? This paper brings a precise answer to the above question of Erdős. Received July 12, 1999     

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.     

Total domination in claw-free graphs with minimum degree 2

A set S of vertices in a graph G is a total dominating set (TDS) of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a TDS of G is the total domination number of G, denoted by γ_t(G). A graph is claw-free if it does not contain K_1,3 as an induced subgraph. It is known [M.A. Henning, Graphs with large total domination number, J. Graph Theory 35(1) (2000) 21-45] that if G is a connected graph of order n with minimum degree at least two and G∉{C₃,C₅, C₆, C₁₀}, then γ_t(G)?4n/7. In this paper, we show that this upper bound can be improved if G is restricted to be a claw-free graph. We show that every connected claw-free graph G of order n and minimum degree at least two satisfies γ_t(G)?(n+2)/2 and we characterize those graphs for which γ_t(G)=⌊(n+2)/2⌋.     

Entropy bounds for perfect matchings and Hamiltonian cycles

For a graph G = (V,E) and x: E → ℜ⁺ satisfying Σ _e∋υ x _e = 1 for each υ ∈ V, set h(x) = Σ _e x _e log(1/x _e ) (with log = log₂). We show that for any n-vertex G, random (not necessarily uniform) perfect matching f satisfying a mild technical condition, and x _e =Pr(e∈f),

Canonical edge-colourings of locally finite graphs

A variety of results on edge-colourings are proved, the main one being the following: ifG is a graph without loops or multiple edges and with maximum degree Δ=Δ(G), and if ν is a given integer 1≦ν≦Δ(G), thenG can be given a proper edge-colouring with the coloursc ₁, ...,c _Δ+1 with the additional property that any edge colouredc _μ with μ≧ν is on a vertex which has on it edges coloured with at least ν − 1 ofc ₁, ...,c _v .