List multicoloring problems involving the k‐fold Hall numbers

We show that the four‐cycle has a k‐fold list coloring if the lists of colors available at the vertices satisfy the necessary Hall's condition, and if each list has length at least ?5k/3?; furthermore, the same is not true with shorter list lengths. In terms of h^(k)(G), the k ‐fold Hall number of a graph G, this result is stated as h^(k)(C₄)=2k??k/3?. For longer cycles it is known that h^(k)(C_n)=2k, for n odd, and 2k??k/(n?1)?≤h^(k)(C_n)≤2k, for n even. Here we show the lower bound for n even, and conjecture that this is the right value (just as for C₄). We prove that if G is the diamond (a four‐cycle with a diagonal), then h^(k)(G)=2k. Combining these results with those published earlier we obtain a characterization of graphs G with h^(k)(G)=k. As a tool in the proofs we obtain and apply an elementary generalization of the classical Hall–Rado–Halmos–Vaughan theorem on pairwise disjoint subset representatives with prescribed cardinalities. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 16–34, 2010.     

Classification of Groups Which Admit a Finite Number of Distinct Right-Orders

Tararin has shown that a non-Abelian group G admits a nonzero finite number of distinct right-orders if and only if G is equipped with a Tararin-type series of some length n. Further, a group which has a Tararin-type series of length n admits 2 ⁿ right-orders. It is known that a group has two right-orders if and only if it is torsionfree Abelian of rank 1. Here we completely classify the groups which admit either four or eight right-orders.     

Finding large cycles in Hamiltonian graphs

We show how to find in Hamiltonian graphs a cycle of length n^{Ω(1/loglogn)}=exp(Ω(logn/loglogn)). This is a consequence of a more general result in which we show that if G has a maximum degree d and has a cycle with k vertices (or a 3-cyclable minor H with k vertices), then we can find in O(n³) time a cycle in G of length k^Ω(1/logd). From this we infer that if G has a cycle of length k, then one can find in O(n³) time a cycle of length k^{Ω(1/(log(n/k)+loglogn))}, which implies the result for Hamiltonian graphs. Our results improve, for some values of k and d, a recent result of Gabow (2004) [11] showing that if G has a cycle of length k, then one can find in polynomial time a cycle in G of length . We finally show that if G has fixed Euler genus g and has a cycle with k vertices (or a 3-cyclable minor H with k vertices), then we can find in polynomial time a cycle in G of length f(g)k^Ω(1), running in time O(n²) for planar graphs.     

Even Cycles in Graphs with Many Odd Cycles

It will be shown that if G is a graph of order n which contains a triangle, a cycle of length n or n−1 and at least cn odd cycles of different lengths for some positive constant c, then there exists some positive constant k=k(c) such that G contains at least kn ^1/6 even cycles of different lengths. Other results on the number of even cycle lengths which appear in graphs with many different odd length cycles will be given. Received: October 15, 1997     

On B(5, 18) Groups

A group G is said to be a B(n, k) group if for any n-element subset A of G, |A²| ≤k. In this paper, a characterization of B(5, 18) groups is given. It is shown that G is a B(5, 18) group if and only if one of the following statements holds: (1) G is abelian; (2) |G| ≤18; (3) G ? ? a, b | a⁵ = b⁴ = 1, a^b = a^?1 ?.     

Some results on generalized exponents

A digraph G = (V, E) is primitive if, for some positive integer k, there is a u → v walk of length k for every pair u, v of vertices of V. The minimum such k is called the exponent of G, denoted exp(G). The exponent of a vertex u ∈ V, denoted exp(u), is the least integer k such that there is a u → v walk of length k for each v ∈ V. For a set X ⊆ V, exp(X) is the least integer k such that for each v ∈ V there is a X → v walk of length k, i.e., a u → v walk of length k for some u ∈ X. Let F(G, k) : = max{exp(X) : |X| = k} and F(n, k) : = max{F(G, k) : |V| = n}, where |X| and |V| denote the number of vertices in X and V, respectively. Recently, B. Liu and Q. Li proved F(n, k) = (n − k)(n − 1) + 1 for all 1 ≤ k ≤ n − 1. In this article, for each k, 1 ≤ k ≤ n − 1, we characterize the digraphs G such that F(G, k) = F(n, k), thereby answering a question of R. Brualdi and B. Liu. We also find some new upper bounds on the (ordinary) exponent of G in terms of the maximum outdegree of G, Δ⁺(G) = max{d⁺(u) : u ∈ V}, and thus obtain a new refinement of the Wielandt bound (n − 1)² + 1. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 215–225, 1998     

The longest cycle of a graph with a large minimal degree

We show that every graph G on n vertices with minimal degree at least n/k contains a cycle of length at least [n/(k ? 1)]. This verifies a conjecture of Katchalski. When k = 2 our result reduces to the classical theorem of Dirac that asserts that if all degrees are at least 1/2n then G is Hamiltonian.     

Matching extension in the powers of n-connected graphs

Let G be a graph on p vertices. Then for a positive integer n₁ G is said to be n-extendible if (i) n < p/2, (ii) G has a set of n independent edges, and (iii) every such set is contained in a perfect matching of G. In this paper we will show that if p is even and G is n-connected, then G^k is -extendible for every integer k ≥ 2 such that . © 1996 John Wiley & Sons, Inc.     

Linear arboricity for graphs with multiple edges

Akiyama, Exoo, and Harary conjectured that for any simple graph G with maximum degree Δ(G), the linear arboricity la(G) satisfies ?Δ(G)/2? ≦ la(G) ≦ ?(Δ(G) + 1)/2?. Here it is proved that if G is a loopless graph with maximum degree Δ(G) ≦ k and maximum edge multiplicity μ(G) ≦ k ? 2ⁿ⁺¹ + 1, where k ≧ 2^n?2, then la(G) ≦ k ? 2ⁿ. It is also conjectured that for any loopless graph G, ?Δ(G)/2? ≦ la(G) ≦ ?(Δ(G) + μ(G))/2?.     

Hamiltonicity of regular 2-connected graphs

Let G be a k-regular 2-connected graph of order n. Jackson proved that G is hamiltonian if n ≤ 3k. Zhu and Li showed that the upper bound 3k on n can be relaxed to 22/7k if G is 3-connected and k ≥ 63. We improve both results by showing that G is hamiltonian if n ≤ 7/2k − 7 and G does not belong to a restricted class F of nonhamiltonian graphs of connectivity 2. To establish this result we obtain a variation of Woodall's Hopping Lemma and use it to prove that if n ≤ 7/2k − 7 and G has a dominating cycle (i.e., a cycle such that the vertices off the cycle constitute an independent set), then G is hamiltonian. We also prove that if n ≤ 4k − 3 and G ∉ F, then G has a dominating cycle. For k ≥ 4 it is conjectured that G is hamiltonian if n ≤ 4k and G ∉ F. © 1996 John Wiley & Sons, Inc.     

The structure of digraphs associated with the congruence <Emphasis Type="Italic">x</Emphasis><Superscript><Emphasis Type="Italic">k</Emphasis></Superscript> ≡ <Emphasis Type="Italic">y</Emphasis> (mod <Emphasis Type="Italic">n</Emphasis>)

We assign to each pair of positive integers n and k ⩾ 2 a digraph G(n, k) whose set of vertices is H = {0, 1, ..., n − 1} and for which there is a directed edge from a ∈ H to b ∈ H if a ^k ≡ b (mod n). We investigate the structure of G(n, k). In particular, upper bounds are given for the longest cycle in G(n, k). We find subdigraphs of G(n, k), called fundamental constituents of G(n, k), for which all trees attached to cycle vertices are isomorphic.     

A New Criterion for Finite Noncyclic Groups

Let H be a subgroup of a group G. We say that H satisfies the power condition with respect to G, or H is a power subgroup of G, if there exists a non-negative integer m such that H = G ^m  = 〈 g ^m |g ? G 〉. In this note, the following theorem is proved: Let G be a group and k the number of nonpower subgroups of G. Then (1) k = 0 if and only if G is a cyclic group (theorem of F. Szász); (2) 0 < k < ∞ if and only if G is a finite noncyclic group; (3) k = ∞ if and only if G is a infinte noncyclic group. Thus we get a new criterion for the finite noncyclic groups.     

On the Pósa-Seymour conjecture

Paul Seymour conjectured that any graph G of order n and minimum degree at least contains the k^th power of a Hamilton cycle. We prove the following approximate version. For any ϵ ≥ 0 and positive integer k, there is an n₀ such that, if G has order n ≥ n₀ and minimum degree at least $(\frac{k}{k+1} + \epsilon )n$, then G contains the k^th power of a Hamilton cycle. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 167–176, 1998     

Packing in regular graphs

A set S of vertices in a graph G is a packing if the vertices in S are pairwise at distance at least 3 apart in G. The packing number of G, denoted by ρ(G), is the maximum cardinality of a packing in G. Favaron [Discrete Math. 158 (1996), 287–293] showed that if G is a connected cubic graph of order n different from the Petersen graph, then ρ(G) ≥ n/8. In this paper, we generalize Favaron’s result. We show that for k ≥ 3, if G is a connected k-regular graph of order n that is not a diameter-2 Moore graph, then ρ(G) ≥ n/(k² ? 1).     

Structures and Chromaticity of Extremal 3-Colourable Sparse Graphs

 Assume that G is a 3-colourable connected graph with e(G) = 2v(G) −k, where k≥ 4. It has been shown that s ₃(G) ≥ 2 ^{k −3}, where s _r (G) = P(G,r)/r! for any positive integer r and P(G, λ) is the chromatic polynomial of G. In this paper, we prove that if G is 2-connected and s ₃(G) < 2 ^{k −2}, then G contains at most v(G) −k triangles; and the upper bound is attained only if G is a graph obtained by replacing each edge in the k-cycle C _k by a 2-tree. By using this result, we settle the problem of determining if W(n, s) is χ-unique, where W(n, s) is the graph obtained from the wheel W _n by deleting all but s consecutive spokes. Received: January 29, 1999 Final version received: April 8, 2000     

Nonsoluble length of finite groups with restrictions on Sylow subgroups

By 𝔛(n) we denote the variety of all groups satisfying the law [x,y]ⁿ≡1, that is, groups with commutators of order dividing n. Let p be a prime and G a finite group whose Sylow p-subgroups have normal series of length k all of whose quotients belong to 𝔛(n). We show that the non-p-soluble length λ_p(G) of G is bounded in terms of k and n only (Theorem 1.2). In the case where p is odd, a stronger result is obtained (Theorem 1.3).     

Vertex‐disjoint cycles containing prescribed vertices

Enomoto 7 conjectured that if the minimum degree of a graph G of order n ≥ 4k ? 1 is at least the integer , then for any k vertices, G contains k vertex‐disjoint cycles each of which contains one of the k specified vertices. We confirm the conjecture for n ≥ ck² where c is a constant. Furthermore, we show that under the same condition the cycles can be chosen so that each has length at most six. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 276–296, 2003     

Euler Tours of Maximum Girth in K2 n +1 and K2 n ,2 n

Given an eulerian graph G and an Euler tour T of G, the girth of T, denoted by g(T), is the minimum integer k such that some segment of k+1 consecutive vertices of T is a cycle of length k in G. Let g^E(G)= maxg(T) where the maximum is taken over all Euler tours of G.We prove that g^E(K_2n,2n)=4n–4 and 2n–3g^E(K_2n+1)2n–1 for any n2. We also show that g^E(K₇)=4. We use these results to prove the following:1)The graph K_2n,2n can be decomposed into edge disjoint paths of length k if and only if k4n–1 and the number of edges in K_2n,2n is divisible by k.2)The graph K_2n+1 can be decomposed into edge disjoint paths of length k if and only if k2n and the number edges in K_2n+1 is divisible by k.     

Reflection sieve obstructions in finite groups of type dn

In [4] we constructed certain homology representations of a finite group G of type A_n, B_n or C_n, and showed that these representations can be used to sift out the reflection compound characters of G. In the present note, we show that for a group G of type D_n, each reflection compound character π^(k), 2 k n − 2, determines a unique “obstruction” character θ^(k), which occurs with positive multiplicity in every homology representation containing π^(k).     

Edge disjoint Hamilton cycles in sparse random graphs of minimum degree at least k

Let G_n,m,k denote the space of simple graphs with n vertices, m edges, and minimum degree at least k, each graph G being equiprobable. Let G have property A_k, if G contains ⌊(k − 1)/2⌋ edge disjoint Hamilton cycles, and, if k is even, a further edge disjoint matching of size ⌊n/2⌋. We prove that, for k ≥ 3, there is a constant C_k such that if 2m ≥ C_kn then A_k occurs in G_n,m,k with probability tending to 1 as n → ∞. © 2000 John Wiley & Sons, Inc. J. Graph Theory 34: 42–59, 2000