Cutting up graphs

LetΓ be infinite connected graph with more than one end. It is shown that there is a subsetd ⊂V Γ which has the following properties. (i) Bothd andd*=VΓ\d are infinite. (ii) there are only finitely many edges joiningd andd*. (iii) For eachgε AutΓ at least one ofd⊂dg, d*⊂dg, d⊂d* g, d*⊂d* g holds. Any group acting on Γ has a decomposition as a free product with amalgamation or as an HNN-group.     

Number of minimum vertex cuts in transitive graphs

Let G be a k-regular vertex transitive graph with connectivity κ(G)=k and let m_k(G) be the number of vertex cuts with k vertices. Define m(n,k)=min{m_k(G): GT_n,k}, where T_n,k denotes the set of all k-regular vertex transitive graphs on n vertices with κ(G)=k. In this paper, we determine the exact values of m(n,k).     

A note on packing paths in planar graphs

Seymour (1981) proved that the cut criterion is necessary and sufficient for the solvability of the edge-disjoint paths problem when the union of the supply graph and the demand graph is planar and Eulerian. When only planarity is required, Middendorf and Pfeiffer (1993) proved the problem to be NP-complete. For this case, Korach and Penn (1992) proved that the cut criterion is sufficient for the existence of a near-complete packing of paths. Here we generalize this result by showing how a natural strengthening of the cut criterion yields better packings of paths.Analogously to Seymour's approach, we actually prove a theorem on packing cuts in an arbitrary graph and then the planar edge-disjoint paths case is obtained by planar dualization. The main result is derived from a theorem of Seb (1990) on the structure of ±1 weightings of a bipartite graph with no negative circuits.Research partially supported by the Hungarian National Foundation for Scientific Research Grants OTKA 2118 and 4271.     

Cutting numbers in graphs

The cutting number of a point of a connected graph is a measure of the extent to which the removal of that point cuts the graph. The cutting center of the graph is the set of points of maximal cutting number. In an earlier paper [1] all possible structures for the cutting center of a tree were determined and examples constructed which realize them. In this paper we extend those results to all graphs.     

On mixed-integer sets with two integer variables

We show that every facet-defining inequality of the convex hull of a mixed-integer polyhedral set with two integer variables is a crooked cross cut (which we defined in 2010). We extend this result to show that crooked cross cuts give the convex hull of mixed-integer sets with more integer variables if the coefficients of the integer variables form a matrix of rank 2. We also present an alternative characterization of the crooked cross cut closure of mixed-integer sets similar to the one on the equivalence of different definitions of split cuts presented in Cook et al. (1990) [4]. This characterization implies that crooked cross cuts dominate the 2-branch split cuts defined by Li and Richard (2008) [8]. Finally, we extend our results to mixed-integer sets that are defined as the set of points (with some components being integral) inside a closed, bounded and convex set.     

Multiple Cuts with a Homogeneous Analytic Center Cutting Plane Method

This paper analyzes the introduction of multiple central cuts in a conic formulation of the analytic center cutting plane method (in short ACCPM). This work extends earlier work on the homogeneous ACCPM, and parallels the analysis of the multiple cut process in the standard ACCPM. The main issue is the calculation of a direction that restores feasibility after introducing p new cutting planes at the query point. We prove that the new analytic center can be recovered in O(p log p) damped Newton iterations, where is a parameter depending of the data. We also present two special cases where the complexity can be decreased to O (p log p). Finally, we show that the number of calls to the oracle is the same as in the single cut case, up to a factor .     

On distance two graphs of upper bound graphs

For a poset P=(X,≤), the upper bound graph (UB-graph) of P is the graph U=(X,E_U), where uv∈E_U if and only if u≠v and there exists m∈X such that u,v≤m. For a graph G, the distance two graph DS₂(G) is the graph with vertex set V(DS₂(G))=V(G) and u,v∈V(DS₂(G)) are adjacent if and only if d_G(u,v)=2. In this paper, we deal with distance two graphs of upper bound graphs. We obtain a characterization of distance two graphs of split upper bound graphs.     

On the max‐cut of sparse random graphs

We consider the problem of estimating the size of a maximum cut (Max‐Cut problem) in a random Erdős‐Rényi graph on n nodes and edges. It is shown in Coppersmith et al. that the size of the maximum cut in this graph normalized by the number of nodes belongs to the asymptotic region with high probability (w.h.p.) as n increases, for all sufficiently large c. The upper bound was obtained by application of the first moment method, and the lower bound was obtained by constructing algorithmically a cut which achieves the stated lower bound. In this paper, we improve both upper and lower bounds by introducing a novel bounding technique. Specifically, we establish that the size of the maximum cut normalized by the number of nodes belongs to the interval w.h.p. as n increases, for all sufficiently large c. Instead of considering the expected number of cuts achieving a particular value as is done in the application of the first moment method, we observe that every maximum size cut satisfies a certain local optimality property, and we compute the expected number of cuts with a given value satisfying this local optimality property. Estimating this expectation amounts to solving a rather involved two dimensional large deviations problem. We solve this underlying large deviation problem asymptotically as c increases and use it to obtain an improved upper bound on the Max‐Cut value. The lower bound is obtained by application of the second moment method, coupled with the same local optimality constraint, and is shown to work up to the stated lower bound value . It is worth noting that both bounds are stronger than the ones obtained by standard first and second moment methods. Finally, we also obtain an improved lower bound of on the Max‐Cut for the random cubic graph or any cubic graph with large girth, improving the previous best bound of .     

Cutting and Surrogate Constraint Analysis for Improved Multidimensional Knapsack Solutions

We use surrogate analysis and constraint pairing in multidimensional knapsack problems to fix some variables to zero and to separate the rest into two groups – those that tend to be zero and those that tend to be one, in an optimal integer solution. Using an initial feasible integer solution, we generate logic cuts based on our analysis before solving the problem with branch and bound. Computational testing, including the set of problems in the OR-library and our own set of difficult problems, shows our approach helps to solve difficult problems in a reasonable amount of time and, in most cases, with a fewer number of nodes in the search tree than leading commercial software.     

Sparse connectivity certificates via MA orderings in graphs

For an undirected multigraph G=(V,E), let α be a positive integer weight function on V. For a positive integer k, G is called (k,α)-connected if any two vertices u,v∈V remain connected after removal of any pair (Z,E^′) of a vertex subset Z⊆V-{u,v} and an edge subset E^′⊆E such that ∑_v∈Zα(v)+|E^′|<k. The (k,α)-connectivity is an extension of several common generalizations of edge-connectivity and vertex-connectivity. Given a (k,α)-connected graph G, we show that a (k,α)-connected spanning subgraph of G with O(k|V|) edges can be found in linear time by using MA orderings. We also show that properties on removal cycles and preservation of minimum cuts can be extended in the (k,α)-connectivity.     

Cutting planes for integer programs with general integer variables

We investigate the use of cutting planes for integer programs with general integer variables. We show how cutting planes arising from knapsack inequalities can be generated and lifted as in the case of 0–1 variables. We also explore the use of Gomory's mixed-integer cuts. We address both theoretical and computational issues and show how to embed these cutting planes in a branch-and-bound framework. We compare results obtained by using our cut generation routines in two existing systems with a commercially available branch-and-bound code on a range of test problems arising from practical applications. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Corresponding author.This research was partly performed when the author was affiliated with CORE, Université Catholique de Louvain.     

Geodetic graphs of diameter two

We survey what is known on geodetic graphs of diameter two and discuss the implications of a new strong necessary condition for the existence of such graphs.     

Pentavalent vertex-transitive diameter two graphs

We classify the family of pentavalent vertex-transitive graphs Γ with diameter 2. Suppose that the automorphism group of Γ is transitive on the set of ordered distance 2 vertex pairs. Then we show that either Γ is distance-transitive or Γ is one of \(\overline {{C_8}} ,{\kern 1pt} {K_5}\square {K_2},{\kern 1pt} {C_5}\left[ {{K_2}} \right],{\kern 1pt} \overline {2{C_4}} ,{\kern 1pt} or{\kern 1pt} {K_3}\square {K_4}\).     

Reduced graphs of diameter two

A graph H is collapsible if for every subset X ? V(H), H has a spanning connected subgraph whose set of odd-degree vertices is X. In any graph G there is a unique collection of maximal collapsible subgraphs, and when all of them are contracted, the resulting contraction of G is a reduced graph. Interest in reduced graphs arises from the fact [4] that a graph G has a spanning closed trail if and only if its corresponding reduced graph has a spanning closed trail. The concept can also be applied to study hamiltonian line graphs [11] or double cycle covers [8]. In this article, we characterize the reduced graphs of diameter two. As applications, we obtain prior results in [12] and [14], and show that every 2-edge-connected graph with diameter at most two either admits a double cycle cover with three even subgraphs or is isomorphic to the Petersen graph.     

f-Class two graphs whose f-cores have maximum degree two

An f-coloring of a graph G is an edge-coloring of G such that each color appears at each vertex v∈V(G) at most f(v) times.The f-core of G is the subgraph of G induced by the vertices v of degree d(v)=f(v) maxv∈V(G){ d(v)/f(v) }.In this paper,we find some necessary conditions for a simple graph,whose f-core has maximum degree two,to be of class 2 for f-colorings.     

Cubic graphs with crossing number two

It is proved that every cubic graph with crossing number at least two contains a subdivision of one of eight graphs.     

On the corona of two graphs

Aequationes mathematicae -