Great-circle tree thrackles

A thrackle is a graph drawing in which every pair of edges meets exactly once. Conway's Thrackle Conjecture states that the number of edges of a thrackle cannot exceed the number of its vertices. Cairns et al. (2015) [1] prove that the Thrackle Conjecture holds for great-circle thrackles drawn on the sphere. They also posit that Conway's Thrackle Conjecture can be restated to say that a graph can be drawn as a thrackle drawing in the plane if and only if it admits a great-circle thrackle drawing. We demonstrate that the class of great-circle thrackleable graphs excludes some trees. Thus the informal conjecture from Cairns et al. (2015) [1] is not equivalent to the Thrackle Conjecture.     

Bounds for Generalized Thrackles

A thrackle (resp. generalized thrackle) is a drawing of a graph in which each pair of edges meets precisely once (resp. an odd number of times). For a graph with n vertices and m edges, we show that, for drawings in the plane, m≤ (2/3)(n-1) for thrackles, while m≤ 2n-2 for generalized thrackles. This improves theorems of Lovász, Pach, and Szegedy. The paper also examines thrackles in the more general setting of drawings on closed surfaces. The main result is: a bipartite graph G can be drawn as a generalized thrackle on a closed orientable connected surface if and only if G can be embedded in that surface. Received July 23, 1998, and in revised form January 1, 1999.     

Applying a proof of tverberg to complete bipartite decompositions of digraphs and multigraphs

Graham and Pollak [2] proved that n – 1 is the minimum number of edge-disjoint complete bipartite subgraphs into which the edges of K_n decompose. Tverberg [6], using a linear algebraic technique, was the first to give a simple proof of this result. We apply Tverberg's technique to obtain results for two related decomposition problems, in which we wish to partition the arcs/edges of complete digraphs/multigraphs into a minimum number of arc/edge-disjoint complete bipartite subgraphs of appropriate natures. We obtain exact results for the digraph problem, which was posed by Lundgren and Maybee [4]. We also obtain exact results for the decomposition of complete multigraphs with exactly two edges connecting every pair of distinct vertices.     

Feasibility of the Mixed Postman Problem with Restrictions on the Edges

The mixed postman problem consists of finding a minimum cost tour of a connected mixed graph traversing all its vertices, edges, and arcs at least once. We consider the variant of the mixed postman problem where all edges must be traversed exactly once. The feasibility version of this problem is NP-complete. We introduce an infinite class of necessary conditions for feasibility, which we conjecture are also sufficient. We prove that no finite subset of these conditions is sufficient.     

Generalized Thrackle Drawings of Non-bipartite Graphs

A graph drawing is called a generalized thrackle if every pair of edges meets an odd number of times. In a previous paper, we showed that a bipartite graph G can be drawn as a generalized thrackle on an oriented closed surface M if and only if G can be embedded in M. In this paper, we use Lins’ notion of a parity embedding and show that a non-bipartite graph can be drawn as a generalized thrackle on an oriented closed surface M if and only if there is a parity embedding of G in a closed non-orientable surface of Euler characteristic χ(M)−1. As a corollary, we prove a sharp upper bound for the number of edges of a simple generalized thrackle.     

Change graphs of edge-colorings of planar cubic graphs

It will be proved that the number of vertices of each component of the change-graph of two edge-colorings of an arbitrary planar cubic graph is even (here a change-graph is the subgraph containing exactly those edges having different colors in the considered two edge-colorings and moreover only those vertices which are incident with at least one of these edges).     

Edge coloring of hypergraphs and a conjecture of ErdÖs,Faber, Lovász

Call a bypergraphsimple if for any pairu, v of distinct vertices, there is at most one edge incident to bothu andv, and there are no edges incident to exactly one vertex. A conjecture of Erds, Faber and Lovász is equivalent to the statement that the edges of any simple hypergraph onn vertices can be colored with at mostn colors. We present a simple proof that the edges of a simple hypergraph onn vertices can be colored with at most [1.5n-2 colors].This research was partially supported by N.S.F. grant No. MCS-8311422.     

Outerplanar Thrackles

We show that a graph drawing is an outerplanar thrackle if and only if, up to an inversion in the plane, it is Reidemeister equivalent to an odd musquash. This establishes Conway’s thrackle conjecture for outerplanar thrackles. We also extend this result in two directions. First, we show that no pair of vertices of an outerplanar thrackle can be joined by an edge in such a way that the resulting graph drawing is a thrackle. Secondly, we introduce the notion of crossing rank; drawings with crossing rank 0 are generalizations of outerplanar drawings. We show that all thrackles of crossing rank 0 are outerplanar. We also introduce the notion of an alternating cycle drawing, and we show that a thrackled cycle is alternating if and only if it is outerplanar.     

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.     

Drawing planar graphs with circular arcs

In this paper we address the problem of drawing planar graphs with circular arcs while maintaining good angular resolution and small drawing area. We present a lower bound on the area of drawings in which edges are drawn using exactly one circular arc. We also give an algorithm for drawing n -vertex planar graphs such that the edges are sequences of two continuous circular arcs. The algorithm runs in O(n) time and embeds the graph on the O(n)\times O(n) grid, while maintaining Θ(1/d(v)) angular resolution, where d(v) is the degree of vertex v . Since in this case we use circular arcs of infinite radius, this is also the first algorithm that simultaneously achieves good angular resolution, small area, and at most one bend per edge using straight-line segments. Finally, we show how to create drawings in which edges are smooth C ¹ -continuous curves, represented by a sequence of at most three circular arcs. Received September 30, 1999, and in revised form March 27, 2000. Online publication October 26, 2000.     

Graphs With 3n−6 Edges Not Containing A Subdivision Of K 5

We determine all graphs on n ≥ 3 vertices with 3n-6 edges which do not contain a subdivision of K₅. These are exactly the graphs which one gets from any number of disjoint maximal planar graphs by successively pasting along triangles.     

Degenerate Crossing Numbers

Let G be a graph with n vertices and e≥4n edges, drawn in the plane in such a way that if two or more edges (arcs) share an interior point p, then they properly cross one another at p. It is shown that the number of crossing points, counted without multiplicity, is at least constant times e and that the order of magnitude of this bound cannot be improved. If, in addition, two edges are allowed to cross only at most once, then the number of crossing points must exceed constant times (e/n)⁴. The research of J. Pach was supported by NSF grant CCF-05-14079 and by grants from NSA, PSC-CUNY, BSF, and OTKA-K-60427. The research of G. Tóth was supported by OTKA-K-60427.     

On critical graphs with chromatic index 4

It is shown that the number of vertices of valency 2 in a critical graph with chromatic index 4 is at most 1/3 of the total number of vertices, and that there exist critical graphs with just one vertex of valency 2, but none with exactly two vertices of valency 2. From this bounds for the number of edges are deduced. The paper ends with a presentation of a catalogue of all critical graphs with chromatic index 4 and at most 8 vertices, and all simple critical graphs with chromatic index 4 and at most 10 vertices.     

Score certificates for tournaments

The score of a vertex in a tournament is its out-degree. A score certificate for a labeled tournament T is a labeled subdigraph D of T which together with the score sequence of T allows errorless reconstruction of T. In this paper we prove a general lower bound on the sizes of score certificates. Our main theorem can be stated as follows: Except for the regular tournaments on 3 and 5 vertices, every tournament T on n vertices requires at least n−1 arcs in a score certificate for T. This is best possible since every transitive tournament on n vertices has a score certificate with exactly n−1 arcs. © 1997 John Wiley & Sons, Inc.     

Contractions to k8

It is proved that the maximal number of edges in a graph with n ≧ 8 vertices that is not contractible to K₈ is 6n ? 21, unless 5 divides n, and the only graphs with n = 5m vertices and more than 6n ? 21 edges that are not contractible to K₈ are the K₅(2)-cockades that have exactly 6n ? 20 edges.     

Phase transition of the minimum degree random multigraph process

We study the phase transition of the minimum degree multigraph process. We prove that for a constant h_g ≈︁ 0.8607, with probability tending to 1 as n → ∞, the graph consists of small components on O(log n) vertices when the number of edges of a graph generated so far is smaller than h_gn, the largest component has order roughly n^2/3 when the number of edges added is exactly h_gn, and the graph consists of one giant component on Θ(n) vertices and small components on O(log n) vertices when the number of edges added is larger than h_gn. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

A generalization of the circumcircle theorem

The theorem relating the bisectors of the edges of a triangle and the corresponding circumscribing circle is established as a special case of a theorem for triangles with weighted vertices where the edges are partitioned with circular arcs in the proportions of the weights. The circular arcs are established as being uniquely determined by the weights and the triangle, and are given by three circles with collinear centres. These circles either intersect in zero, one or two real points, these latter points being the triple points.     

Graphs with equal eternal vertex cover and eternal domination numbers

Mobile guards on the vertices of a graph are used to defend it against an infinite sequence of attacks on either its vertices or its edges. If attacks occur at vertices, this is known at the eternal domination problem. If attacks occur at edges, this is known as the eternal vertex cover problem. We focus on the model in which all guards can move to neighboring vertices in response to an attack. Motivated by the question of which graphs have equal eternal vertex cover and eternal domination numbers, a number of results are presented; one of the main results of the paper is that the eternal vertex cover number is greater than the eternal domination number (in the all-guards move model) in all graphs of minimum degree at least two.     

An Extremal Problem on Contractible Edges in 3-Connected Graphs

An edge e in a 3-connected graph G is contractible if the contraction G/e is still 3-connected. The existence of contractible edges is a very useful induction tool. Let G be a simple 3-connected graph with at least five vertices. Wu [7] proved that G has at most vertices that are not incident to contractible edges. In this paper, we characterize all simple 3-connected graphs with exactly vertices that are not incident to contractible edges. We show that all such graphs can be constructed from either a single vertex or a 3-edge-connected graph (multiple edges are allowed, but loops are not allowed) by a simple graph operation. Research partially supported by an ONR grant under grant number N00014-01-1-0917     

Expected numbers at hitting times

We determine exactly the expected number of hamilton cycles in the random graph obtained by starting with n isolated vertices and adding edges at random until each vertex degree is at least two. This complements recent work of Cooper and Frieze. There are similar results concerning expected numbers, for example, of perfect matchings, spanning trees, hamilton paths, and directed hamilton cycles.