On the Circumference of 3-Connected Quasi-Claw-Free Graphs

A graph G is quasi-claw-free if it satisfies the property: d(x,y)=2 ⇒ there exists such that . In the paper, we prove that the circumference of a 3-connected quasi-claw-free graph G on n vertices is at least min{4δ−2,n} and G is hamiltonian if n≤5δ−5.     

New Local Conditions for a Graph to be Hamiltonian

For a vertex w of a graph G the ball of radius 2 centered at w is the subgraph of G induced by the set M₂(w) of all vertices whose distance from w does not exceed 2. We prove the following theorem: Let G be a connected graph where every ball of radius 2 is 2-connected and d(u)+d(v)≥|M₂(w)|−1 for every induced path uwv. Then either G is hamiltonian or for some p≥2 where ∨ denotes join. As a corollary we obtain the following local analogue of a theorem of Nash-Williams: A connected r-regular graph G is hamiltonian if every ball of radius 2 is 2-connected and for each vertex w of G. Supported by the Swedish Research Council (VR)     

An Extremal Problem on Contractible Edges in 3-Connected Graphs

An edge e in a 3-connected graph G is contractible if the contraction G/e is still 3-connected. The existence of contractible edges is a very useful induction tool. Let G be a simple 3-connected graph with at least five vertices. Wu [7] proved that G has at most vertices that are not incident to contractible edges. In this paper, we characterize all simple 3-connected graphs with exactly vertices that are not incident to contractible edges. We show that all such graphs can be constructed from either a single vertex or a 3-edge-connected graph (multiple edges are allowed, but loops are not allowed) by a simple graph operation. Research partially supported by an ONR grant under grant number N00014-01-1-0917     

Minimal Connected τ-Critical Hypergraphs

A hypergraph is τ-critical if τ(−{E})<τ() for every edge E ∈ , where τ() denotes the transversal number of . We show that if is a connected τ-critical hypergraph, then −{E} can be partitioned into τ()−1 stars of size at least two, for every edge E ∈ . An immediate corollary is that a connected τ-critical hypergraph has at least 2τ()−1 edges. This extends, in a very natural way, a classical theorem of Gallai on colour-critical graphs, and is equivalent to a theorem of Füredi on t-stable hypergraphs. We deduce a lower bound on the size of τ-critical hypergraphs of minimum degree at least two.     

The Maximum Size of 3-Wise Intersecting and 3-Wise Union Families

Let be an n-uniform hypergraph on 2n vertices. Suppose that and holds for all F₁,F₂,F₃ ∈ . We prove that the size of is at most . The second author was supported by MEXT Grant-in-Aid for Scientific Research (B) 16340027     

Extremal Problems for Imbalanced Edges

Albertson [2] has introduced the imbalance of an edge e=uv in a graph G as |d_G(u)−d_G(v)|. If for a graph G of order n and size m the minimum imbalance of an edge of G equals d, then our main result states that with equality if and only if G is isomorphic to We also prove best-possible upper bounds on the number of edges uv of a graph G such that |d_G(u)−d_G(v)|≥d for some given d.     

Reconstructing under Group Actions

We give a bound on the reconstructibility of an action GX in terms of the reconstructibility of a the action NX, where N is a normal subgroup of G, and the reconstructibility of the quotient G/N. We also show that if the action GX is locally finite, in the sense that every point is either in an orbit by itself or has finite stabilizer, then the reconstructibility of GX is at most the reconstructibility of G. Finally, we give some applications to geometric reconstruction problems.     

Orthogonal Double Covers of Complete Graphs by Caterpillars of Diameter 5

An orthogonal double cover (ODC) of the complete graph K_n by a graph G is a collection = {G_i|i = 1,2, . . . ,n} of spanning subgraphs of K_n, all isomorphic to G, with the property that every edge of K_n belongs to exactly two members of and any two distinct members of share exactly one edge. A caterpillar of diameter five is a tree arising from a path with six vertices by attaching pendant vertices to some or each of its vertices of degree two. We show that for any caterpillar of diameter five there exists an ODC of the complete graph K_n.     

Largest Non-Unique Subgraphs

The reduction number r(G) of a graph G is the maximum integer m≤|E(G)| such that the graphs G−E, E⊆E(G),|E|≤m, are mutually non-isomorphic, i.e., each graph is unique as a subgraph of G. We prove that and show by probabilistic methods that r(G) can come close to this bound for large orders. By direct construction, we exhibit graphs with large reduction number, although somewhat smaller than the upper bound. We also discuss similarities to a parameter introduced by Erdős and Rényi capturing the degree of asymmetry of a graph, and we consider graphs with few circuits in some detail. Supported by a grant from the Danish Natural Science Research Council.     

-Decompositions of and D v ∪P where P is a 2-Regular Subgraph of D v

In this paper, we extend the study of C₄-decompositions of the complete graph with 2-regular leaves and paddings to directed versions. Mainly, we prove that if P is a vertex-disjoint union of directed cycles in a complete digraph D_v, then and D_v∪P can be decomposed into directed 4-cycles, respectively, if and only if v(v−1)−|E(P)|≡0(mod 4) and v(v−1)+|E(P)|≡0(mod 4) where |E(P)| denotes the number of directed edges of P, and v≥8.     

On the Intersection Problem for Steiner Triple Systems of Different Orders

A Steiner triple system of order v, or STS(v), is a pair (V, ) with V a set of v points and a set of 3-subsets of V called blocks or triples, such that every pair of distinct elements of V occurs in exactly one triple. The intersection problem for STS is to determine the possible numbers of blocks common to two Steiner triple systems STS(u), (U, ), and STS(v), (V, ), with U⊆V. The case where U=V was solved by Lindner and Rosa in 1975. Here, we let U⊂V and completely solve this question for v−u=2,4 and for v≥2u−3. supported by NSERC research grant #OGP0170220. supported by NSERC postdoctoral fellowship. supported by NSERC research grant #OGP007621.     

On Resolvable Multipartite G-Designs II

In this paper, it has been proved that and are factorable, where ⊗ denotes wreath product of graphs. As a consequence, a resolvable (k,n,k,2λ) multipartite –design exists for even k. These results generalize the results of Ushio on –factorizations of complete tripartite graphs.     

Non-Jumping Numbers for 4-Uniform Hypergraphs

Let r≥2 be an integer. A real number α ∈ [0,1) is a jump for r if for any Open image in new window >0 and any integer m, m≥r, any r-uniform graph with n>n₀( Open image in new window ,m) vertices and at least Open image in new window edges contains a subgraph with m vertices and at least Open image in new window edges, where c=c(α) does not depend on Open image in new window and m. It follows from a theorem of Erd?s, Stone and Simonovits that every α ∈ [0,1) is a jump for r=2. Erd?s asked whether the same is true for r≥3. Frankl and Rödl gave a negative answer by showing that Open image in new window is not a jump for r if r≥3 and l>2r. Following a similar approach, we give several sequences of non-jumping numbers generalizing the above result for r=4.     

Almost Symmetric Cycles in Large Digraphs

We prove that every digraph D with n≥7, n≥+6 vertices and at least (n−k−1)(n−1)+k(k+1) arcs contains all symmetric cycles of length at most n−k−2, an almost symmetric cycle of length n−k−1, and with some exceptions, also an almost symmetric cycle of length n−k. Consequently, D contains all orientations of cycles of length at most n−k, unless D is an exception. The research was partially supported by the AGH University of Science and Technology grant No 11 420 04     

Consistent Cycles in Graphs and Digraphs

Let Γ be a finite digraph and let G be a subgroup of the automorphism group of Γ. A directed cycle of Γ is called G-consistent whenever there is an element of G whose restriction to is the 1-step rotation of . Consistent cycles in finite arc-transitive graphs were introduced by J. H. Conway in his public lectures at the Second British Combinatorial Conference in 1971. He observed that the number of G-orbits of G-consistent cycles of an arc-transitive group G is precisely one less than the valency of the graph. In this paper, we give a detailed proof of this result in a more general setting of arbitrary groups of automorphisms of graphs and digraphs. Supported in part by ``Ministrstvo za šolstvo, znanost in šport Republike Slovenije', bilateral project BI-USA/04-05/38.     

A Note on a Packing Problem in Transitive Tournaments

Let TT_n be a transitive tournament on n vertices. We show that for any directed acyclic graph G of order n and of size not greater than two directed graphs isomorphic to G are arc disjoint subgraphs of TT_n. Moreover, this bound is generally the best possible. The research partially supported by KBN grant 2 P03A 016 18     

Inequalities for the Hadamard Weighted Geometric Mean of Positive Kernel Operators on Banach Function Spaces

Let K₁, . . . , K_n be positive kernel operators on a Banach function space. We prove that the Hadamard weighted geometric mean of K₁, . . . , K_n, the operator K, satisfies the following inequalities where || · ||and r(·) denote the operator norm and the spectral radius, respectively. In the case of completely atomic measure space we show some additional results. In particular, we prove an infinite-dimensional extension of the known characterization of those functions satisfying for all non-negative matrices A₁, . . . , A_n of the same order.     

A Five Color Zero-Sum Generalization

Let g_zs(m, 2k) (g_zs(m, 2k+1)) be the minimal integer such that for any coloring Δ of the integers from 1, . . . , g_zs(m, 2k) by (the integers from 1 to g_zs(m, 2k+1) by ) there exist integers such that 1. there exists j_x such that Δ(x_i) ∈ for each i and ∑_i=1^m Δ(x_i) = 0 mod m (or Δ(x_i)=∞ for each i); 2. there exists j_y such that Δ(y_i) ∈ for each i and ∑_i=1^m Δ(y_i) = 0 mod m (or Δ(y_i)=∞ for each i); and 1. 2(x_m−x₁)≤y_m−x₁. In this note we show g_zs(m, 2)=5m−4 for m≥2, g_zs(m, 3)=7m+−6 for m≥4, g_zs(m, 4)=10m−9 for m≥3, and g_zs(m, 5)=13m−2 for m≥2. Supported by NSF grant DMS 0097317     

Colouring Cubic Graphs by Small Steiner Triple Systems

Given a Steiner triple system , we say that a cubic graph G is -colourable if its edges can be coloured by points of in such way that the colours of any three edges meeting at a vertex form a triple of . We prove that there is Steiner triple system of order 21 which is universal in the sense that every simple cubic graph is -colourable. This improves the result of Grannell et al. [J. Graph Theory 46 (2004), 15–24] who found a similar system of order 381. On the other hand, it is known that any universal Steiner triple system must have order at least 13, and it has been conjectured that this bound is sharp (Holroyd and Škoviera [J. Combin. Theory Ser. B 91 (2004), 57–66]). Research partially supported by APVT, project 51-027604. Research partially supported by VEGA, grant 1/3022/06.