Iterating the branching operation on a directed graph

The branching operation D, defined by Propp, assigns to any directed graph G another directed graph D(G) whose vertices are the oriented rooted spanning trees of the original graph G. We characterize the directed graphs G for which the sequence δ(G) = (G, D(G), D²(G),…) converges, meaning that it is eventually constant. As a corollary of the proof we get the following conjecture of Propp: for strongly connected directed graphs G, δ(G) converges if and only if D²(G) = D(G). © 1997 John Wiley & Sons, Inc.     

The number of spanning trees in regular graphs

Let C(G) denote the number of spanning trees of a graph G. It is shown that there is a function ?(k) that tends to zero as k tends to infinity such that for every connected, k-regular simple graph G on n vertices C(G) = {k[1 ? δ(G)]}ⁿ. where 0 ≤ δ(G) ≤ ?(k).     

Ramsey-type results for oriented trees

For a graph G and a digraph (RIGHT ARROW ABOVE H), we write G → (RIGHT ARROW ABOVE H) (respectively, G (A ABOVE RIGHT ARROW)(RIGHT ARROW ABOVE H) if every orientation (respectively, acyclic orientation) of the edges of G results in an induced copy of (RIGHT ARROW ABOVE H). In this note we study how small the graphs G such that G → (RIGHT ARROW ABOVE H) or such that G (A ABOVE RIGHT ARROW) (RIGHT ARROW ABOVE H) may be, if (RIGHT ARROW ABOVE H) is a given oriented tree (RIGHT ARROW ABOVE T)ⁿ on n vertices. We show that there is a graph on O(n⁴ log n) vertices and O(n⁶(log n)²) edges such that G → Tⁿ for every n-vertex oriented tree (RIGHT ARROW ABOVE T)ⁿ. We also prove that there exists a graph G with O(n² log n) vertices and O(n³(log n)²) edges such that G → (RIGHT ARROW ABOVE T)ⁿ for any such tree (RIGHT ARROW ABOVE T)ⁿ. This last result turns out to be nearly best possible as it is shown that any graph G with G (A ABOVE RIGHT ARROW) (RIGHT ARROW ABOVE P)ⁿ, where (RIGHT ARROW ABOVE P)ⁿ is the directed path of order n, has more than n²/2 vertices and more than [n/3]³ edges if n ≥ 3. © 1996, John Wiley & Sons, Inc.     

Decomposing oriented graphs into transitive tournaments

For an oriented graph G with n vertices, let f(G) denote the minimum number of transitive subtournaments that decompose G. We prove several results on f(G). In particular, if G is a tournament then and there are tournaments for which f(G)>n²/3000. For general G we prove that f(G)?⌊n²/3⌋ and this is tight. Some related parameters are also considered.     

Acyclic and oriented chromatic numbers of graphs

The oriented chromatic number χ_o(G ^→) of an oriented graph G ^→ = (V, A) is the minimum number of vertices in an oriented graph H ^→ for which there exists a homomorphism of G ^→ to H ^→. The oriented chromatic number χ_o(G) of an undirected graph G is the maximum of the oriented chromatic numbers of all the orientations of G. This paper discusses the relations between the oriented chromatic number and the acyclic chromatic number and some other parameters of a graph. We shall give a lower bound for χ_o(G) in terms of χ_a(G). An upper bound for χ_o(G) in terms of χ_a(G) was given by Raspaud and Sopena. We also give an upper bound for χ_o(G) in terms of the maximum degree of G. We shall show that this upper bound is not far from being optimal. © 1997 John Wiley & Sons, Inc.     

Sufficient conditions for equality of connectivity and minimum degree of a graph

For a graph G, let n(G), κ(G) and δ(G) denote the order, the connectivity, and the minimum degree of G, respectively. The paper contains some conditions on G implying κ(G) = δ(G). One of the conditions is that n(G) ≤ δ(G)(2p ?1)/(2p ?3) if G is a p-partite graph. © 1993 John Wiley & Sons, Inc.     

Diameters of iterated clique graphs of chordal graphs

The clique graph K(G) of a graph is the intersection graph of maximal cliques of G. The iterated clique graph Kⁿ(G) is inductively defined as K(K^n?1(G)) and K¹(G) = K(G). Let the diameter diam(G) be the greatest distance between all pairs of vertices of G. We show that diam(Kⁿ(G)) = diam(G) — n if G is a connected chordal graph and n ≤ diam(G). This generalizes a similar result for time graphs by Bruce Hedman.     

Minimum degree of minimal defect -extendable bipartite graphs

A near perfect matching is a matching saturating all but one vertex in a graph. If G is a connected graph and any n independent edges in G are contained in a near perfect matching, then G is said to be defect n-extendable. If for any edge e in a defect n-extendable graph G, G−e is not defect n-extendable, then G is minimal defect n-extendable. The minimum degree and the connectivity of a graph G are denoted by δ(G) and κ(G) respectively. In this paper, we study the minimum degree of minimal defect n-extendable bipartite graphs. We prove that a minimal defect 1-extendable bipartite graph G has δ(G)=1. Consider a minimal defect n-extendable bipartite graph G with n≥2, we show that if κ(G)=1, then δ(G)≤n+1 and if κ(G)≥2, then 2≤δ(G)=κ(G)≤n+1. In addition, graphs are also constructed showing that, in all cases but one, there exist graphs with minimum degree that satisfies the established bounds.     

MAX-CUT has a randomized approximation scheme in dense graphs

A cut in a graph G = (V(G), E(G)) is the boundary δ(S) of some subset S η V(G) and the maximum cut problem for G is to find the maximum number of edges in a cut. Let MC(G) denote this maximum. For any given 0 < α < 1, ϵ > 0, and η, we give a randomized algorithm which runs in a polynomial time and which, when applied to any given graph G on n vertices with minimum degree ≥αn, outputs a cut δ(S) of G with $ P[|\delta(S)|\geq MC(G)(1-\epsilon)] \geq 1-2^{-n} $ We also show that the proposed method can be used to approximate MAXIMUM ACYCLIC SUBGRAPH in the unweighted case. © 1996 John Wiley & Sons, Inc.     

Overlap number of graphs

An overlap representation of a graph G assigns sets to vertices so that vertices are adjacent if and only if their assigned sets intersect with neither containing the other. The overlap number φ(G) (introduced by Rosgen) is the minimum size of the union of the sets in such a representation. We prove the following: (1) An optimal overlap representation of a tree can be produced in linear time, and its size is the number of vertices in the largest subtree in which the neighbor of any leaf has degree 2. (2) If δ(G)?2 and G≠K₃, then φ(G)?|E(G)| ? 1, with equality when G is connected and triangle‐free and has no star‐cutset. (3) If G is an n‐vertex plane graph with n?5, then φ(G)?2n ? 5, with equality when every face has length 4 and there is no star‐cutset. (4) If G is an n‐vertex graph with n?14, then φ(G)?n²/4 ? n/2 ? 1, with equality for even n when G arises from K_{n/2, n/2} by deleting a perfect matching. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Graphs whose every transitive orientation contains almost every relation

Given a graphG onn vertices and a total ordering ≺ ofV(G), the transitive orientation ofG associated with ≺, denotedP(G; ≺), is the partial order onV(G) defined by settingx<y inP(G; ≺) if there is a pathx=x ₁ x ₂…x _r=y inG such thatx ₁ ≺x _j for 1≦i<j≦r. We investigate graphsG such that every transitive orientation ofG contains ₂ ⁿ −o(n ²) relations. We prove that almost everyG _n,p satisfies this requirement if , but almost noG _n,p satisfies the condition if (pn log log logn)/(logn log logn) is bounded. We also show that every graphG withn vertices and at mostcn logn edges has some transitive orientation with fewer than ₂ ⁿ −δ(c)n ² relations. Partially supported by MCS Grant 8104854.     

Characterizing defect n-extendable graphs and -critical graphs

A near perfect matching is a matching saturating all but one vertex in a graph. Let G be a connected graph. If any n independent edges in G are contained in a near perfect matching where n is a positive integer and n(|V(G)|-2)/2, then G is said to be defect n-extendable. If deleting any k vertices in G where k|V(G)|-2, the remaining graph has a perfect matching, then G is a k-critical graph. This paper first shows that the connectivity of defect n-extendable graphs can be any integer. Then the characterizations of defect n-extendable graphs and (2k+1)-critical graphs using M-alternating paths are presented.     

Minimum degree thresholds for bipartite graph tiling

Given a bipartite graph H and a positive integer n such that v(H) divides 2n, we define the minimum degree threshold for bipartite H‐tiling, δ₂(n, H), as the smallest integer k such that every bipartite graph G with n vertices in each partition and minimum degree δ(G)≥k contains a spanning subgraph consisting of vertex‐disjoint copies of H. Zhao, Hladký‐Schacht, Czygrinow‐DeBiasio determined δ₂(n, K_{s, t}) exactly for all s?t and suffi‐ciently large n. In this article we determine δ₂(n, H), up to an additive constant, for all bipartite H and sufficiently large n. Additionally, we give a corresponding minimum degree threshold to guarantee that G has an H‐tiling missing only a constant number of vertices. Our δ₂(n, H) depends on either the chromatic number χ(H) or the critical chromatic number χ_cr(H), while the threshold for the almost perfect tiling only depends on χ_cr(H). These results can be viewed as bipartite analogs to the results of Kuhn and Osthus [Combinatorica 29 (2009), 65–107] and of Shokoufandeh and Zhao [Rand Struc Alg 23 (2003), 180–205]. © 2011 Wiley Periodicals, Inc. J Graph Theory     

The 3‐connectivity of a graph and the multiplicity of zero “2” of its chromatic polynomial

Let G be a graph of order n, maximum degree Δ, and minimum degree δ. Let P(G, λ) be the chromatic polynomial of G. It is known that the multiplicity of zero “0” of P(G, λ) is one if G is connected, and the multiplicity of zero “1” of P(G, λ) is one if G is 2‐connected. Is the multiplicity of zero “2” of P(G, λ) at most one if G is 3‐connected? In this article, we first construct an infinite family of 3‐connected graphs G such that the multiplicity of zero “2” of P(G, λ) is more than one, and then characterize 3‐connected graphs G with Δ + δ?n such that the multiplicity of zero “2” of P(G, λ) is at most one. In particular, we show that for a 3‐connected graph G, if Δ + δ?n and (Δ, δ₃)≠(n?3, 3), where δ₃ is the third minimum degree of G, then the multiplicity of zero “2” of P(G, λ) is at most one. © 2011 Wiley Periodicals, Inc. J Graph Theory     

The symmetric (2k,k)‐graphs

A noncomplete graph G is called an (n, k)‐graph if it is n‐connected and G − X is not (n − |X| + 1)‐connected for any X ⊆ V(G) with |X| ≤ k. Mader conjectured that for k ≥ 3 the graph K_{2k + 2} − (1‐factor) is the unique (2k, k)‐graph. We settle this conjecture for strongly regular graphs, for edge transitive graphs, and for vertex transitive graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 36: 35–51, 2001     

Random I-colorable graphs

In this article we investigate properties of the class of all l-colorable graphs on n vertices, where l = l(n) may depend on n. Let G^l_n denote a uniformly chosen element of this class, i.e., a random l-colorable graph. For a random graph G^l_n we study in particular the property of being uniquely l-colorable. We show that not only does there exist a threshold function l = l(n) for this property, but this threshold corresponds to the chromatic number of a random graph. We also prove similar results for the class of all l-colorable graphs on n vertices with m = m(n) edges.     

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.     

Exotic n-universal graphs

An n-universal graph is a graph that contains as an induced subgraph a copy of every graph on n vertices. It is shown that for each positive integer n > 1 there exists an n-universal graph G on 4ⁿ - 1 vertices such that G is a (v, k, λ)-graph, and both G and its complement G¯ are 1-transitive in the sense of W. T. Tutte and are of diameter 2. The automorphism group of G is a transitive rank 3 permutation group, i.e., it acts transitively on (1) the vertices of G, (2) the ordered pairs uv of adjacent vertices of G, and (3) the ordered pairs xy of nonadjacent vertices of G.     

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