Largest planar matching in random bipartite graphs

For a distribution ?? over labeled bipartite (multi) graphs G = (W, M, E), |W| = |M| = n, let L(n) denote the size of the largest planar matching of G (here W and M are posets drawn on the plane as two ordered rows of nodes and edges are drawn as straight lines). We study the asymptotic (in n) behavior of L(n) for different distributions ??. Two interesting instances of this problem are Ulam's longest increasing subsequence problem and the longest common subsequence problem. We focus on the case where ?? is the uniform distribution over the k‐regular bipartite graphs on W and M. For k = o(n^1/4), we establish that $L(n) \slash \sqrt{kn}$ tends to 2 in probability when n → ∞. Convergence in mean is also studied. Furthermore, we show that if each of the n² possible edges between W and M are chosen independently with probability 0 < p < 1, then L(n)/n tends to a constant γ_p in probability and in mean when n → ∞. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 162–181, 2002     

Changes of leadership in a random graph process

Let be a random graph process in which in each step we add to a graph a new edge, chosen at random from all available pairs. Define the leader of G(n, M) as either the unique largest component or, if G(n, M) contains many components of the maximum size, the one from the largest components which emerged first during the process. We show that the longest period between two changes of leaders in the random graph process is, with probability tending to 1 as n →∞, of the order of n/log log n/log n. © 1994 John Wiley & Sons, Inc.     

A Note on Cycle Lengths in Graphs

 We prove that for every c>0 there exists a constant K = K(c) such that every graph G with n vertices and minimum degree at least c n contains a cycle of length t for every even t in the interval [4,e c(G) − K] and every odd t in the interval [K,o c(G) − K], where e c(G) and o c(G) denote the length of the longest even cycle in G and the longest odd cycle in G respectively. We also give a rough estimate of the magnitude of K. Received: July 5, 2000 Final version received: April 17, 2002 2000 Mathematics Subject Classification. 05C38     

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.     

Toughness and longest cycles in 2-connected planar graphs

Let G be a planar graph on n vertices, let c(G) denote the length of a longest cycle of G, and let w(G) denote the number of components of G. By a well-known theorem of Tutte, c(G) = n (i.e., G is hamiltonian) if G is 4-connected. Recently, Jackson and Wormald showed that c(G) ≥ βn^α for some positive constants β and α ≅ 0.2 if G is 3-connected. Now let G have connectivity 2. Then c(G) may be as small as 4, as with K_2,n-2, unless we bound w(G − S) for every subset S of V(G) with |S| = 2. Define ξ(G) as the maximum of w(G − S) taken over all 2-element subsets S ⊆ V(G). We give an asymptotically sharp lower bound for the toughness of G in terms of ξ(G), and we show that c(G) ≥ θ ln n for some positive constant θ depending only on ξ(G). In the proof we use a recent result of Gao and Yu improving Jackson and Wormald's result. Examples show that the lower bound on c(G) is essentially best-possible. © 1996 John Wiley & Sons, Inc.     

On triangle‐free random graphs

We show that for every k≥1 and δ>0 there exists a constant c>0 such that, with probability tending to 1 as n→∞, a graph chosen uniformly at random among all triangle‐free graphs with n vertices and M≥cn^3/2 edges can be made bipartite by deleting ⌊δM⌋ edges. As an immediate consequence of this fact we infer that if M/n^3/2→∞ but M/n²→0, then the probability that a random graph G(n, M) contains no triangles decreases as 2^−(1+o(1))M. We also discuss possible generalizations of the above results. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 16: 260–276, 2000     

Linear maps preserving regional eigenvalue location

Let M(n, C) be the vector space of n × n complex matrices and let G(r,s,t) be the set of all matrices in M(n, C) having r eigenvalues with positive real parts eigenvalues with negative real part and t eigenvalues with zero real part. In particularG(0,n,0) is the set of stable matrices. We investigate the set of linear operators on M(n, C) that map G(r,s,t) into itself. Such maps include, but are not always limited to similarities, transposition, and multiplication by a positive constant. The proof of our results depends on a characterization of nilpotent matrices in terms of matrices in a particular G(r,s,t), and an extension of a result about the existence of a matrix with prescribed eigenstructure and diagonal entries. Each of these results is of independent interest. Moreover, our char-acterization of nilpotent matrices is sufficiently general to allow us to determine the preservers of many other "inertia classes."     

Relative length of long paths and cycles in graphs with large degree sums

For a graph G, p(G) denotes the order of a longest path in G and c(G) the order of a longest cycle. We show that if G is a connected graph n ≥ 3 vertices such that d(u) + d(v) + d(w) ≧ n for all triples u, v, w of independent vertices, then G satisfies c(G) ≥ p(G) – 1, or G is in one of six families of exceptional graphs. This generalizes results of Bondy and of Bauer, Morgana, Schmeichel, and Veldman. © 1995, John Wiley & Sons, Inc.     

Long cycles passing through a specified path in a graph

For a graph G and an integer k ≥ 1, let ς_k(G) = d_G(v_i): {v₁, …, v_k} is an independent set of vertices in G}. Enomoto proved the following theorem. Let s ≥ 1 and let G be a (s + 2)-connected graph. Then G has a cycle of length ≥ min{|V(G)|, ς₂(G) − s} passing through any path of length s. We generalize this result as follows. Let k ≥ 3 and s ≥ 1 and let G be a (k + s − 1)-connected graph. Then G has a cycle of length ≥ min{|V(G)|, − s} passing through any path of length s. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 177–184, 1998     

Sign determinacy of M-matrix minors

We show that if A is an M-matrix for which the length of the longest simple cycle in its associated undirected graph G(A) is at most 3, then every minor of A has determined sign (nonnegative or nonpositive), independent of the magnitudes of the matrix entries. Consequently, if A and B are M-matrices such that G(A) and G(B) are subgraphs of an undirected graph with longest simple cycle at most 3, then all principal minors of AB are nonnegative.     

On the Range of Possible Integrities of Graphs G(n, k)

We discuss the range of values for the integrity of a graphs G(n, k) where G(n, k) denotes a simple graph with n vertices and k edges. Let I _max(n, k) and I _min(n, k) be the maximal and minimal value for the integrity of all possible G(n, k) graphs and let the difference be D(n, k) = I _max(n, k) − I _min(n, k). In this paper we give some exact values and several lower bounds of D(n, k) for various values of n and k. For some special values of n and for s < n ^1/4 we construct examples of graphs G _n  = G _n (n, n + s) with a maximal integrity of I(G _n ) = I(C _n ) + s where C _n is the cycle with n vertices. We show that for k = n ²/6 the value of D(n, n ²/6) is at least \frac?6-13n{\frac{\sqrt{6}-1}{3}n} for large n.     

Structures and Chromaticity of Extremal 3-Colourable Sparse Graphs

 Assume that G is a 3-colourable connected graph with e(G) = 2v(G) −k, where k≥ 4. It has been shown that s ₃(G) ≥ 2 ^{k −3}, where s _r (G) = P(G,r)/r! for any positive integer r and P(G, λ) is the chromatic polynomial of G. In this paper, we prove that if G is 2-connected and s ₃(G) < 2 ^{k −2}, then G contains at most v(G) −k triangles; and the upper bound is attained only if G is a graph obtained by replacing each edge in the k-cycle C _k by a 2-tree. By using this result, we settle the problem of determining if W(n, s) is χ-unique, where W(n, s) is the graph obtained from the wheel W _n by deleting all but s consecutive spokes. Received: January 29, 1999 Final version received: April 8, 2000     

The upper traceable number of a graph

For a nontrivial connected graph G of order n and a linear ordering s: v ₁, v ₂, …, v _n of vertices of G, define . The traceable number t(G) of a graph G is t(G) = min{d(s)} and the upper traceable number t ⁺(G) of G is t ⁺(G) = max{d(s)}, where the minimum and maximum are taken over all linear orderings s of vertices of G. We study upper traceable numbers of several classes of graphs and the relationship between the traceable number and upper traceable number of a graph. All connected graphs G for which t ⁺(G) − t(G) = 1 are characterized and a formula for the upper traceable number of a tree is established. Research supported by Srinakharinwirot University, the Thailand Research Fund and the Commission on Higher Education, Thailand under the grant number MRG 5080075.     

Joint probability generating function for degrees of active/passive random intersection graphs

Correlations of active and passive random intersection graphs are studied in this paper. We present the joint probability generating function for degrees of G ^active(n, m, p) and G ^passive(n, m, p), which are generated by a random bipartite graph G*(n, m, p) on n + m vertices.     

The structure of digraphs associated with the congruence <Emphasis Type="Italic">x</Emphasis><Superscript><Emphasis Type="Italic">k</Emphasis></Superscript> ≡ <Emphasis Type="Italic">y</Emphasis> (mod <Emphasis Type="Italic">n</Emphasis>)

We assign to each pair of positive integers n and k ⩾ 2 a digraph G(n, k) whose set of vertices is H = {0, 1, ..., n − 1} and for which there is a directed edge from a ∈ H to b ∈ H if a ^k ≡ b (mod n). We investigate the structure of G(n, k). In particular, upper bounds are given for the longest cycle in G(n, k). We find subdigraphs of G(n, k), called fundamental constituents of G(n, k), for which all trees attached to cycle vertices are isomorphic.     

Degree sums for edges and cycle lengths in graphs

Let G be a graph of order n satisfying d(u) + d(v) ≥ n for every edge uv of G. We show that the circumference—the length of a longest cycle—of G can be expressed in terms of a certain graph parameter, and can be computed in polynomial time. Moreover, we show that G contains cycles of every length between 3 and the circumference, unless G is complete bipartite. If G is 1-tough then it is pancyclic or G = K_r,r with r = n/2. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 253–256, 1997     

Stability for large forbidden subgraphs

In this note we strengthen the stability theorem of Erd?s and Simonovits. Write K_r(s₁, …, s_r) for the complete r‐partite graph with classes of sizes s₁, …, s_r and T_r(n) for the r‐partite Turán graph of order n. Our main result is: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with e(G)>(1?1/r?ε)n²/2 satisfies one of the conditions:

• (a) G contains a $K_{r+1} (\lfloor c\,\mbox{ln}\,n \rfloor,\ldots,\lfloor c\,\mbox{ln}\,n \rfloor,\lceil n^{{1}-\sqrt{c}}\rceil)In this note we strengthen the stability theorem of Erd?s and Simonovits. Write K_r(s₁, …, s_r) for the complete r‐partite graph with classes of sizes s₁, …, s_r and T_r(n) for the r‐partite Turán graph of order n. Our main result is: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with e(G)>(1?1/r?ε)n²/2 satisfies one of the conditions:
  • (a) G contains a $K_{r+1} (\lfloor c\,\mbox{ln}\,n \rfloor,\ldots,\lfloor c\,\mbox{ln}\,n \rfloor,\lceil n^{{1}-\sqrt{c}}\rceil)$;
  • (b) G differs from T_r(n) in fewer than (ε^1/3+c^1/(3r+3))n² edges.
  Letting µ(G) be the spectral radius of G, we prove also a spectral stability theorem: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with µ(G)>(1?1/r?ε)n satisfies one of the conditions:
  • (a) G contains a $K_{r+1}(\lfloor c\,\mbox{ln}\,n\rfloor,\ldots,\lfloor c\,\mbox{ln}\,n\rfloor,\lceil n^{1-\sqrt{c}}\rceil)$;
  • (b) G differs from T_r(n) in fewer than (ε^1/4+c^1/(8r+8))n² edges.
  © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 362–368, 2009     

List multicoloring problems involving the k‐fold Hall numbers

We show that the four‐cycle has a k‐fold list coloring if the lists of colors available at the vertices satisfy the necessary Hall's condition, and if each list has length at least ?5k/3?; furthermore, the same is not true with shorter list lengths. In terms of h^(k)(G), the k ‐fold Hall number of a graph G, this result is stated as h^(k)(C₄)=2k??k/3?. For longer cycles it is known that h^(k)(C_n)=2k, for n odd, and 2k??k/(n?1)?≤h^(k)(C_n)≤2k, for n even. Here we show the lower bound for n even, and conjecture that this is the right value (just as for C₄). We prove that if G is the diamond (a four‐cycle with a diagonal), then h^(k)(G)=2k. Combining these results with those published earlier we obtain a characterization of graphs G with h^(k)(G)=k. As a tool in the proofs we obtain and apply an elementary generalization of the classical Hall–Rado–Halmos–Vaughan theorem on pairwise disjoint subset representatives with prescribed cardinalities. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 16–34, 2010.     

Component behavior near the critical point of the random graph process

We study the behavior of a random graph process (G(n, M))₀²ⁿ for M(n) = n/2 + s and ∣s∣³n^?;2 → ∞. Among others we find the number of components in G(n, M) and estimate the number of vertices and edges in the kth largest component of G(n, M), for any natural number k, Moreover, it is shown that, with probability 1 –o(1), when M(n) = n/2 + s, s³n^?2 →?∞, then during a random graph process in some step M¹ > M a “new” largest component will emerge, whereas when s³n^?2→∞, the largest component of G(n, M) remains largest until the very end of the process.     

Classification of Morse-Smale diffeomorphisms with one-dimensional set of unstable separatrices

Let M ⁿ be a closed orientable manifold of dimension n > 3. We study the class G ₁(M ⁿ ) of orientation-preserving Morse-Smale diffeomorphisms of M ⁿ such that the set of unstable separatrices of any f ∈ G ₁(M ⁿ ) is one-dimensional and does not contain heteroclinic intersections. We prove that the Peixoto graph (equipped with an automorphism) is a complete topological invariant for diffeomorphisms of class G ₁(M ⁿ ), and construct a standard representative for any class of topologically conjugate diffeomorphisms.