Finding Scores in Tournaments

A tournamentT_nis an orientation of the complete graph onnvertices. We continue the algorithmic study initiated by10of recognizing various directed trees in tournaments. Hell and Rosenfeld studied the complexity of finding various oriented paths in tournaments by probing edge directions. Here, we investigate the complexity of finding a vertex of prescribed outdegree (or indegree) in the same model. We show that the complexity of finding a vertex of outdegreek( ≤ (n − 1)/2) inT_nis Θ(nk). This bound is in sharp contrast to the Θ(n) bound for selection in the case of transitive tournaments. We also establish tight bounds for finding vertices of prescribed degree from the adjacency matrix of general directed/undirected graphs. These bounds generalize the classical bound of11for finding a sink (a vertex of outdegree 0 and indegreen − 1) in a directed graph.     

Directed triangles in directed graphs

We show that each directed graph (with no parallel arcs) on n vertices, each with indegree and outdegree at least n/twhere t=2.888997… contains a directed circuit of length at most 3.     

Oriented hamilton cycles in digraphs

We show that a directed graph of order n will contain n-cycles of every orientation, provided each vertex has indegree and outdegree at least (1/2 + n^-1/6)n and n is sufficiently large. © 1995 John Wiley & Sons, Inc.     

On short cycles in triangle-free oriented graphs

An orientation of a simple graph is referred to as an oriented graph. Caccetta and Häggkvist conjectured that any digraph on n vertices with minimum outdegree d contains a directed cycle of length at most ?n/d?. In this paper, we consider short cycles in oriented graphs without directed triangles. Suppose that α0 is the smallest real such that every n-vertex digraph with minimum outdegree at least α₀n contains a directed triangle. Let ε < (3 ? 2α₀)/(4 ? 2α₀) be a positive real. We show that if D is an oriented graph without directed triangles and has minimum outdegree and minimum indegree at least (1/(4 ? 2α₀)+ε)|D|, then each vertex of D is contained in a directed cycle of length l for each 4 ≤ l < (4 ? 2α₀)ε|D|/(3 ? 2α₀) + 2.     

Score sequences in oriented graphs

An oriented graph is a digraph with no symmetric pairs of directed arcs and without loops. The score of a vertexv _i in an oriented graph D is $a_{v_i } $ (or simply a_i) $d_{v_i }^ - $ are the outdegree and indegree, respectively, ofv _i and n is the number of vertices in D. In this paper, we give a new proof of Avery’s theorem and obtain some stronger inequalities for scores in oriented graphs. We also characterize strongly transitive oriented graphs.     

Topological minors in bipartite graphs

For a bipartite graph G on m and n vertices, respectively, in its vertices classes, and for integers s and t such that 2 ≤ s ≤ t, 0 ≤ m − s ≤ n − t, and m + n ≤ 2s + t − 1, we prove that if G has at least mn − (2(m − s) + n − t) edges then it contains a subdivision of the complete bipartite K _(s,t) with s vertices in the m-class and t vertices in the n-class. Furthermore, we characterize the corresponding extremal bipartite graphs with mn − (2(m − s) + n − t + 1) edges for this topological Turan type problem.     

Note on Halin's theorem on minimally connected graphs

In this note it is shown that any finite directed graph of strong connectivity n contains either a vertex with indegree n, a vertex with outdegree n, or an edge whose removal does not decrease the connectivity. This is a directed graph counterpart of Halin's theorem on undirected graphs. It is pointed out that only a few preparations and modifications are necessary to make his proof valid for directed graphs.     

Cycles of given color patterns

In 2-edge-colored graphs, we define an (s, t)-cycle to be a cyle of length s + t, in which s consecutive edges are in one color and the remaining t edges are in the other color. Here we investigate the existence of (s, t)-cycles, in a 2-edge-colored complete graph K^c_n on n vertices. In particular, in the first result we give a complete characterization for the existence of (s, t)-cycles in K^c_n with n relatively large with respect to max({s, t}). We also study cycles of length 4 for all possible values of s and t. Then, we show that K^c_n contains an (s, t)-hamiltonian cycle unless it is isomorphic to a specified graph. This extends a result of A. Gyárfás [Journal of Graph Theory, 7 (1983), 131–135]. Finally, we give some sufficient conditions for the existence of (s, 1)-cycles, (inverted sans serif aye) s ϵ {2, 3,…, n − 2}. © 1996 John Wiley & Sons, Inc.     

Degree frequencies in digraphs and tournaments

The number of vertices in a digraph G having a particular outdegree (indegree) is called the frequency of the outdegree (indegree). A set F of distinct positive integers {f₁, f₂, …, f_n} is the frequency set of the digraph G if every outdegree and indegree occurs with frequency f_j∈F and for each f_j∈F there is a least one outdegree and at least one indegree with frequency f_j. We prove that each nonempty set F of positive integers is the frequency set of some tournament, and we determine the smallest possible order for such a tournament. Similar results for asymmetric digraphs are also given. The results and techniques for frequency sets are used to derive corresponding results for vertex frequency partitions.     

Claw‐decompositions and tutte‐orientations

We conjecture that, for each tree T, there exists a natural number k_T such that the following holds: If G is a k_T‐edge‐connected graph such that |E(T)| divides |E(G)|, then the edges of G can be divided into parts, each of which is isomorphic to T. We prove that for T = K_1,3 (the claw), this holds if and only if there exists a (smallest) natural number k_t such that every k_t‐edge‐connected graph has an orientation for which the indegree of each vertex equals its outdegree modulo 3. Tutte's 3‐flow conjecture says that k_t = 4. We prove the weaker statement that every 4$\lceil$ log n$\rceil$ ‐edge‐connected graph with n vertices has an edge‐decomposition into claws provided its number of edges is divisible by 3. We also prove that every triangulation of a surface has an edge‐decomposition into claws. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 135–146, 2006     

A sufficient condition for the existence of an anti-directed 2-factor in a directed graph

Let D be a directed graph with vertex set V, arc set A, and order n. The graph underlyingD is the graph obtained from D by replacing each arc (u,v)∈A by an undirected edge {u,v} and then replacing each double edge by a single edge. An anti-directed (hamiltonian) cycleH in D is a (hamiltonian) cycle in the graph underlying D such that no pair of consecutive arcs in H form a directed path in D. An anti-directed 2-factor in D is a vertex-disjoint collection of anti-directed cycles in D that span V. It was proved in Busch et al. (submitted for publication) [3] that if the indegree and the outdegree of each vertex of D is greater than then D contains an anti-directed Hamilton cycle. In this paper we prove that given a directed graph D, the problem of determining whether D has an anti-directed 2-factor is NP-complete, and we use a proof technique similar to the one used in Busch et al. (submitted for publication) [3] to prove that if the indegree and the outdegree of each vertex of D is greater than then D contains an anti-directed 2-factor.     

Improved Sufficient Conditions for the Existence of Anti-Directed Hamiltonian Cycles in Digraphs

Let D be a directed graph of order n. An anti-directed (hamiltonian) cycle H in D is a (hamiltonian) cycle in the graph underlying D such that no pair of consecutive arcs in H form a directed path in D. In this paper we give sufficient conditions for the existence of anti-directed hamiltonian cycles. Specifically, we prove that a directed graph D of even order n with minimum indegree and outdegree greater than ${\frac{1}{2}n + 7\sqrt{n}/3}$ contains an anti-directed hamiltonian cycle. In addition, we show that D contains anti-directed cycles of all possible (even) lengths when n is sufficiently large and has minimum in- and out-degree at least ${(1/2+ \epsilon)n}$ for any ${\epsilon > 0}$ .     

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.     

Minimal n-fach zusammenhängende Digraphen

For a minimally n-connected digraph D, the subgraph spanned by the edges (x, y) with outdegree of x and indegree of y exceeding n is denoted by D₀. It is proved that D₀ corresponds to a forest. This implies that in a finite, minimally n-connected digraph D, the number of vertices of outdegree n is at least n and that the number of vertices of outdegree or indegree equal to n grows linearly in |D|. For almost every integer m, the maximum number of edges in a minimally n-connected digraph of order m is determined and the extremal digraphs are characterized.     

A note on transitive orientations with maximum sets of sources and sinks

Given a transitive orientation of a comparability graph G, a vertex of G is a source (sink) if it has indegree (outdegree) zero in , respectively. A source set of G is a subset of vertices formed by sources of some transitive orientation . A pair of subsets S,TV(G) is a source–sink pair of G when the vertices of S and T are sources and sinks, of some transitive orientation , respectively. We describe algorithms for finding a transitive orientation with a maximum source–sink pair in a comparability graph. The algorithms are applications of modular decomposition and are all of linear-time complexity.     

Digraphs containing every possible pair of dicycles

Let D = (V, A) be a directed graph of order n ≥ 4. Suppose that the minimum degree of D is at least (3n − 3)/2. Then for any two integers s and t with s ≥ 2, t ≥ 2 and s + t ≤ n, D contains two vertex‐disjoint directed cycles of lengths s and t, respectively. Moreover, the condition on the minimum degree is sharp. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 154–162, 2000     

A neighborhood condition which implies the existence of a class of d-chromatic subgraphs

A graph G of order n satisfies the neighborhood condition NC_k > s if any collection of k independent vertices is collectively adjacent to more than s vertices. Given a family H of graphs, the decomposition class β(H) is the family of graphs B with the property that for some H ∈ H of chromatic number d, H contains B as an induced subgraph and l?V(H) ? V(B)? is (d ? 2) colorable. Let H be a family of d-chromatic graphs, B an element of β(H) such that B contains an s-matching as an induced subgraph. Thus the cardinality of one of the partite sets of B is s + r for some integer r ≥ 0. We show that if t is a fixed positive integer, G is a graph of sufficiently large order n that satisfies the neighborhood condition then G contains B + K(d - 2; t) as a subgraph.     

A constructive approach for the lower bounds on the Ramsey numbers R (s,t)

Graph G is a (k, p)‐graph if G does not contain a complete graph on k vertices K_k, nor an independent set of order p. Given a (k, p)‐graph G and a (k, q)‐graph H, such that G and H contain an induced subgraph isomorphic to some K_k?1‐free graph M, we construct a (k, p + q ? 1)‐graph on n(G) + n(H) + n(M) vertices. This implies that R (k, p + q ? 1) ≥ R (k, p) + R (k, q) + n(M) ? 1, where R (s, t) is the classical two‐color Ramsey number. By applying this construction, and some its generalizations, we improve on 22 lower bounds for R (s, t), for various specific values of s and t. In particular, we obtain the following new lower bounds: R (4, 15) ≥ 153, R (6, 7) ≥ 111, R (6, 11) ≥ 253, R (7, 12) ≥ 416, and R (8, 13) ≥ 635. Most of the results did not require any use of computer algorithms. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 231–239, 2004     

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.     

The diameter of randomly perturbed digraphs and some applications

The central observation of this paper is that if εn random arcs are added to any n‐node strongly connected digraph with bounded degree then the resulting graph has diameter 𝒪(lnn) with high probability. We apply this to smoothed analysis of algorithms and property testing. Smoothed Analysis: Recognizing strongly connected digraphs is a basic computational task in graph theory. Even for digraphs with bounded degree, it is NL‐complete. By XORing an arbitrary bounded degree digraph with a sparse random digraph R ∼ 𝔻_n,ε/n we obtain a “smoothed” instance. We show that, with high probability, a log‐space algorithm will correctly determine if a smoothed instance is strongly connected. We also show that if NL ⫅̸ almost‐L then no heuristic can recognize similarly perturbed instances of (s,t)‐connectivity. Property Testing: A digraph is called k‐linked if, for every choice of 2k distinct vertices s₁,…,s_k,t₁,…,t_k, the graph contains k vertex disjoint paths joining s_r to t_r for r = 1,…,k. Recognizing k‐linked digraphs is NP‐complete for k ≥ 2. We describe a polynomial time algorithm for bounded degree digraphs, which accepts k‐linked graphs with high probability, and rejects all graphs that are at least εn arcs away from being k‐linked. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007