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].     

Heavy cycles passing through some specified vertices in weighted graphs

A weighted graph is one in which every edge e is assigned a nonnegative number, called the weight of e. The sum of the weights of the edges incident with a vertex υ is called the weighted degree of υ. The weight of a cycle is defined as the sum of the weights of its edges. In this paper, we prove that: (1) if G is a 2‐connected weighted graph such that the minimum weighted degree of G is at least d, then for every given vertices x and y, either G contains a cycle of weight at least 2d passing through both of x and y or every heaviest cycle in G is a hamiltonian cycle, and (2) if G is a 2‐connected weighted graph such that the weighted degree sum of every pair of nonadjacent vertices is at least s, then for every vertex y, G contains either a cycle of weight at least s passing through y or a hamiltonian cycle. AMS classification: 05C45 05C38 05C35. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Heavy cycles in 2-connected triangle-free weighted graphs

A weighted graph is one in which every edge e is assigned a nonnegative number, called the weight of e. The sum of the weights of the edges incident with a vertex v is called the weighted degree of v, denoted by dw(v). The weight of a cycle is defined as the sum of the weights of its edges. Fujisawa proved that if G is a 2-connected triangle-free weighted graph such that the minimum weighted degree of G is at least d, then G contains a cycle of weight at least 2d. In this paper, we proved that if G is a2-connected triangle-free weighted graph of even size such that dw(u) + dw(v) ≥ 2d holds for any pair of nonadjacent vertices u, v ∈ V(G), then G contains a cycle of weight at least 2d.     

Claw Conditions for Heavy Cycles in Weighted Graphs

A graph is called a weighted graph when each edge e is assigned a nonnegative number w(e), called the weight of e. For a vertex v of a weighted graph, d^w(v) is the sum of the weights of the edges incident with v. For a subgraph H of a weighted graph G, the weight of H is the sum of the weights of the edges belonging to H. In this paper, we give a new sufficient condition for a weighted graph to have a heavy cycle. A 2-connected weighted graph G contains either a Hamilton cycle or a cycle of weight at least c, if G satisfies the following conditions: In every induced claw or induced modified claw F of G, (1) max{d^w(x),d^w(y)} c/2 for each non-adjacent pair of vertices x and y in F, and (2) all edges of F have the same weight.     

Removable edges in a 5-connected graph and a construction method of 5-connected graphs

An edge e of a k-connected graph G is said to be a removable edge if G?e is still k-connected. A k-connected graph G is said to be a quasi (k+1)-connected if G has no nontrivial k-separator. The existence of removable edges of 3-connected and 4-connected graphs and some properties of quasi k-connected graphs have been investigated [D.A. Holton, B. Jackson, A. Saito, N.C. Wormale, Removable edges in 3-connected graphs, J. Graph Theory 14(4) (1990) 465-473; H. Jiang, J. Su, Minimum degree of minimally quasi (k+1)-connected graphs, J. Math. Study 35 (2002) 187-193; T. Politof, A. Satyanarayana, Minors of quasi 4-connected graphs, Discrete Math. 126 (1994) 245-256; T. Politof, A. Satyanarayana, The structure of quasi 4-connected graphs, Discrete Math. 161 (1996) 217-228; J. Su, The number of removable edges in 3-connected graphs, J. Combin. Theory Ser. B 75(1) (1999) 74-87; J. Yin, Removable edges and constructions of 4-connected graphs, J. Systems Sci. Math. Sci. 19(4) (1999) 434-438]. In this paper, we first investigate the relation between quasi connectivity and removable edges. Based on the relation, the existence of removable edges in k-connected graphs (k?5) is investigated. It is proved that a 5-connected graph has no removable edge if and only if it is isomorphic to K₆. For a k-connected graph G such that end vertices of any edge of G have at most k-3 common adjacent vertices, it is also proved that G has a removable edge. Consequently, a recursive construction method of 5-connected graphs is established, that is, any 5-connected graph can be obtained from K₆ by a number of θ⁺-operations. We conjecture that, if k is even, a k-connected graph G without removable edge is isomorphic to either K_k+1 or the graph H_k/2+1 obtained from K_k+2 by removing k/2+1 disjoint edges, and, if k is odd, G is isomorphic to K_k+1.     

A degree sum condition for long cycles passing through a linear forest

Let G be a (k+m)-connected graph and F be a linear forest in G such that |E(F)|=m and F has at most k-2 components of order 1, where k?2 and m?0. In this paper, we prove that if every independent set S of G with |S|=k+1 contains two vertices whose degree sum is at least d, then G has a cycle C of length at least min{d-m,|V(G)|} which contains all the vertices and edges of F.     

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 heavy paths in 2-connected weighted graphs

A weighted graph is a graph in which every edge is assigned a non-negative real number. In a weighted graph, the weight of a path is the sum of the weights of its edges, and the weighed degree of a vertex is the sum of the weights of the edges incident with it. In this paper we give three weighted degree conditions for the existence of heavy or Hamilton paths with one or two given end-vertices in 2-connected weighted graphs.     

On the sum of Laplacian eigenvalues of graphs

Let k be a natural number and let G be a graph with at least k vertices. Brouwer conjectured that the sum of the k largest Laplacian eigenvalues of G is at most , where e(G) is the number of edges of G. We prove this conjecture for k=2. We also show that if G is a tree, then the sum of the k largest Laplacian eigenvalues of G is at most e(G)+2k-1.     

关于赋权图中重圈的一个范型定理

设G=(V, E; w)为赋权图,定义G中点v的权度d_G^w(v)为G中与v相关联的所有边的权和.该文证明了下述定理: 假设G为满足下列条件的2 -连通赋权图: (i) 对G中任何导出路xyz都有w(xy)=w(yz); (ii)对G中每一个与K_1,3或K_1,3+e同构的导出子图T, T中所有边的权都相等并且min{max{d_G^w(x), d^w_G(y)}:d(x,y)=2,x,y∈ V(T)}≥ c/2. 那么, G中存在哈密尔顿圈或者存在权和至少为 c 的圈. 该结论分别推广了Fan^[5], Bedrossian等人^[2]和Zhang等人^[7]的相关定理     

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).     

Long cycles in bipartite graphs

Let G be a 2-connected bipartite graph with bipartition (A, B), where |A| ≥ |B|. It is shown that if each vertex of A has degree at least k, and each vertex of B has degree at least l, then G contains a cycle of length at least 2min(|B|, k + l ? 1, 2k ? 2). Then this result is used to determine the minimum number of edges required in a bipartite graph to ensure a cycle of length at least 2m, for any integer m ≥ 2.     

Reductions of 3-connected graphs with minimum degree at least four

We show that if G is a 3-connected graph of minimum degree at least 4 and with |V (G)| ≥ 7 then one of the following is true: (1) G has an edge e such that G/e is a 3-connected graph of minimum degree at least 4; (2) G has two edges uv and xy with ux, vy, vx ∈ E(G) such that the graph G/uv/xy obtained by contraction of edges uv and xy in G is a 3-connected graph of minimum degree at least 4; (3) G has a vertex x with N(x) = {x₁, x₂, x₃, x₄} and x₁x₂, x₃x₄ ∈ E(G) such that the graph (G ? x)/x₁x₂/x₃x₄ obtained by contraction of edges x₁x₂ and x₃x₄ in G – x is a 3-connected graph of minimum degree at least 4.

Each of the three reductions is necessary: there exists an infinite family of 3- connected graphs of minimum degree not less than 4 such that only one of the three reductions may be performed for the members of the family and not the two other reductions.     

Connected graphs with maximal Q-index: The one-dominating-vertex case

By the signless Laplacian of a (simple) graph G we mean the matrix Q(G)=D(G)+A(G), where A(G),D(G) denote respectively the adjacency matrix and the diagonal matrix of vertex degrees of G. For every pair of positive integers n,k, it is proved that if 3?k?n-3, then H_n,k, the graph obtained from the star K_1,n-1 by joining a vertex of degree 1 to k+1 other vertices of degree 1, is the unique connected graph that maximizes the largest signless Laplacian eigenvalue over all connected graphs with n vertices and n+k edges.     

A property of weighted graphs without induced cycles of nonpositive weights

It has been conjectured [B. Xu, On signed cycle domination in graphs, Discrete Math. 309 (4) (2009) 1007–1012] that if there is a mapping from the edge set of a 2-connected graph G to {−1,1} such that for each induced subgraph, that is a cycle, the sum of all numbers assigned to its edges by this mapping is positive, then the number of all those edges of G to which 1 is assigned, is more than the number of all other edges of G. This conjecture follows from the main result of this note: If a mapping assigns integers as weights to the edges of a 2-connected graphGsuch that for each edge, its weight is not more than 1 and for each cycle which is an induced subgraph ofG, the sum of all weights of its edges is positive, then the sum of all weights of the edges ofGalso is positive. A simple corollary of this result is the following: If?is a mapping from the edge set of a 2-connected graphGto a set of real numbers such that for each cycleCofG, ∑_e∈E(C)?(e)>0, then∑_e∈E(G)?(e)also is positive.     

A Fan Type Condition For Heavy Cycles in Weighted Graphs

 A weighted graph is a graph in which each edge e is assigned a non-negative number w(e), called the weight of e. The weight of a cycle is the sum of the weights of its edges. The weighted degree d ^w (v) of a vertex v is the sum of the weights of the edges incident with v. In this paper, we prove the following result: Suppose G is a 2-connected weighted graph which satisfies the following conditions: 1. max{d ^w (x),d ^w (y)∣d(x,y)=2}≥c/2; 2. w(x z)=w(y z) for every vertex z∈N(x)∩N(y) with d(x,y)=2; 3. In every triangle T of G, either all edges of T have different weights or all edges of T have the same weight. Then G contains either a Hamilton cycle or a cycle of weight at least c. This generalizes a theorem of Fan on the existence of long cycles in unweighted graphs to weighted graphs. We also show we cannot omit Condition 2 or 3 in the above result. Received: February 7, 2000 Final version received: June 5, 2001     

On matching and total domination in graphs

A set M of edges of a graph G is a matching if no two edges in M are incident to the same vertex. A set S of vertices in G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The matching number is the maximum cardinality of a matching of G, while the total domination number of G is the minimum cardinality of a total dominating set of G. In this paper, we investigate the relationships between the matching and total domination number of a graph. We observe that the total domination number of every claw-free graph with minimum degree at least three is bounded above by its matching number, and we show that every k-regular graph with k?3 has total domination number at most its matching number. In general, we show that no minimum degree is sufficient to guarantee that the matching number and total domination number are comparable.     

Contractible edges in triangle-free graphs

An edge of a graph is calledk-contractible if the contraction of the edge results in ak-connected graph. Thomassen [5] proved that everyk-connected graph of girth at least four has ak-contractible edge. In this paper, we study the distribution ofk-contractible edges in triangle-free graphs and show the following: Whenk≧2, everyk-connected graph of girth at least four and ordern≧3k, hasn+(3/2)k ²-3k or morek-contractible edges.     

Subgraphs with Restricted Degrees of Their Vertices in Planar 3-Connected Graphs

We have proved that every 3-connected planar graph G either contains a path on k vertices each of which has degree at most 5k or does not contain any path on k vertices; the bound 5k is the best possible. Moreover, for every connected planar graph H other than a path and for every integer m ≥ 3 there is a 3-connected planar graph G such that each copy of H in G contains a vertex of degree at least m.     

Removable Edges and Chords of Longest Cycles in 3-Connected Graphs

We verify two special cases of Thomassen’s conjecture of 1976 stating that every longest cycle in a 3-connected graph contains a chord.We prove that Thomassen’s conjecture is true for two classes of 3-connected graphs that have a bounded number of removable edges on or off a longest cycle. Here an edge e of a 3-connected graph G is said to be removable if G – e is still 3-connected or a subdivision of a 3-connected (multi)graph.We give examples to showthat these classes are not covered by previous results.