Ramsey-Type Results for Unions of Comparability Graphs

 It is well known that the comparability graph of any partially ordered set of n elements contains either a clique or an independent set of size at least . In this note we show that any graph of n vertices which is the union of two comparability graphs on the same vertex set, contains either a clique or an independent set of size at least . On the other hand, there exist such graphs for which the size of any clique or independent set is at most n ^0.4118. Similar results are obtained for graphs which are unions of a fixed number k comparability graphs. We also show that the same bounds hold for unions of perfect graphs. Received: November 1, 1999 Final version received: December 1, 2000     

The Laplacian spread of graphs

The Laplacian spread of a graph is defined as the difference between the largest and second smallest eigenvalues of the Laplacian matrix of the graph. In this paper, bounds are obtained for the Laplacian spread of graphs. By the Laplacian spread, several upper bounds of the Nordhaus-Gaddum type of Laplacian eigenvalues are improved. Some operations on Laplacian spread are presented. Connected c-cyclic graphs with n vertices and Laplacian spread n − 1 are discussed.     

On the sum of all distances in a graph or digraph

The transmission of a graph or digraph G is the sum of all distances in G. Strict bounds on the transmission are collected and extended for several classes of graphs and digraphs. For example, in the class of 2-connected or 2-edge-connected graphs of order n, the maximal transmission is realized only by the cycle C_n. The independence of the transmission on the diameter or radius is shown. Remarks are also given about the NP-hardness of some related algorithmic problems.     

Ramsey Theory and Bandwidth of Graphs

 The bandwidth of a graph is the minimum, over vertex labelings with distinct integers, of the maximum difference between labels on adjacent vertices. Kuang and McDiarmid proved that almost all n-vertex graphs have bandwidth . Thus the sum of the bandwidths of a graph and its complement is almost always at least ; we prove that it is always at most 2n−4 log ₂ n+o(log n). The proofs involve improving the bounds on the Ramsey and Turán numbers of the “halfgraph”. Received: September 2, 1998?Final version received: November 29, 1999     

Diameter bounds for altered graphs

The main question addressed in this article is the following: If t edges are removed from a (t + 1) edge-connected graph G having diameter D, how large can the diameter of the resulting graph be? (The diameter of a graph is the maximum, over all pairs of vertices, of the length of the shortest path joining those vertices.) We provide bounds on this value that imply that the maximum possible diameter of the resulting graph, for large D and fixed t, is essentially (t + 1) · D. The bulk of the proof consists of showing that, if t edges are added to an n-vertex path P_n, then the diameter of the resulting graph is at least (n/(t + 1)) - 1. Using a similar proof, we also show that if t edges are added to an n-vertex cycle C_n, then the least possible diameter of the resulting graph is (for large n) essentially n/(t + 2) when t is even and n/(t + 1) when t is odd. Examples are given in all these cases to show that there exist graphs for which the bounds are achieved. We also give results for the corresponding vertex deletion problem for general graphs. Such results are of interest, for example, when studying the potential effects of node or link failures on the performance of a communication network, especially for networks in which the maximum time-delay or signal degradation is directly related to the diameter of the network.     

On the Nullity of Bipartite Graphs

The nullity of a graph is the multiplicity of the eigenvalue zero in its spectrum. We obtain some lower bounds for the nullity of graphs and we then find the nullity of bipartite graphs with no cycle of length a multiple of 4 as a subgraph. Among bipartite graphs on n vertices, the star has the greatest nullity (equal to n − 2). We generalize this by showing that among bipartite graphs with n vertices, e edges and maximum degree Δ which do not have any cycle of length a multiple of 4 as a subgraph, the greatest nullity is . G. R. Omidi: This research was in part supported by a grant from IPM (No.87050016).     

The analysis of a nested dissection algorithm

Summary Nested dissection is an algorithm invented by Alan George for preserving sparsity in Gaussian elimination on symmetric positive definite matrices. Nested dissection can be viewed as a recursive divide-and-conquer algorithm on an undirected graph; it usesseparators in the graph, which are small sets of vertices whose removal divides the graph approximately in half. George and Liu gave an implementation of nested dissection that used a heuristic to find separators. Lipton and Tarjan gave an algorithm to findn ^1/2-separators in planar graphs and two-dimensional finite element graphs, and Lipton, Rose, and Tarjan used these separators in a modified version of nested dissection, guaranteeing bounds ofO (n logn) on fill andO(n ^3/2) on operation count. We analyze the combination of the original George-Liu nested dissection algorithm and the Lipton-Tarjan planar separator algorithm. This combination is interesting because it is easier to implement than the Lipton-Rose-Tarjan version, especially in the framework of existïng sparse matrix software. Using some topological graph theory, we proveO(n logn) fill andO(n ^3/2) operation count bounds for planar graphs, twodimensional finite element graphs, graphs of bounded genus, and graphs of bounded degree withn ^1/2-separators. For planar and finite element graphs, the leading constant factor is smaller than that in the Lipton-Rose-Tarjan analysis. We also construct a class of graphs withn ^1/2-separators for which our algorithm does not achieve anO(n logn) bound on fill.The work of this author was supported in part by the Hertz Foundation under a graduate fellowship and by the National Science Foundation under Grant MCS 82-02948The work of this author was supported in part by the National Science Foundation under Grant MCS 78-26858 and by the Office of Naval Research under Contract N00014-76-C-0688     

Random maximal H‐free graphs*

Given a graph H, a random maximal H‐free graph is constructed by the following random greedy process. First assign to each edge of the complete graph on n vertices a birthtime which is uniformly distributed in [0, 1]. At time p=0 start with the empty graph and increase p gradually. Each time a new edge is born, it is included in the graph if this does not create a copy of H. The question is then how many edges such a graph will have when p=1. Here we give asymptotically almost sure bounds on the number of edges if H is a strictly 2‐balanced graph, which includes the case when H is a complete graph or a cycle. Furthermore, we prove the existence of graphs with girth greater than 𝓁 and chromatic number n*y1/(𝓁‐1)+o(1), which improves on previous bounds for 𝓁>3. ©2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 61–82, 2001     

Total domination in 2‐connected graphs and in graphs with no induced 6‐cycles

A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number γ_t(G) of G. It is known [J Graph Theory 35 (2000), 21–45] that if G is a connected graph of order n > 10 with minimum degree at least 2, then γ_t(G) ≤ 4n/7 and the (infinite family of) graphs of large order that achieve equality in this bound are characterized. In this article, we improve this upper bound of 4n/7 for 2‐connected graphs, as well as for connected graphs with no induced 6‐cycle. We prove that if G is a 2‐connected graph of order n > 18, then γ_t(G) ≤ 6n/11. Our proof is an interplay between graph theory and transversals in hypergraphs. We also prove that if G is a connected graph of order n > 18 with minimum degree at least 2 and no induced 6‐cycle, then γ_t(G) ≤ 6n/11. Both bounds are shown to be sharp. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 55–79, 2009     

On the embedding of graphs into graphs with few eigenvalues

A graph is called of type k if it is connected, regular, and has k distinct eigenvalues. For example graphs of type 2 are the complete graphs, while those of type 3 are the strongly regular graphs. We prove that for any positive integer n, every graph can be embedded in n cospectral, non-isomorphic graphs of type k for every k ≥ 3. Furthermore, in the case k ≥ 5 such a family of extensions can be found at every sufficiently large order. Some bounds for the extension will also be given. © 1996 John Wiley & Sons, Inc.     

On some subclasses of well-covered graphs

A set of points in a graph is independent if no two points in the set are adjacent. A graph is well covered if every maximal independent set is a maximum independent set or, equivalently, if every independent set is contained in a maximum independent set. The well-covered graphs are classified by the W_n property: For a positive integer n, a graph G belongs to class W_n if ≥ n and any n disjoint independent sets are contained in n disjoint maximum independent sets. Constructions are presented that show how to build infinite families of W_n graphs containing arbitrarily large independent sets. A characterization of W_n graphs in terms of well-covered subgraphs is given, as well as bounds for the size of a maximum independent set and the minimum and maximum degrees of points in W_n graphs.     

Turán-type results for partial orders and intersection graphs of convex sets

We prove Ramsey-type results for intersection graphs of geometric objects. In particular, we prove the following bounds, all of which are tight apart from the constant c. There is a constant c > 0 such that for every family F of n convex sets in the plane, the intersection graph of F or its complement contains a balanced complete bipartite graph of size at least cn. There is a constant c > 0 such that for every family F of n x-monotone curves in the plane, the intersection graph G of F contains a balanced complete bipartite graph of size at least cn/log n or the complement of G contains a balanced complete bipartite graph of size at least cn. Our bounds rely on new Turán-type results on incomparability graphs of partially ordered sets.     

Cycles in 2-Factors of Balanced Bipartite Graphs

In the study of hamiltonian graphs, many well known results use degree conditions to ensure sufficient edge density for the existence of a hamiltonian cycle. Recently it was shown that the classic degree conditions of Dirac and Ore actually imply far more than the existence of a hamiltonian cycle in a graph G, but also the existence of a 2-factor with exactly k cycles, where . In this paper we continue to study the number of cycles in 2-factors. Here we consider the well-known result of Moon and Moser which implies the existence of a hamiltonian cycle in a balanced bipartite graph of order 2n. We show that a related degree condition also implies the existence of a 2-factor with exactly k cycles in a balanced bipartite graph of order 2n with . Revised: May 7, 1999     

Hamilton cycle rich two‐factorizations of complete graphs

For all integers n ≥ 5, it is shown that the graph obtained from the n‐cycle by joining vertices at distance 2 has a 2‐factorization is which one 2‐factor is a Hamilton cycle, and the other is isomorphic to any given 2‐regular graph of order n. This result is used to prove several results on 2‐factorizations of the complete graph K_n of order n. For example, it is shown that for all odd n ≥ 11, K_n has a 2‐factorization in which three of the 2‐factors are isomorphic to any three given 2‐regular graphs of order n, and the remaining 2‐factors are Hamilton cycles. For any two given 2‐regular graphs of even order n, the corresponding result is proved for the graph K_n ‐ I obtained from the complete graph by removing the edges of a 1‐factor. © 2004 Wiley Periodicals, Inc.     

Enumeration of Full Graphs: Onset of the Asymptotic Region

A full graph on n vertices, as defined by Fulkerson, is a representation of the intersection and containment relations among a system of n sets. It has an undirected edge between vertices representing intersecting sets and a directed edge from a to b if the corresponding set A contains B;. Kleitman, Lasaga, and Cowen gave a unified argument to show that asymptotically, almost all full graphs can be obtained by taking an arbitrary undirected graph on the n vertices, distinguishing a clique in this graph, which need not be maximal, and then adding directed edges going out from each vertex in the clique to all vertices to which there is not already an existing undirected edge. Call graphs of this type members of the dominant class. This article obtains the first upper and lower bounds on how large n has to be, so that the asymptotic behavior is indeed observed. It is shown that when n > 170, the dominant class predominates, while when n < 17, the full graphs in the dominant class compose less than half of the total number of realizable full graphs on n vertices.     

3‐Factor‐Criticality of Vertex‐Transitive Graphs

A graph of order n is p ‐factor‐critical, where p is an integer of the same parity as n, if the removal of any set of p vertices results in a graph with a perfect matching. 1‐factor‐critical graphs and 2‐factor‐critical graphs are factor‐critical graphs and bicritical graphs, respectively. It is well known that every connected vertex‐transitive graph of odd order is factor‐critical and every connected nonbipartite vertex‐transitive graph of even order is bicritical. In this article, we show that a simple connected vertex‐transitive graph of odd order at least five is 3‐factor‐critical if and only if it is not a cycle.     

Geometric Graphs with Few Disjoint Edges

A geometric graph is a graph drawn in the plane so that the vertices are represented by points in general position, the edges are represented by straight line segments connecting the corresponding points. Improving a result of Pach and T?rőcsik, we show that a geometric graph on n vertices with no k+1 pairwise disjoint edges has at most k ³ (n+1) edges. On the other hand, we construct geometric graphs with n vertices and approximately (3/2)(k-1)n edges, containing no k+1 pairwise disjoint edges. We also improve both the lower and upper bounds of Goddard, Katchalski, and Kleitman on the maximum number of edges in a geometric graph with no four pairwise disjoint edges. Received May 7, 1998, and in revised form March 24, 1999.     

New Bounds on Crossing Numbers

The crossing number , cr(G) , of a graph G is the least number of crossing points in any drawing of G in the plane. Denote by κ(n,e) the minimum of cr(G) taken over all graphs with n vertices and at least e edges. We prove a conjecture of Erdos os and Guy by showing that κ(n,e)n ² /e ³ tends to a positive constant as n→∈fty and n l e l n ² . Similar results hold for graph drawings on any other surface of fixed genus. We prove better bounds for graphs satisfying some monotone properties. In particular, we show that if G is a graph with n vertices and e≥ 4n edges, which does not contain a cycle of length four (resp. six ), then its crossing number is at least ce ⁴ /n ³ (resp. ce ⁵ /n ⁴ ), where c>0 is a suitable constant. These results cannot be improved, apart from the value of the constant. This settles a question of Simonovits. Received January 27, 1999, and in revised form March 23, 1999.     

Note on vertex degrees of planar graphs

In this note the second moment of the vertex degree sequence of planar graphs is considered. We prove that

• 1 If G is an outerplanar graph of order n ? 3 then

• 2 If G is a planar graph of order n ? 4 then

where d₁,…,d_n is the vertex degree sequence of G. We exhibit all graphs for which these upper bounds are attained.     

Applications of balance equations to vertex switching reconstruction

A graph is called s-vertex switching reconstructible (s-VSR) if it is uniquely defined, up to isomorphism, by the multiset of unlabeled graphs obtained by switching of all its s-vertex subsets. We show that a graph with n vertices is n/2-VSR if n = 0(mod 4), (n ? 2)/2-VSR and n/2-VSR if n = 2(mod 4), (n ? 1)/2-VSR if n = 1 (mod 2). For hypothetical nonreconstructible graphs, we give bounds on the number of edges (for any s) and on the maximum and minimum degree (for s = 2). We also show that for n > 9 the degree sequence is 2-VSR.