On the m-capacitated peripatetic salesman problem with capacity restrictions

We consider a special case of the problem of finding m Hamiltonian cycles with capacity restrictions on the number of usages of the edges (m-Capacitated Peripatetic Salesman Problem or m-CPSP): the minimization and maximization 2-CPSP with edge weights chosen from an integer segment {1, q} with the edges capacities given as independent identically distributed random variables equal to 2 with probability p and 1 with probability (1 ? p). Some polynomial algorithms are proposed for 2-CPSP_min and 2-CPSP_max with average performance guarantees. In particular, when the edge weights are equal to 1 and 2, the algorithms have approximation ratios (19 ? 5p)/12 and (25 + 7p)/36 for the minimization and the maximization problem correspondingly.     

An interpretation of the Dittert conjecture in terms of semi-matchings

Let G be K_n,n with non-negative edge weights and let U and V be the two colour classes of vertices in G. We define a k-semimatching in G to be a set of k edges such that the edges either have distinct ends in U or distinct ends in V. Semimatchings are to be counted according to the product of the weights on the edges in the semimatching. The Dittert conjecture is a longstanding open problem involving matrix permanents. Here we show that it is equivalent to the following assertion: For a fixed total weight, the number of n-semimatchings in G is maximised by weighting all edges of G equally. We also introduce sub-Dittert functions which count k-semimatchings and are analogous to the subpermanent functions which count k-matchings. We prove some results about the extremal values of our sub-Dittert functions, and also that the Dittert conjecture cannot be disproved by means of unweighted graphs.     

Minmax subtree cover problem on cacti

Let G=(V,E) be a connected graph such that edges and vertices are weighted by nonnegative reals. Let p be a positive integer. The minmax subtree cover problem (MSC) asks to find a pair (X,T) of a partition X={X₁,X₂,…,X_p} of V and a set T of p subtrees T₁,T₂,…,T_p, each T_i containing X_i so as to minimize the maximum cost of the subtrees, where the cost of T_i is defined to be the sum of the weights of edges in T_i and the weights of vertices in X_i. In this paper, we propose an O(p²n) time (4-4/(p+1))-approximation algorithm for the MSC when G is a cactus.     

An approximation algorithm for finding a <Emphasis Type="Italic">d</Emphasis>-regular spanning connected subgraph of maximum weight in a complete graph with random weights of edges

An approximation algorithm is suggested for the problem of finding a d-regular spanning connected subgraph of maximum weight in a complete undirected weighted n-vertex graph. Probabilistic analysis of the algorithm is carried out for the problem with random input data (some weights of edges) in the case of a uniform distribution of the weights of edges and in the case of a minorized type distribution. It is shown that the algorithm finds an asymptotically optimal solution with time complexity O(n ²) when d = o(n). For the minimization version of the problem, an additional restriction on the dispersion of weights of the graph edges is added to the condition of the asymptotical optimality of the modified algorithm.     

Extremals of functions on graphs with applications to graphs and hypergraphs

The method used in an article by T. S. Matzkin and E. G. Straus [Canad. J. Math.17 (1965), 533–540] is generalized by attaching nonnegative weights to t-tuples of vertices in a hypergraph subject to a suitable normalization condition. The edges of the hypergraph are given weights which are functions of the weights of its t-tuples and the graph is given the sum of the weights of its edges. The extremal values and the extremal points of these functions are determined. The results can be applied to various extremal problems on graphs and hypergraphs which are analogous to P. Turán's Theorem [Colloq. Math.3 (1954), 19–30: (Hungarian) Mat. Fiz. Lapok48 (1941), 436–452].     

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.     

An approximation algorithm for multidimensional assignment problems minimizing the sum of squared errors

Given a complete k-partite graph G=(V₁,V₂,…,V_k;E) satisfying |V₁|=|V₂|=?=|V_k|=n and weights of all  k-cliques of G, the  k-dimensional assignment problem finds a partition of vertices of G into a set of (pairwise disjoint) n k-cliques that minimizes the sum total of weights of the chosen cliques. In this paper, we consider a case in which the weight of a clique is defined by the sum of given weights of edges induced by the clique. Additionally, we assume that vertices of G are embedded in the d-dimensional space Q^d and a weight of an edge is defined by the square of the Euclidean distance between its two endpoints. We describe that these problem instances arise from a multidimensional Gaussian model of a data-association problem.We propose a second-order cone programming relaxation of the problem and a polynomial time randomized rounding procedure. We show that the expected objective value obtained by our algorithm is bounded by (5/2−3/k) times the optimal value. Our result improves the previously known bound (4−6/k) of the approximation ratio.     

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.     

Triangle-free partial graphs and edge covering theorems

In section 1 some lower bounds are given for the maximal number of edges ofa (p ? 1)- colorable partial graph. Among others we show that a graph on n vertices with m edges has a (p?1)-colorable partial graph with at least mT_n.p/(ⁿ₂) edges, where T_n.p denotes the so called Turán number. These results are used to obtain upper bounds for special edge covering numbers of graphs. In Section 2 we prove the following theorem: If G is a simple graph and μ is the maximal cardinality of a triangle-free edge set of G, then the edges of G can be covered by μ triangles and edges. In Section 3 related questions are examined.     

Some Results on Weighted Graphs without Induced Cycles of Nonpositive Weights

Let G be a simple graph; assume that a mapping assigns integers as weights to the edges of G such that for each induced subgraph that is a cycle, the sum of all weights assigned to its edges is positive; let σ be the sum of weights of all edges of G. It has been proved (Vijayakumar, Discrete Math 311(14):1385–1387, 2011) that (1) if G is 2-connected and the weight of each edge is not more than 1, then σ is positive. It has been conjectured (Xu, Discrete Math 309(4):1007–1012, 2009) that (2) if the minimum degree of G is 3 and the weight of each edge is ±1, then σ > 0. In this article, we prove a generalization of (1) and using this, we settle a vast generalization of (2).     

Bounds for the number of meeting edges in graph partitioning

Let G be a weighted hypergraph with edges of size at most 2. Bollobás and Scott conjectured that G admits a bipartition such that each vertex class meets edges of total weight at least (w ₁?Δ₁)/2+2w ₂/3, where wi is the total weight of edges of size i and Δ₁ is the maximum weight of an edge of size 1. In this paper, for positive integer weighted hypergraph G (i.e., multi-hypergraph), we show that there exists a bipartition of G such that each vertex class meets edges of total weight at least (w ₀?1)/6+(w ₁?Δ₁)/3+2w ₂/3, where w ₀ is the number of edges of size 1. This generalizes a result of Haslegrave. Based on this result, we show that every graph with m edges, except for K ₂ and K _1,3, admits a tripartition such that each vertex class meets at least [2m/5] edges, which establishes a special case of a more general conjecture of Bollobás and Scott.     

On the complexity of testing membership in the core of min-cost spanning tree games

LetN = {1,...,n} be a finite set of players andK _N the complete graph on the node setN∪{0}. Assume that the edges ofK _N have nonnegative weights and associate with each coalitionS∪N of players as costc(S) the weight of a minimal spanning tree on the node setS∪{0}. Using transformation from EXACT COVER BY 3-SETS, we exhibit the following problem to beNP-complete. Given the vectorxε?^itN withx(N) =c(N). decide whether there exists a coalitionS such thatx(S) >c(S).     

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 vertex symmetric digraphs

The problem of how “near” we can come to a n-coloring of a given graph is investigated. I.e., what is the minimum possible number of edges joining equicolored vertices if we color the vertices of a given graph with n colors. In its generality the problem of finding such an optimal color assignment to the vertices (given the graph and the number of colors) is NP-complete. For each graph G, however, colors can be assigned to the vertices in such a way that the number of offending edges is less than the total number of edges divided by the number of colors. Furthermore, an Ω(epn) deterministic algorithm for finding such an n-color assignment is exhibited where e is the number of edges and p is the number of vertices of the graph (e?p?n). A priori solutions for the minimal number of offending edges are given for complete graphs; similarly for equicolored K_m in K_p and equicolored graphs in K_p.     

Improving multicut in directed trees by upgrading nodes

In this paper, we consider the network improvement problem for multicut by upgrading nodes in a directed tree T = (V, E) with multiple sources and multiple terminals. In a node based upgrading model, a node v can be upgraded at the expense of c(v) and such an upgrade reduces weights on all edges incident to v. The objective is to upgrade a minimum cost subset S ⊆ V of nodes such that the resulting network has a multicut in which no edge has weight larger than a given value D. We first obtain a minimum cardinality node multicut V_c for tree T, then find the minimum cost upgrading set based on the upgrading sets for the subtrees rooted at the nodes in V_c. We show that our algorithm is polynomial when the number of source–terminal pairs is upper bounded by a given value.     

Large dense neighbourhoods and turán's theorem

Let t_r(n) denote the number of edges in the complete r-partite graph on n vertices whose colour classes are as equal in size as possible. It is proved that if G is a simple graph on n vertices and more than t_r(n) edges, and if v is any vertex of maximum degree m in G, then the subgraph of G induced by the neighbours of v has more than t_r?1(m) edges. Examples are given to demonstrate the sharpness of this theorem, and its algorithmic implications are noted.     

Edges without crossings in drawings of complete graphs

In drawings (two edges have at most one point in common, either a node or a crossing) of the complete graph K_n in the Euclidean plane there occur at most 2n ? 2 edges without crossings. This was proved by G. Ringel in [1]. Here the minimal number of edges without crossings in drawings of K_n is determined, and for the existence of values between minimum and maximum is asked.     

Multicolored parallelisms of Hamiltonian cycles

A subgraph in an edge-colored graph is multicolored if all its edges receive distinct colors. In this paper, we prove that a complete graph on 2m+1 vertices K_2m+1 can be properly edge-colored with 2m+1 colors in such a way that the edges of K_2m+1 can be partitioned into m multicolored Hamiltonian cycles.