The maximum number of Hamiltonian paths in tournaments

Solving an old conjecture of Szele we show that the maximum number of directed Hamiltonian paths in a tournament onn vertices is at mostc · n ^3/2 · n!/2 ^n–1, wherec is a positive constant independent ofn.Research supported in part by a U.S.A.-Israel BSF grant and by a Bergmann Memorial Grant.     

Multiplicativity of acyclic local tournaments

A homomorphism of a digraph to another digraph is an edge-preserving vertex mapping. A digraphH is said to be multiplicative if the set of digraphs which do not admit a homomorphism toH is closed under categorical product. In this paper we discuss the multiplicativity of acyclic Hamiltonian digraphs, i.e., acyclic digraphs which contains a Hamiltonian path. As a consequence, we give a complete characterization of acyclic local tournaments with respect to multiplicativity.     

Polynomial time algorithms for recognizing and isomorphism testing of cyclic tournaments

In [3] the problem of finding an efficient criterion for isomorphism testing of cyclic graphs was posed. In the context of the theory of computational complexity the problem reduces to that of the existence of a polynomial-time algorithm for recognizing their isomorphism. The main result of the present paper is an algorithm for finding among all tournaments the cyclic ones. For cyclic tournaments generators of the automorphism group and the set of canonical labels are constructed. The running time of the algorithm is bounded by a polynomial function of the number of input tournament vertices. Thus an affirmative answer to the above problem is obtained.     

Cycles throughk vertices in bipartite tournaments

We give a simple proof that everyk-connected bipartite tournament has a cycle through every set ofk vertices. This was conjectured in [4].This research was done while the first author was visiting Laboratoire de Recherche en Informatique, universite Paris-Sud whose hospitality and financial support is gratefully acknowledged     

On infinite tournaments with regular automorphism groups

Atournament regular representation (TRR) of an abstract groupG is a tournamentT whose automorphism group is isomorphic toG and is a regular permutation group on the vertices ofT. L. Babai and W. Imrich have shown that every finite group of odd order exceptZ ₃ ×Z ₃ admits a TRR. In the present paper we give several sufficient conditions for an infinite groupG with no element of order 2 to admit a TRR. Among these are the following: (1)G is a cyclic extension byZ of a finitely generated group; (2)G is a cyclic extension byZ _2n+1 of any group admitting a TRR; (3)G is a finitely generated abelian group; (4)G is a countably generated abelian group whose torsion subgroup is finite.     

The asymptotic numbers of regular tournaments,Eulerian digraphs and Eulerian oriented graphs

LetRT(n), ED(n) andEOG(n) be the number of labelled regular tournaments, labelled loop-free simple Eulerian digraphs, and labelled Eulerian oriented simple graphs, respectively, onn vertices. Then, asn,, for any>0. The last two families of graphs are also enumerated by their numbers of edges. The proofs use the saddle point method applied to appropriaten-dimensional integrals.     

A lower bound for the recognition of digraph properties

The complexity of a digraph property is the number of entries of the adjacency matrix which must be examined by a decision tree algorithm to recognize the property in the worst case, Aanderaa and Rosenberg conjectured that there is a constant such that every digraph property which is monotone (not destroyed by the deletion of edges) and nontrivial (holds for some but not all digraphs) has complexity at leastv ² wherev is the number of nodes in the digraph. This conjecture was proved by Rivest and Vuillemin and a lower bound ofv ²/4–o(v ²) was subsequently found by Kahn, Saks, and Sturtevant. Here we show a lower bound ofv ²/2–o(v ²). We also prove that a certain class of monotone, nontrivial bipartite digraph properties is evasive (requires that every entry in the adjacency matrix be examined in the worst case).     

The convexity spectra of graphs

Let D be a connected oriented graph. A set S⊆V(D) is convex in D if, for every pair of vertices x,y∈S, the vertex set of every x-y geodesic (x-y shortest dipath) and y-x geodesic in D is contained in S. The convexity numbercon(D) of a nontrivial oriented graph D is the maximum cardinality of a proper convex set of D. Let G be a graph. We define that S_C(G)={con(D):D is an orientation of G} and S_SC(G)={con(D):D is a strongly connected orientation of G}. In the paper, we show that, for any n?4, 1?a?n-2, and a≠2, there exists a 2-connected graph G with n vertices such that S_C(G)=S_SC(G)={a,n-1} and there is no connected graph G of order n?3 with S_SC(G)={n-1}. Then, we determine that S_C(K₃)={1,2}, S_C(K₄)={1,3}, S_SC(K₃)=S_SC(K₄)={1}, S_C(K₅)={1,3,4}, S_C(K₆)={1,3,4,5}, S_SC(K₅)=S_SC(K₆)={1,3}, S_C(K_n)={1,3,5,6,…,n-1}, S_SC(K_n)={1,3,5,6,…,n-2} for n?7. Finally, we prove that, for any integers n, m, and k with , 1?k?n-1, and k≠2,4, there exists a strongly connected oriented graph D with n vertices, m edges, and convexity number k.     

The game of arboricity

Using a fixed set of colors C, Ann and Ben color the edges of a graph G so that no monochromatic cycle may appear. Ann wins if all edges of G have been colored, while Ben wins if completing a coloring is not possible. The minimum size of C for which Ann has a winning strategy is called the game arboricity of G, denoted by A_g(G). We prove that A_g(G)?3k for any graph G of arboricity k, and that there are graphs such that A_g(G)?2k-2. The upper bound is achieved by a suitable version of the activation strategy, used earlier for the vertex coloring game. We also provide two other strategies based on induction and acyclic colorings.     

Lower bounds for the game colouring number of partial k-trees and planar graphs

This paper discusses the game colouring number of partial k-trees and planar graphs. Let col_g(PT_k) and col_g(P) denote the maximum game colouring number of partial k trees and the maximum game colouring number of planar graphs, respectively. In this paper, we prove that col_g(PT_k)=3k+2 and col_g(P)?11. We also prove that the game colouring number col_g(G) of a graph is a monotone parameter, i.e., if H is a subgraph of G, then col_g(H)?col_g(G).     

Related solution operators in mathematical physics

Transmutation operators are derived relating many of the frequently encountered linear partial differential equations in mathematical physics. The setting for this study is vector-valued distributions. Examples are given showing how fundamental solutions are derived for both homogeneous and nonhomogeneous partial differential equations.     

A note on the girth of digraphs

Behzad, Chartrand and Wall conjectured that the girth of a diregular graph of ordern and outdegreer is not greater than [n /r]. This conjecture has been proved forr=2 by Behzad and forr=3 by Bermond. We prove that a digraph of ordern and halfdegree ≧4 has girth not exceeding [n / 4]. We also obtain short proofs of the above results. Our method is an application of the theory of connectivity of digraphs.     

On the Szeged and the Laplacian Szeged spectrum of a graph

For a given graph G its Szeged weighting is defined by w(e)=n_u(e)n_v(e), where e=uv is an edge of G,n_u(e) is the number of vertices of G closer to u than to v, and n_v(e) is defined analogously. The adjacency matrix of a graph weighted in this way is called its Szeged matrix. In this paper we determine the spectra of Szeged matrices and their Laplacians for several families of graphs. We also present sharp upper and lower bounds on the eigenvalues of Szeged matrices of graphs.     

On the solutions of the Cauchy problem for a class of partial differential equations with double characteristic at a point

We give an explicit representation of the solutions of the Cauchy problem, in terms of series of hypergeometric functions, for the following class of partial differential equations with double characteristic at the origin:

(xkt_∂+ax_∂)(xkt_∂+bx_∂)u+cxk−1t_∂u=0,     

On the pebbling threshold of paths and the pebbling threshold spectrum

A configuration of pebbles on the vertices of a graph is solvable if one can place a pebble on any given root vertex via a sequence of pebbling steps. A function is a pebbling threshold for a sequence of graphs if a randomly chosen configuration of asymptotically more pebbles is almost surely solvable, while one of asymptotically fewer pebbles is almost surely not. In this paper we tighten the gap between the upper and lower bounds for the pebbling threshold for the sequence of paths in the multiset model. We also find the pebbling threshold for the sequence of paths in the binomial model. Finally, we show that the spectrum of pebbling thresholds for graph sequences in the multiset model spans the entire range from n^1/2 to n, answering a question of Czygrinow, Eaton, Hurlbert and Kayll. What the spectrum looks like above n remains unknown.     

Explicit construction of regular graphs without small cycles

For every integerd>2 we give an explicit construction of infinitely many Cayley graphsX of degreed withn(X) vertices and girth >0.4801...(logn(X))/log (d−1)−2. This improves a result of Margulis. Dedicated to Paul Erdős on his seventieth birthday     

Intersecting sperner families and their convex hulls

Let ℱ be a family of subsets of a finite set ofn elements. The vector (f ₀, ...,f _n ) is called the profile of ℱ wheref _i denotes the number ofi-element subsets in ℱ. Take the set of profiles of all families ℱ satisfyingF ₁⊄F ₂ andF ₁∩F ₂≠0 for allF ₁,F ₂teℱ. It is proved that the extreme points of this set inR ⁿ⁺¹ have at most two non-zero components. Dedicated to Paul Erdős on his seventieth birthday     

Extremal hypergraph problems and convex hulls

Theprofile of a hypergraph onn vertices is (f ₀, f₁, ...,f _n) wheref _i denotes the number ofi-element edges. The extreme points of the set of profiles is determined for certain hypergraph classes. The results contain many old theorems of extremal set theory as particular cases (Sperner. Erdős—Ko—Rado, Daykin—Frankl—Green—Hilton).     

Colorful Isomorphic Spanning Trees in Complete Graphs

Can a complete graph on an even number n (> 4) of vertices be properly edge-colored with n − 1 colors in such a way that the edges can be partitioned into edge-disjoint colorful isomorphic spanning trees? A spanning treee is colorful if all n − 1 colors occur among its edges. It is proved that this is possible to accomplish whenever n is a power of two.Received July 24, 2001