On packing 3‐vertex paths in a graph

Let G be a connected graph and let eb(G) and λ(G) denote the number of end‐blocks and the maximum number of disjoint 3‐vertex paths Λ in G. We prove the following theorems on claw‐free graphs: (t1) if G is claw‐free and eb(G) ≤ 2 (and in particular, G is 2‐connected) then λ(G) = ⌊| V(G)|/3⌋; (t2) if G is claw‐free and eb(G) ≥ 2 then λ(G) ≥ ⌊(| V(G) | − eb(G) + 2)/3 ⌋; and (t3) if G is claw‐free and Δ^*‐free then λ(G) = ⌊| V(G) |/3⌋ (here Δ^* is a graph obtained from a triangle Δ by attaching to each vertex a new dangling edge). We also give the following sufficient condition for a graph to have a Λ‐factor: Let n and p be integers, 1 ≤ p ≤ n − 2, G a 2‐connected graph, and |V(G)| = 3n. Suppose that G − S has a Λ‐factor for every S ⊆ V(G) such that |S| = 3p and both V(G) − S and S induce connected subgraphs in G. Then G has a Λ‐factor. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 175–197, 2001     

Long paths through four vertices in a 2‐connected graph

Let G be a 2‐connected graph, let u and v be distinct vertices in V(G), and let X be a set of at most four vertices lying on a common (u, v)‐path in G. If deg(x) ≥ d for all x ∈ V(G) \ {u, v}, then there is a (u, v)‐path P in G with X ⊂ V(P) and |E(P)| ≥ d. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 55–65, 2000     

Graph diameter in long‐range percolation

We study the asymptotic growth of the diameter of a graph obtained by adding sparse “long” edges to a square box in ${\mathbb Z}^dWe study the asymptotic growth of the diameter of a graph obtained by adding sparse “long” edges to a square box in ${\mathbb Z}^d$. We focus on the cases when an edge between x and y is added with probability decaying with the Euclidean distance as |x ? y|^?s+o(1) when |x ? y| → ∞. For s ∈ (d, 2d) we show that the graph diameter for the graph reduced to a box of side L scales like (log L)^Δ+o(1) where Δ^?1 := log₂(2d/s). In particular, the diameter grows about as fast as the typical graph distance between two vertices at distance L. We also show that a ball of radius r in the intrinsic metric on the (infinite) graph will roughly coincide with a ball of radius exp{r^1/Δ+o(1)} in the Euclidean metric. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 39, 210‐227, 2011     

Subdivisions of large complete bipartite graphs and long induced paths in k‐connected graphs

It is proved that for every positive integers k, r and s there exists an integer n = n(k,r,s) such that every k‐connected graph of order at least n contains either an induced path of length s or a subdivision of the complete bipartite graph K_k,r. © 2004 Wiley Periodicals, Inc. J Graph Theory 45: 270–274, 2004     

Near‐automorphisms of paths

The total relative displacement of a permutation f of vertices of a connected graph G is , where the sum is taken over all unordered pairs of distinct vertices of G. Let π(G) denote the smallest positive value of δ_f(G) among the n! permutations f. Aitken [J Combin Theory Series A 87 (1999), 1–21] proved that π(P_n) = 2n ? 4 for the n‐path P_n, which was conjectured by Chartrand et al. [Proceedings of the 1996 Eighth Quadrennial International Conference on Graph Theory, Combinatorics Algorithms, and Applications I, New Issues Press, Kalamazoo, 1999, pp. 181–192]. This article gives a short proof of the result. © 2011 Wiley Periodicals, Inc. J Graph Theory 68:323‐325, 2011     

On perfect Γ‐decompositions of the complete graph

Generalizing the well‐known concept of an i‐perfect cycle system, Pasotti [Pasotti, in press, Australas J Combin] defined a Γ‐decomposition (Γ‐factorization) of a complete graph K_v to be i‐perfect if for every edge [x, y] of K_v there is exactly one block of the decomposition (factor of the factorization) in which x and y have distance i. In particular, a Γ‐decomposition (Γ‐factorization) of K_v that is i‐perfect for any i not exceeding the diameter of a connected graph Γ will be said a Steiner (Kirkman) Γ‐system of order v. In this article we first observe that as a consequence of the deep theory on decompositions of edge‐colored graphs developed by Lamken and Wilson [Lamken and Wilson, 2000, J Combin Theory Ser A 89, 149–200], there are infinitely many values of v for which there exists an i‐perfect Γ‐decomposition of K_v provided that Γ is an i‐equidistance graph, namely a graph such that the number of pairs of vertices at distance i is equal to the number of its edges. Then we give some concrete direct constructions for elementary abelian Steiner Γ‐systems with Γ the wheel on 8 vertices or a circulant graph, and for elementary abelian 2‐perfect cube‐factorizations. We also present some recursive constructions and some results on 2‐transitive Kirkman Γ‐systems. © 2008 Wiley Periodicals, Inc. J Combin Designs 17: 197–209, 2009     

The depression of a graph and the diameter of its line graph

An edge ordering of a graph G=(V,E) is an injection f:E→Q⁺ where Q⁺ is the set of positive rational numbers. A (simple) path λ for which f increases along its edge sequence is an f-ascent, and a maximal f-ascent if it is not contained in a longer f-ascent. The depression ε(G) of G is the least integer k such that every edge ordering of G has a maximal ascent of length at most k.It has been shown in [E.J. Cockayne, G. Geldenhuys, P.J.P. Grobler, C.M. Mynhardt, J. van Vuuren, The depression of a graph, Utilitas Math. 69 (2006) 143-160] that the difference may be made arbitrarily large. We prove that the difference can also be arbitrarily large, thus answering a question raised in [E.J. Cockayne, G. Geldenhuys, P.J.P. Grobler, C.M. Mynhardt, J. van Vuuren, The depression of a graph, Utilitas Math. 69 (2006) 143-160].     

New i‐Perfect Cycle Decompositions via Vertex Colorings of Graphs

Generalizing a result by Buratti et al.[M. Buratti, F. Rania, and F. Zuanni, Some constructions for cyclic perfect cycle systems, Discrete Math 299 (2005), 33–48], we present a construction for i‐perfect k‐cycle decompositions of the complete m‐partite graph with parts of size k. These decompositions are sharply vertex‐transitive under the additive group of with R a suitable ring of order m. The construction works whenever a suitable i‐perfect map exists. We show that for determining the set of all triples for which such a map exists, it is crucial to calculate the chromatic numbers of some auxiliary graphs. We completely determine this set except for one special case where is the product of two distinct primes, is even, and . This result allows us to obtain a plethora of new i‐perfect k‐cycle decompositions of the complete graph of order (mod 2k) with k odd. In particular, if k is a prime, such a decomposition exists for any possible i provided that .     

On the complexity of finding paths in a two‐dimensional domain I: Shortest paths

The computational complexity of finding a shortest path in a two‐dimensional domain is studied in the Turing machine‐based computational model and in the discrete complexity theory. This problem is studied with respect to two formulations of polynomial‐time computable two‐dimensional domains: (A) domains with polynomialtime computable boundaries, and (B) polynomial‐time recognizable domains with polynomial‐time computable distance functions. It is proved that the shortest path problem has the polynomial‐space upper bound for domains of both type (A) and type (B); and it has a polynomial‐space lower bound for the domains of type (B), and has a #P lower bound for the domains of type (A). (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Solution of a conjecture of Volkmann on longest paths through an arc in strongly connected in‐tournaments

An in‐tournament is an oriented graph such that the negative neighborhood of every vertex induces a tournament. Let m = 4 or m = 5 and let D be a strongly connected in‐tournament of order such that each arc belongs to a directed path of order at least m. In 2000, Volkmann showed that if D contains an arc e such that the longest directed path through e consists of exactly m vertices, then e is the only arc of D with that property. In this article we shall see that this proposition is true for , thereby validating a conjecture of Volkmann. Furthermore, we prove that if we ease the restrictions on the order of D to , the in‐tournament D in question has at most two such arcs. In doing so, we also give a characterization of the in‐tournaments with exactly two such arcs. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 130–148, 2009     

On a classical theorem on the diameter and minimum degree of a graph

In this work, we obtain good upper bounds for the diameter of any graph in terms of its minimum degree and its order, improving a classical theorem due to Erd¨os, Pach, Pollack and Tuza.We use these bounds in order to study hyperbolic graphs(in the Gromov sense). To compute the hyperbolicity constant is an almost intractable problem, thus it is natural to try to bound it in terms of some parameters of the graph. Let H(n, δ_0) be the set of graphs G with n vertices and minimum degree δ_0, and J(n, Δ) be the set of graphs G with n vertices and maximum degree Δ. We study the four following extremal problems on graphs: a(n, δ_0) = min{δ(G) | G ∈ H(n, δ_0)}, b(n, δ_0) = max{δ(G) |G ∈ H(n, δ_0)}, α(n, Δ) = min{δ(G) | G ∈ J(n, Δ)} and β(n, Δ) = max{δ(G) | G ∈ J(n, Δ)}. In particular, we obtain bounds for b(n, δ_0) and we compute the precise value of a(n, δ_0), α(n, Δ) andβ(n, Δ) for all values of n, δ_0 and Δ, respectively.     

Eigenvalues of the k‐th power of a graph

The k‐th power of a graph G, denoted by , is a graph with the same set of vertices as G such that two vertices are adjacent in if and only if their distance in G is at most k. In this paper, we give the bounds on the spectral radius of and . The Nordhaus–Gaddum‐type inequality for the spectral radius of the graph is also presented. Moreover, we obtain an upper bound on the energy of the second power of graphs.     

Cycles and paths in edge‐colored graphs with given degrees

Sufficient degree conditions for the existence of properly edge‐colored cycles and paths in edge‐colored graphs, multigraphs and random graphs are investigated. In particular, we prove that an edge‐colored multigraph of order n on at least three colors and with minimum colored degree greater than or equal to ?(n+1)/2? has properly edge‐colored cycles of all possible lengths, including hamiltonian cycles. Longest properly edge‐colored paths and hamiltonian paths between given vertices are considered as well. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 63–86, 2010     

On the diameter of a domination dot-critical graph

A graph G is domination dot-critical, or just dot-critical, if contracting any edge decreases the domination number. It is totally dot-critical if identifying any two vertices decreases the domination number. In this paper, we study an open question concerning of the diameter of a domination dot-critical graph G.     

On k‐connectivity for a geometric random graph

For n points uniformly randomly distributed on the unit cube in d dimensions, with d≥2, let ρ_n (respectively, σ_n) denote the minimum r at which the graph, obtained by adding an edge between each pair of points distant at most r apart, is k‐connected (respectively, has minimum degree k). Then P[ρ_n=σ_n]→1 as n→∞. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 15, 145–164, 1999     

Double coverings of 2‐paths by Hamilton cycles*

A double Dudeney set in K_n is a multiset of Hamilton cycles in K_n having the property that each 2‐path in K_n lies in exactly two of the cycles. A double Dudeney set in K_n has been constructed when n ≥ 4 is even. In this paper, we construct a double Dudeney set in K_n when n ≥ 3 is odd. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 195–206, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ) DOI 10.1002/jcd.10003     

On the degree distance of a graph

If G is a connected graph with vertex set V, then the degree distance of G, D^′(G), is defined as , where degw is the degree of vertex w, and d(u,v) denotes the distance between u and v. We prove the asymptotically sharp upper bound for graphs of order n and diameter d. As a corollary we obtain the bound for graphs of order n. This essentially proves a conjecture by Tomescu [I. Tomescu, Some extremal properties of the degree distance of a graph, Discrete Appl. Math. (98) (1999) 159-163].     

Large Cayley graphs and vertex‐transitive non‐Cayley graphs of given degree and diameter

For any d?5 and k?3 we construct a family of Cayley graphs of degree d, diameter k, and order at least k((d?3)/3)^k. By comparison with other available results in this area we show that our family gives the largest currently known Cayley graphs for a wide range of sufficiently large degrees and diameters. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 87–98, 2010     

On weights of induced paths and cycles in claw‐free and K1,r‐free graphs

Let G be a K_1,r ‐free graph (r ≥ 3) on n vertices. We prove that, for any induced path or induced cycle on k vertices in G (k ≥ 2r − 1 or k ≥ 2r, respectively), the degree sum of its vertices is at most (2r − 2)(n − α) where α is the independence number of G. As a corollary we obtain an upper bound on the length of a longest induced path and a longest induced cycle in a K_1,r ‐free graph. Stronger bounds are given in the special case of claw‐free graphs (i.e., r = 3). Sharpness examples are also presented. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 131–143, 2001