Decomposing graphs with girth at least five under degree constraints

We prove that the vertex set of a simple graph with minimum degree at least s + t − 1 and girth at least 5 can be decomposed into two parts, which induce subgraphs with minimum degree at least s and t, respectively, where s, t are positive integers ≥ 2. © 2000 John Wiley & Sons, Inc: J Graph Theory 33: 237–239, 2000     

Solution of a conjecture of Tewes and Volkmann regarding extendable cycles in in‐tournaments

A directed cycle C of a digraph D is extendable if there exists a directed cycle C′ in D that contains all vertices of C and an additional one. In 1989, Hendry defined a digraph D to be cycle extendable if it contains a directed cycle and every non‐Hamiltonian directed cycle of D is extendable. Furthermore, D is fully cycle extendable if it is cycle extendable and every vertex of D belongs to a directed cycle of length three. In 2001, Tewes and Volkmann extended these definitions in considering only directed cycles whose length exceed a certain bound 3≤k<n: a digraph D is k ‐extendable if every directed cycle of length t, where k≤t<n, is extendable. Moreover, D is called fully k ‐extendable if D is k ‐extendable and every vertex of D belongs to a directed cycle of length k. An in‐tournament is an oriented graph such that the in‐neighborhood of every vertex induces a tournament. This class of digraphs which generalizes the class of tournaments was introduced by Bang‐Jensen, Huang and Prisner in 1993. Tewes and Volkmann showed that every connected in‐tournament D of order n with minimum degree δ≥1 is ( ) ‐extendable. Furthermore, if D is a strongly connected in‐tournament of order n with minimum degree δ=2 or , then D is fully ( ) ‐extendable. In this article we shall see that if , every vertex of D belongs to a directed cycle of length , which means that D is fully ( ) ‐extendable. This confirms a conjecture of Tewes and Volkmann. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 82–92, 2010     

Locally semicomplete digraphs that are complementary m-pancyclic

If A and B are two subdigraphs of D, then we denote by d_D (A, B) the distance between A and B. Let D be a 2-connected locally semicomplete digraph on n ≥ 6 vertices. If S is a minimum separating set of D and then m = max{3, d + 2} ≤ n/2 and D contains two vertex-disjoint dicycles of lengths t and n − t for every integer t satisfying m ≤ t ≤ n/2, unless D is a member of a family of locally semicomplete digraphs. This result extends those of Reid (Ann. Discrete Math. 27 (1985), 321–334) and Song (J. Combin. Theory B 57 (1993), 18–25) for tournaments, and it confirms two conjectures of Bang-Jensen (Discrete Math. 100 (1992), 243–265. © 1996 John Wiley & Sons, Inc.     

The inducibility of complete bipartite graphs

For any s ≥ 1 and t ≥ (^S₂), we prove that among all graphs with n vertices the graph that contains the maximal number of induced copies of K_{t, t+s} for any fixed s ≥ 1 and t ≥ (^s₂) is K_{(n/2)+α(n/2)-α} for some function α = o(n). We show that this is not valid for t < (^s₂). Analogous results for complete multipartite graphs are also obtained.     

Disjoint triangles and quadrilaterals in a graph

Let n, s and t be three integers with s ≥ 1, t ≥ 0 and n = 3s + 4t. Let G be a graph of order n such that the minimum degree of G is at least (n + s)/2. Then G contains a 2-factor with s + t components such that s of them are triangles and t of them are quadrilaterals.      

On decomposition of triangle-free graphs under degree constraints

We prove that if s and t are positive integers and if G is a triangle-free graph with minimum degree s + t, then the vertex set of G has a decomposition into two sets which induce subgraphs of minimum degree at least s and t, respectively. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 7–9, 1998     

A General Theory of Almost Splitting Sets

Let * be a star-operation of finite type on an integral domain D. In this paper, we generalize and study the concept of almost splitting sets. We define a saturated multiplicative subset S of D to be an almost g*-splitting set of D if for each 0 ≠ d ∈ D, there exists an integer n = n(d) ≥1 such that d ⁿ  = st for some s ∈ S and t ∈ D with (t, s′)_* = D for all s′ ∈ S. Among other things, we prove that every saturated multiplicative subset of D is an almost g*-splitting set if and only if D is an almost weakly factorial domain (AWFD) with *-dim (D) = 1. We also give an example of an almost g*-splitting set which is not a g*-splitting set.     

Decreasing the diameter of bounded degree graphs

Let f_d (G) denote the minimum number of edges that have to be added to a graph G to transform it into a graph of diameter at most d. We prove that for any graph G with maximum degree D and n > n₀ (D) vertices, f₂(G) = n − D − 1 and f₃(G) ≥ n − O(D³). For d ≥ 4, f_d (G) depends strongly on the actual structure of G, not only on the maximum degree of G. We prove that the maximum of f_d (G) over all connected graphs on n vertices is n/⌊d/2 ⌋ − O(1). As a byproduct, we show that for the n‐cycle C_n, f_d (C_n) = n/(2⌊d/2 ⌋ − 1) − O(1) for every d and n, improving earlier estimates of Chung and Garey in certain ranges. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 161–172, 2000     

Directed star decompositions of the complete directed graph

An (s, t)-directed star is a directed graph with s + t + 1 vertices and s + t arcs; s vertices have indegree zero and outdegree one, t have indegree one and outdegree zero, and one has indegree s and outdegree t. An (s, t)-directed star decomposition is a partition of the arcs of a complete directed graph of order n into (s, t)-directed starsx. We establish necessary and sufficient conditions on s, t, and n for an (s, t)-directed star decomposition of order n to exist.     

Independent Directed Triangles in a Directed Graph

If D is a directed graph of order n≥3 with , then D contains independent directed triangles. Moreover, the condition on the minimum degree is sharp in general. Revised: April 19, 1999     

Component structure of the vacant set induced by a random walk on a random graph

We consider random walks on several classes of graphs and explore the likely structure of the vacant set, i.e. the set of unvisited vertices. Let Γ(t) be the subgraph induced by the vacant set of the walk at step t. We show that for random graphs G_n,p (above the connectivity threshold) and for random regular graphs G_r,r ≥ 3, the graph Γ(t) undergoes a phase transition in the sense of the well‐known ErdJW‐RSAT1100590x.png ‐Renyi phase transition. Thus for t ≤ (1 ‐ ε)t^*, there is a unique giant component, plus components of size O(log n), and for t ≥ (1 + ε)t^* all components are of size O(log n). For G_n,p and G_r we give the value of t^*, and the size of Γ(t). For G_r, we also give the degree sequence of Γ(t), the size of the giant component (if any) of Γ(t) and the number of tree components of Γ(t) of a given size k = O(log n). We also show that for random digraphs D_n,p above the strong connectivity threshold, there is a similar directed phase transition. Thus for t ≤ (1 ‐ ε)t^*, there is a unique strongly connected giant component, plus strongly connected components of size O(log n), and for t ≥ (1 + ε)t^* all strongly connected components are of size O(log n). © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Diameter vulnerability of graphs

Let f(t, D) denote the maximum possible diameter of a graph obtained from a (t+1)-edge-connected graph of diameter D by deleting t edges. F.R.K. Chung and M.R. Garey have shown that for D≥4,(t+1)(D?2)≤ f(t, D)≤(t+1)D+t. Here we consider the cases D=2 and D=3 and show that f(t,2)=4 and $\text{3}\text{2t}\text{?3≤f(t,3)≤3}\text{2t}\text{+4}$ if t is large enough. We solve also the problem for the directed case (answering a question of F.R.K. Chung and M.R. Garey) by showing that if D ≥ 3 the diameter of a diagraph obtained from a (t + 1)-arc-connected digraph of order n by deleting t arcs is at most n?2t+1. In the case D=.....2, the maximum possible diameter of the resulting digraph is (like in the undirected case) 4. We also consider the same problem for vertices.     

Constructions of Spherical 3-Designs

 Spherical t-designs are Chebyshev-type averaging sets on the d-sphere which are exact for polynomials of degree at most t. This concept was introduced in 1977 by Delsarte, Goethals, and Seidel, who also found the minimum possible size of such designs, in particular, that the number of points in a 3-design on S ^d must be at least . In this paper we give explicit constructions for spherical 3-designs on S ^d consisting of n points for d=1 and ; d=2 and ; d=3 and ; d=4 and ; and odd or even. We also provide some evidence that 3-designs of other sizes do not exist. We will introduce and apply a concept from additive number theory generalizing the classical Sidon-sequences. Namely, we study sets of integers S for which the congruence mod n, where and , only holds in the trivial cases. We call such sets Sidon-type sets of strength t, and denote their maximum cardinality by s(n, t). We find a lower bound for s(n, 3), and show how Sidon-type sets of strength 3 can be used to construct spherical 3-designs. We also conjecture that our lower bound gives the true value of s(n, 3) (this has been verified for n≤125). Received: June 19, 1996     

Two vertex-disjoint cycles in a graph

LetG be a graph of ordern 6 with minimum degree at least (n + 1)/2. Then, for any two integerss andt withs 3,t 3 ands + t n, G contains two vertex-disjoint cycles of lengthss andt, respectively, unless thatn, s andt are odd andG is isomorphic toK _{(n–1)/2,(n–1)/2} + K₁. We also show that ifG is a graph of ordern 8 withn even and minimum degree at leastn/2, thenG contains two vertex-disjoint cycles with any given even lengths provided that the sum of the two lengths is at mostn.     

A note on vertex pancyclic oriented graphs

Let D be an oriented graph of order n ≥ 9, minimum degree at least n − 2, such that, for the choice of distinct vertices x and y, either xy ∈ E(D) or d⁺(x) + d⁻(y) ≥ n − 3. Song (J. Graph Theory 18 (1994), 461–468) proved that D is pancyclic. In this note, we give a short proof, based on Song's result, that D is, in fact, vertex pancyclic. This also generalizes a result of Jackson (J. Graph Theory 5 (1981), 147–157) for the existence of a hamiltonian cycle in oriented graphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 313–318, 1999     

Distance connectivity in graphs and digraphs

Let G = (V, A) be a digraph with diameter D ≠ 1. For a given integer 2 ≤ t ≤ D, the t-distance connectivity κ(t) of G is the minimum cardinality of an x → y separating set over all the pairs of vertices x, y which are at distance d(x, y) ≥ t. The t-distance edge connectivity λ(t) of G is defined similarly. The t-degree of G, δ(t), is the minimum among the out-degrees and in-degrees of all vertices with (out- or -in-) eccentricity at least t. A digraph is said to be maximally distance connected if κ(t) = δ(t) for all values of t. In this paper we give a construction of a digraph having D − 1 positive arbitrary integers c₂ ≤ … ≤ c_D, D > 3, as the values of its t-distance connectivities κ(2) = c₂, …, κ(D) = c_D. Besides, a digraph that shows the independence of the parameters κ(t), λ(t), and δ(t) is constructed. Also we derive some results on the distance connectivities of digraphs, as well as sufficient conditions for a digraph to be maximally distance connected. Similar results for (undirected) graphs are presented. © 1996 John Wiley & Sons, Inc.     

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     

Disproof of a conjecture about independent branchings in k-connected directed graphs

For each k ≥ 3, we construct a finite directed strongly k-connected graph D containing a vertex t with the following property: For any k spanning t-branchings, B₁, …, B_k in D (i. e., each B_i is a spanning tree in D directed toward t), there exists a vertex x ≠ t of D such that the k, x, t-paths in B₁, …, B_k are not pairwise openly disjoint. This disproves a well-known conjecture of Frank. © 1995, John Wiley & Sons, Inc.     

A linear Vizing‐like relation relating the size and total domination number of a graph

We prove that m ≤ Δ (n ? γ_t) for every graph each component of which has order at least 3 of order n, size m, total domination number γ_t, and maximum degree Δ ≥ 3. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 285–290, 2005