Phase transitions in graphs on orientable surfaces

Let be the orientable surface of genus and denote by the class of all graphs on vertex set with edges embeddable on . We prove that the component structure of a graph chosen uniformly at random from features two phase transitions. The first phase transition mirrors the classical phase transition in the Erd?s‐Rényi random graph chosen uniformly at random from all graphs with vertex set and edges. It takes place at , when the giant component emerges. The second phase transition occurs at , when the giant component covers almost all vertices of the graph. This kind of phenomenon is strikingly different from and has only been observed for graphs on surfaces.     

The genus distributions for a certain type of permutation graphs in orientable surfaces

A circuit is a connected nontrivial 2-regular graph.A graph G is a permutation graph over a circuit C,if G can be obtained from two copies of C by joining these two copies with a perfect matching.In this paper,based on the joint tree method introduced by Liu,the genus polynomials for a certain type of permutation graphs in orientable surfaces are given.     

Long cycles in 3‐connected graphs in orientable surfaces

In this article, we apply a cutting theorem of Thomassen to show that there is a function f: N → N such that if G is a 3‐connected graph on n vertices which can be embedded in the orientable surface of genus g with face‐width at least f(g), then G contains a cycle of length at least cn, where c is a constant not dependent on g. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 69–84, 2002     

A polynomial algorithm for the max-cut problem on graphs without long odd cycles

Given a graphG=[V, E] with positive edge weights, the max-cut problem is to find a cut inG such that the sum of the weights of the edges of this cut is as large as possible. Letg(K) be the class of graphs whose longest odd cycle is not longer than2K+1, whereK is a nonnegative integer independent of the numbern of nodes ofG. We present an O(n ^4K) algorithm for the max-cut problem for graphs ing(K). The algorithm is recursive and is based on some properties of longest and longest odd cycles of graphs. This research was supported by National Science Foundation Grant ECS-8005350 to Cornell University.     

Quadratic Upper Bounds on the Erdős–Pósa Property for a Generalization of Packing and Covering Cycles

According to the classical Erd?s–Pósa theorem, given a positive integer k, every graph G either contains k vertex disjoint cycles or a set of at most vertices that hits all its cycles. Robertson and Seymour (J Comb Theory Ser B 41 (1986), 92–114) generalized this result in the best possible way. More specifically, they showed that if is the class of all graphs that can be contracted to a fixed planar graph H, then every graph G either contains a set of k vertex‐disjoint subgraphs of G, such that each of these subgraphs is isomorphic to some graph in or there exists a set S of at most vertices such that contains no subgraph isomorphic to any graph in . However, the function f is exponential. In this note, we prove that this function becomes quadratic when consists all graphs that can be contracted to a fixed planar graph . For a fixed c, is the graph with two vertices and parallel edges. Observe that for this corresponds to the classical Erd?s–Pósa theorem.     

The ratio of the numbers of odd and even cycles in outerplanar graphs

In this paper, we investigate the ratio of the numbers of odd and even cycles in outerplanar graphs. We verify that the ratio generally diverges to infinity as the order of a graph diverges to infinity. We also give sharp estimations of the ratio for several classes of outerplanar graphs, and obtain a constant upper bound of the ratio for some of them. Furthermore, we consider similar problems in graphs with some pairs of forbidden subgraphs/minors, and propose a challenging problem concerning claw-free graphs.     

The mean value property for harmonic functions on graphs and trees

Following the Euclidean example, we introduce the strong and weak mean value property for finite variation measures on graphs. We completely characterize finite variation measures with bounded support on radial trees which have the strong mean value property. We show that for counting measures on bounded subsets of a tree with root o, the strong mean value property is equivalent to the invariance of the subset under the action of the stabilizer of o in the automorphism group. We finally characterize, using the discrete Laplacian, the finite variation measures on a generic graph which have the weak mean value property and we give a non-trivial example. Received: July 21, 2000; in final form: March 13, 2001?Published online: March 19, 2002