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.     

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.     

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     

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.     

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

设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]的相关定理     

On the edge multicoloring of unicyclic graphs

A multicoloring of an edge weighted graph is an assignment of intervals to its edges so that the intervals of adjacent edges do not intersect at interior points and the length of each interval is equal to the weight of the edge. The minimum length of the union of all intervals is called an edge multichromatic number of the graph. The maximum weighted degree of a vertex (i.e., the sum of the weights of all edges incident with it) is an evident lower bound of this number. There are available the examples in which the multichromatic number is one and a half times larger than the lower bound. Also, there is a conjecture that the bound cannot exceeded by a larger factor. Here we prove this conjecture for the class of unicyclic graphs.     

The weighted complexity and the determinant functions of graphs

The complexity of a graph can be obtained as a derivative of a variation of the zeta function [S. Northshield, A note on the zeta function of a graph, J. Combin. Theory Ser. B 74 (1998) 408-410] or a partial derivative of its generalized characteristic polynomial evaluated at a point [D. Kim, H.K. Kim, J. Lee, Generalized characteristic polynomials of graph bundles, Linear Algebra Appl. 429 (4) (2008) 688-697]. A similar result for the weighted complexity of weighted graphs was found using a determinant function [H. Mizuno, I. Sato, On the weighted complexity of a regular covering of a graph, J. Combin. Theory Ser. B 89 (2003) 17-26]. In this paper, we consider the determinant function of two variables and discover a condition that the weighted complexity of a weighted graph is a partial derivative of the determinant function evaluated at a point. Consequently, we simply obtain the previous results and disclose a new formula for the complexity from a variation of the Bartholdi zeta function. We also consider a new weighted complexity, for which the weights of spanning trees are taken as the sum of weights of edges in the tree, and find a similar formula for this new weighted complexity. As an application, we compute the weighted complexities of the product of the complete graphs.     

Cutting plane algorithms for solving a stochastic edge-partition problem

We consider the edge-partition problem, which is a graph theoretic problem arising in the design of Synchronous Optical Networks. The deterministic edge-partition problem considers an undirected graph with weighted edges, and simultaneously assigns nodes and edges to subgraphs such that each edge appears in exactly one subgraph, and such that no edge is assigned to a subgraph unless both of its incident nodes are also assigned to that subgraph. Additionally, there are limitations on the number of nodes and on the sum of edge weights that can be assigned to each subgraph. In this paper, we consider a stochastic version of the edge-partition problem in which we assign nodes to subgraphs in a first stage, realize a set of edge weights from a finite set of alternatives, and then assign edges to subgraphs. We first prescribe a two-stage cutting plane approach with integer variables in both stages, and examine computational difficulties associated with the proposed cutting planes. As an alternative, we prescribe a hybrid integer programming/constraint programming algorithm capable of solving a suite of test instances within practical computational limits.     

最大Randid指标的k悬挂点化学树的性质

化学分子图G的Randie指标为R（G）=∑wv（dG（u）dG（v））^2/1．其中uv是G的边，dG（u）表示的顶点u的度．本文刻画了具有最大Randie指标的k悬挂点化学树的一些性质．     

Approximation of Dense-n/2-Subgraph and the Complement of Min-Bisection

We consider the DENSE-n/2-SUBGRAPH problem, i.e., determine a block of half number nodes from a weighted graph such that the sum of the edge weights, within the subgraph induced by the block, is maximized. We prove that a strengthened semidefinite relaxation with a mixed rounding technique yields a 0.586 approximations of the problem. The previous best-known results for approximating this problem are 0.25 using a simple coin-toss randomization, 0.48 using a semidefinite relaxation, 0.5 using a linear programming relaxation or another semidefinite relaxation. In fact, an un-strengthened SDP relaxation provably yields no more than 0.5 approximation. We also consider the complement of the graph MIN-BISECTION problem, i.e., partitioning the nodes into two blocks of equal cardinality so as to maximize the weights of non-crossing edges. We present a 0.602 approximation of the complement of MIN-BISECTION.     

最大Randi(c)指标的k悬挂点化学树的性质

化学分子图G的Randic指标为R(G)=E(dG(u)dG(v))-(1/2).其中uv是G的边,dG(u)表示G的顶点u的度.本文刻画了具有最大Randic指标的K悬挂点化学树的一些性质.     

Edge searching weighted graphs

In traditional edge searching one tries to clean all of the edges in a graph employing the least number of searchers. It is assumed that each edge of the graph initially has a weight equal to one. In this paper we modify the problem and introduce the Weighted Edge Searching Problem by considering graphs with arbitrary positive integer weights assigned to its edges. We give bounds on the weighted search number in terms of related graph parameters including pathwidth. We characterize the graphs for which two searchers are sufficient to clear all edges. We show that for every weighted graph the minimum number of searchers needed for a not-necessarily-monotonic weighted edge search strategy is enough for a monotonic weighted edge search strategy, where each edge is cleaned only once. This result proves the NP-completeness of the problem.     

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     

Graph Mates

A weighted digraph graph D is said to be doubly stochastic if all the weights of the edges in D are in [0, 1] and sum of the weights of the edges incident to each vertex in D is one. Let Ω(G) be denoted as set of all doubly stochastic digraphs with n vertices. We defined a Graph Mates in Ω(G) and derived a necessary and sufficient condition for two doubly stochastic digraphs are to be a Graph Mates.     

The max-cut problem and quadratic 0–1 optimization; polyhedral aspects,relaxations and bounds

Given a graphG, themaximum cut problem consists of finding the subsetS of vertices such that the number of edges having exactly one endpoint inS is as large as possible. In the weighted version of this problem there are given real weights on the edges ofG, and the objective is to maximize the sum of the weights of the edges having exactly one endpoint in the subsetS. In this paper, we consider the maximum cut problem and some related problems, likemaximum-2-satisfiability, weighted signed graph balancing. We describe the relation of these problems to the unconstrained quadratic 0–1 programming problem, and we survey the known methods for lower and upper bounds to this optimization problem. We also give the relation between the related polyhedra, and we describe some of the known and some new classes of facets for them.     

w-DENSITY AND w-BALANCED PROPERTY OF WEIGHTED GRAPHS

§ 1　IntroductionAll graphsconsidered in this paperare finite undirected ones withoutloops ormultipleedges.Our terminology and notation are standard exceptas indicated.A good reference forany undefined terms is[1 ] .Let G be a graph with vertex set V( G) and edge set E( G) .The density of G is definedbyd( G) =ε( G)ν( G) ,whereν( G) andε( G) denote| V( G) | and| E( G) | ,respectively.G is said to be balanced iffor each subgraph H of G we have d( H )≤ d( G) ,where V( H ) is assum…     

The new upper bounds on the spectral radius of weighted graphs

Let us consider weighted graphs, where the weights of the edges are positive definite matrices. The eigenvalues of a weighted graph are the eigenvalues of its adjacency matrix and the spectral radius of a weighted graph is also the spectral radius of its adjacency matrix. In this paper, we obtain two upper bounds for the spectral radius of weighted graphs and compare with a known upper bound. We also characterize graphs for which the upper bounds are attained.     

Local and variable neighborhood search for the <Emphasis Type="Italic">k</Emphasis>-cardinality subgraph problem

The minimum weighted k-cardinality subgraph problem consists of finding a connected subgraph of a given graph with exactly k edges whose sum of weights is minimum. For this NP-hard combinatorial problem, only constructive types of heuristics have been suggested in the literature. In this paper we propose a new heuristic based on variable neighborhood search metaheuristic rules. This procedure uses a new local search developed by us. Extensive numerical results that include graphs with up to 5,000 vertices are reported. It appears that VNS outperforms all previous methods.     

Antimagic labeling of generalized pyramid graphs

An antimagic labeling of a graph withq edges is a bijection from the set of edges to the set of positive integers{1,2,...,q}such that all vertex weights are pairwise distinct,where the vertex weight of a vertex is the sum of the labels of all edges incident with that vertex.A graph is antimagic if it has an antimagic labeling.In this paper,we provide antimagic labelings for a family of generalized pyramid graphs.     

On a new edge function on complete weighted graphs and its application for locating Hamiltonian cycles of small weight

In this paper, we define a new combinatorial function on the edges of complete weighted graphs. This function assigns to each edge of the graph the sum of the weights of all Hamiltonian cycles that contain the edge. Since this function involves the factorial function, whose exact calculation is intractable due to its superexponential asymptotic rate of increase, we also introduce a normalized version of the function that is efficiently computable. From this version, we derive an upper bound to the weight of the minimum weight Hamiltonian cycle of the graph based on the weights of the graph edges. Then we investigate the possible algorithmic applications of this normalized function using the Nearest Neighbor Heuristic and a smallest edge first heuristic. As evidence for its applicability, we show that the use of this function as a criterion for the selection of the next edge, improves the performance of both heuristics for approximating the minimum weight Hamiltonian cycles in Euclidean plane graphs. Moreover, our experimental results show that the use of the function is more suitable with the structure of the smallest edge first heuristic since it provides a solution closer to the best known solution of known hard TSP instances but in \(O(n^3)\) time.