Regular pseudo-median graphs

A graph is pseudo-median if for every triple u, v, w of vertices there exists either a unique vertex between each pair of them (if their mutual distances sum up to an even number) or a unique triangle whose edges lie between the three pairs of u, v, w, respectively (if the distance sum is odd). We show that a finite pseudo-median graph is regular if and only if it is the Cartesian product of a hypercube with either a complete graph or a hyper-octahedron. Every self-map of a pseudo-median graph that preserves or collapses edges has an invariant regular pseudo-median subgraph. Furthermore, the set of all vertices minimizing the total distance to the vertices of a pseudo-median graph induces a regular pseudo-median subgraph.     

Rectangular drawings of plane graphs without designated corners

This paper addresses the problem of finding rectangular drawings of plane graphs, in which each vertex is drawn as a point, each edge is drawn as a horizontal or a vertical line segment, and the contour of each face is drawn as a rectangle. A graph is a 2–3 plane graph if it is a plane graph and each vertex has degree 3 except the vertices on the outer face which have degree 2 or 3. A necessary and sufficient condition for the existence of a rectangular drawing has been known only for the case where exactly four vertices of degree 2 on the outer face are designated as corners in a 2–3 plane graph G. In this paper we establish a necessary and sufficient condition for the existence of a rectangular drawing of G for the general case in which no vertices are designated as corners. We also give a linear-time algorithm to find a rectangular drawing of G if it exists.     

A local structure theorem on 5‐connected graphs

An edge of a 5‐connected graph is said to be contractible if the contraction of the edge results in a 5‐connected graph. Let x be a vertex of a 5‐connected graph. We prove that if there are no contractible edges whose distance from x is two or less, then either there are two triangles with x in common each of which has a distinct degree five vertex other than x, or there is a specified structure called a K₄^?‐configuration with center x. As a corollary, we show that if a 5‐connected graph on n vertices has no contractible edges, then it has 2n/5 vertices of degree 5. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 99–129, 2009     

A Metric of Constant Curvature on Polycycles

We prove the following main theorem of the theory of (r, q)-polycycles. Suppose a nonseparable plane graph satisfies the following two conditions:(1) each internal face is an r-gon, where r ≥ 3;(2) the degree of each internal vertex is q, where q ≥ 3, and the degree of each boundary vertex is at most q and at least 2.Then it also possesses the following third property:(3) the vertices, the edges, and the internal faces form a cell complex.Simple examples show that conditions (1) and (2) are independent even provided condition (3) is satisfied. These are the defining conditions for an (r, q)-polycycle.__________Translated from Matematicheskie Zametki, vol. 78, no. 2, 2005, pp. 223–233.Original Russian Text Copyright © 2005 by M. Deza, M. I. Shtogrin.     

A fast algorithm for equitable coloring

A proper vertex coloring of a graph is equitable if the sizes of color classes differ by at most one. The celebrated Hajnal-Szemerédi Theorem states: For every positive integer r, every graph with maximum degree at most r has an equitable coloring with r+1 colors. We show that this coloring can be obtained in O(rn ²) time, where n is the number of vertices.     

Fragile graphs with small independent cuts

A graph is called fragile if it has a vertex cut which is also an independent set. Chen and Yu proved that every graph with n vertices and at most 2n?4 edges is fragile, which was conjectured to be true by Caro. However, their proof does not give any information on the number of vertices in the independent cuts. The purpose of this paper is to investigate when a graph has a small independent cut. We show that if G is a graph on n vertices and at most (12n/7)?3 edges, then G contains an independent cut S with ∣S∣≤3. Upper bounds on the number of edges of a graph having an independent cut of size 1 or 2 are also obtained. We also show that for any positive integer k, there is a positive number ε such that there are infinitely many graphs G with n vertices and at most (2?ε)n edges, but G has no independent cut with less than k vertices. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 327–341, 2002     

Enumeration of Unrooted Odd-Valent Regular Planar Maps

We derive closed formulae for the numbers of rooted maps with a fixed number of vertices of the same odd degree except for the root vertex and one other exceptional vertex of degree 1. The same applies to the generating functions for these numbers. Similar results, but without the vertex of degree 1, were obtained by the first author and Rahman. We also show, by manipulating a recursion of Bouttier, Di Francesco and Guitter, that there are closed formulae when the exceptional vertex has arbitrary degree. We combine these formulae with results of the second author to count unrooted regular maps of odd degree. In this way we obtain, for each even n, a closed formula for the function f _n whose value at odd positive integers r is the number of unrooted maps (up to orientation-preserving homeomorphisms) with n vertices and degree r. The formula for f _n becomes more cumbersome as n increases, but for n > 2 each has a bounded number of terms independent of r.     

Subdivisions of Transitive Tournaments

We prove that, for r ≥ 2 andn ≥ n(r), every directed graph with n vertices and more edges than the r -partite Turán graph T(r, n) contains a subdivision of the transitive tournament on r + 1 vertices. Furthermore, the extremal graphs are the orientations ofT (r, n) induced by orderings of the vertex classes.     

Box-Rectangular Drawings of Plane Graphs

In this paper we introduce a new drawing style of a plane graph G called a box-rectangular drawing. It is defined to be a drawing of G on an integer grid such that every vertex is drawn as a rectangle, called a box, each edge is drawn as either a horizontal line segment or a vertical line segment, and the contour of each face is drawn as a rectangle. We establish a necessary and sufficient condition for the existence of a box-rectangular drawing of G. We also give a linear-time algorithm to find a box-rectangular drawing of G if it exists.     

On induced subgraphs of a block

If G is a block, then a vertex u of G is called critical if G - u is not a block. In this article, relationships between the localization of critical vertices and the localization of vertices of relatively small degrees (especially, of degree two) are studied. A block is called semicritical if a) each edge is incident with at least one critical vertex and b) each vertex of degree two is critical. Let G be a semicritical block with at least six vertices. It is proved that A) there exist distinct vertices u₂, v₁, u₂, and v₂ of degree two in G such that u₁v₁ and u₂v₂ are edges of G, and u₁v₂, and u₂v₂ are edges of the complement of G, and B) the complement of G is a block with no critical vertex of degree two.     

The negative cycles polyhedron and hardness of checking some polyhedral properties

Given a graph G=(V,E) and a weight function on the edges w:E→ℝ, we consider the polyhedron P(G,w) of negative-weight flows on G, and get a complete characterization of the vertices and extreme directions of P(G,w). Based on this characterization, and using a construction developed in Khachiyan et al. (Discrete Comput. Geom. 39(1–3):174–190, 2008), we show that, unless P=NP, there is no output polynomial-time algorithm to generate all the vertices of a 0/1-polyhedron. This strengthens the NP-hardness result of Khachiyan et al. (Discrete Comput. Geom. 39(1–3):174–190, 2008) for non 0/1-polyhedra, and comes in contrast with the polynomiality of vertex enumeration for 0/1-polytopes (Bussiech and Lübbecke in Comput. Geom., Theory Appl. 11(2):103–109, 1998). As further applications, we show that it is NP-hard to check if a given integral polyhedron is 0/1, or if a given polyhedron is half-integral. Finally, we also show that it is NP-hard to approximate the maximum support of a vertex of a polyhedron in ℝ ⁿ within a factor of 12/n.     

Competing first passage percolation on random graphs with finite variance degrees

We study the growth of two competing infection types on graphs generated by the configuration model with a given degree sequence. Starting from two vertices chosen uniformly at random, the infection types spread via the edges in the graph in that an uninfected vertex becomes type 1 (2) infected at rate λ₁ (λ₂) times the number of nearest neighbors of type 1 (2). Assuming (essentially) that the degree of a randomly chosen vertex has finite second moment, we show that if λ₁ = λ₂, then the fraction of vertices that are ultimately infected by type 1 converges to a continuous random variable V ∈ (0,1), as the number of vertices tends to infinity. Both infection types hence occupy a positive (random) fraction of the vertices. If λ₁ ≠ λ₂, on the other hand, then the type with the larger intensity occupies all but a vanishing fraction of the vertices. Our results apply also to a uniformly chosen simple graph with the given degree sequence.     

Intersection graphs of proper subtrees of unicyclic graphs

A graph is fraternally oriented iff for every three vertices u, ν, w the existence of the edges u → w and ν → w implies that u and ν are adjacent. A directed unicyclic graph is obtained from a unicyclic graph by orienting the unique cycle clockwise and by orienting the appended subtrees from the cycle outwardly. Two directed subtrees s, t of a directed unicyclic graph are proper if their union contains no (directed or undirected) cycle and either they are disjoint or one of them s has its root r(s) in t and contains all the successors of r(s) in t. In the present paper we prove that G is an intersection graph of a family of proper directed subtrees of a directed unicyclic graph iff it has a fraternal orientation such that for every vertex ν, G(Γⁱⁿν) is acyclic and G(Γ^outν) is the transitive closure of a tree. We describe efficient algorithms for recognizing when such graphs are perfect and for testing isomorphism of proper circular-arc graphs.     

Signed graph factors and degree sequences

For a signed graph G and function , a signed f‐factor of G is a spanning subgraph F such that sdeg_F(υ) = f(υ) for every vertex υ of G, where sdeg(υ) is the number of positive edges incident with v less the number of negative edges incident with υ, with loops counting twice in either case. For a given vertex‐function f, we provide necessary and sufficient conditions for a signed graph G to have a signed f‐factor. As a consequence of this result, an Erd?s‐Gallai‐type result is given for a sequence of integers to be the degree sequence of a signed r‐graph, the graph with at most r positive and r negative edges between a given pair of distinct vertices. We discuss how the theory can be altered when mixed edges (i.e., edges with one positive and one negative end) are allowed, and how it applies to bidirected graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 27–36, 2006     

Path covers of weighted graphs

Let (G, w) denote a simple graph G with a weight function w : E(G) ← {0, 1, 2}. A path cover of (G, w) is a collection of paths in G such that every edge e is contained in exactly w(e) paths of the collection. For a vertex v, w(v) is the sum of the weights of the edges incident with v; v is called an odd (even) vertex if w(v) is odd (even). We prove that if every vertex of (G, w) is incident with at most one edge of weight 2, then (G, w) has a path cover P such that each odd vertex occurs exactly once, and each even vertex exactly twice, as an end of a path of P. We also prove that if every vertex of (G, w) is even, then (G, w) has a path cover P such that each vertex occurs exactly twice as an end of a path of P. © 1995 John Wiley & Sons, Inc.     

A solitaire game played on 2-colored graphs

We introduce a solitaire game played on a graph. Initially one disk is placed at each vertex, one face green and the other red, oriented with either color facing up. Each move of the game consists of selecting a vertex whose disk shows green, flipping over the disks at neighboring vertices, and deleting the selected vertex. The game is won if all vertices are eliminated. We derive a simple parity-based necessary condition for winnability of a given game instance. By studying graph operations that construct new graphs from old ones, we obtain broad classes of graphs where this condition also suffices, thus characterizing the winnable games on such graphs. Concerning two familiar (but narrow) classes of graphs, we show that for trees a game is winnable if and only if the number of green vertices is odd, and for n-cubes a game is winnable if and only if the number of green vertices is even and not all vertices have the same color. We provide a linear-time algorithm for deciding winnability for games on maximal outerplanar graphs. We reduce the decision problem for winnability of a game on an arbitrary graph G to winnability of games on its blocks, and to winnability on homeomorphic images of G obtained by contracting edges at 2-valent vertices.     

Forcing highly connected subgraphs

A theorem of Mader states that highly connected subgraphs can be forced in finite graphs by assuming a high minimum degree. We extend this result to infinite graphs. Here, it is necessary to require not only high degree for the vertices but also high vertex‐degree (or multiplicity) for the ends of the graph, that is, a large number of disjoint rays in each end. We give a lower bound on the degree of vertices and the vertex‐degree of the ends which is quadratic in k, the connectedness of the desired subgraph. In fact, this is not far from best possible: we exhibit a family of graphs with a degree of order 2^k at the vertices and a vertex‐degree of order k log k at the ends which have no k‐connected subgraphs. Furthermore, if in addition to the high degrees at the vertices, we only require high edge‐degree for the ends (which is defined as the maximum number of edge‐disjoint rays in an end), Mader's theorem does not extend to infinite graphs, not even to locally finite ones. We give a counterexample in this respect. But, assuming a lower bound of at least 2k for the edge‐degree at the ends and the degree at the vertices does suffice to ensure the existence (k + 1)‐edge‐connected subgraphs in arbitrary graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 331–349, 2007     

Cycles through ten vertices in 3-connected cubic graphs

It is known that there exists a cycle through any nine vertices of a 3-connected cubic graphG. Here we show that if an edge is removed from such a graph, then there is still a cycle through any five vertices. Furthermore, we characterise the circumstances in which there fails to be a cycle through six. As corollaries we are able to prove that a 3-connected cubic graph has a cycle through any specified five vertices and one edge, and to classify the conditions under which it has a cycle through four chosen vertices and two edges. We are able to use the five and six vertex results to show that a 3-connected cubic graph has a cycle which passes through any ten given vertices if and only if the graph is not contractible to the Petersen graph in such a way that the ten vertices each map to a distinct vertex of the Petersen graph.     

Antimagic Properties of Graphs with Large Maximum Degree

An antimagic labeling of a graph with m edges and n vertices is a bijection from the set of edges to the integers such that all n vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges incident with the same vertex. A graph is called antimagic if it has an antimagic labeling. In this article, we discuss antimagic properties of graphs that contain vertices of large degree. We also show that graphs with maximum degree at least are antimagic.