Every 3-connected essentially 10-connected line graph is Hamilton-connected

Thomassen conjectured that every 4-connected line graph is Hamiltonian. Lai et al. (in 2006) [5] considered whether the high essential connectivity of the 3-connected line graphs can guarantee the existence of the Hamiltonian cycle in graphs and they showed that every 3-connected, essentially 11-connected line graph is Hamiltonian. In this note, we show that every 3-connected, essentially 10-connected line graph is Hamiltonian-connected. The result strengthens the known result mentioned above.     

A Rogers-Ramanujan bijection

In this paper we give a bijection between the partitions of n with parts congruent to 1 or 4 (mod 5) and the partitions of n with parts differing by at least 2. This bijection is obtained by a cut-and-paste procedure which starts with a partition in one class and ends with a partition in the other class. The whole construction is a combination of a bijection discovered quite early by Schur and two bijections of our own. A basic principle concerning pairs of involutions provides the key for connecting all these bijections. It appears that our methods lead to an algorithm for constructing bijections for other identities of Rogers-Ramanujan type such as the Gordon identities.     

A nine point theorem for 3-connected graphs

We prove that a 3-connected cubic graph contains a cycle through any nine points.     

A bijection of the set of 3-regular partitions

A bijection of the set of 3-regular partitions of an integer n is constructed. It is shown that this map has order 2 and that the 3-cores of a partition and its image have diagrams which are mutual transposes. It is conjectured that this is the same bijection as the one induced, using the labeling of Farahat, Müller, and Peel, from the action of the alternating character upon the 3-modular irreducible representations of the symmetric group of degree n.     

A construction of 3-connected graphs

We show that the 3-connected graphs can be generated from the complete graph on four vertices and the complete 3,3 bipartite graph by adding vertices and adding edges with endpoints on two edges meeting at a 3-valent vertex.     

A bijection for partitions with initial repetitions

A theorem of Andrews equates partitions in which no part is repeated more than 2k−1 times to partitions in which, if j appears at least k times, all parts less than j also do so. This paper proves the theorem bijectively, with some of the generalizations that usually arise from such proofs.     

An inductive definition of cubic toroidal maps

An inductive definition of the class of all cubic toroidal maps will be given. Moreover, it will be demonstrated how this definition can be used to develop an efficient algorithm which constructs all cubic toroidal maps with a limited number of vertices.     

On 3-connected minors of 3-connected matroids and graphs

Whittle proved, for k=1,2, that if N is a 3-connected minor of a 3-connected matroid M, satisfying r(M)−r(N)≥k, then there is a k-independent set I of M such that, for every x∈I, si(M/x) is a 3-connected matroid with an N-minor. In this paper, we establish this result for k=3. It is already known that it cannot be extended to greater values of k. But, here we also show that, in the graphic case, with the extra assumption that r(M)−r(N)≥6, we can guarantee the existence of a 4-independent set of M with such a property. Moreover, in the binary case, we show that if r(M)−r(N)≥5, then M has such a 4-independent set or M has a triangle T meeting 3 triads and such that M/T is a 3-connected matroid with an N-minor.     

A direct bijection for the Harer-Zagier formula

We give a combinatorial proof of Harer and Zagier's formula for the disjoint cycle distribution of a long cycle multiplied by an involution with no fixed points, in the symmetric group on a set of even cardinality. The main result of this paper is a direct bijection of a set B_p,k, the enumeration of which is equivalent to the Harer-Zagier formula. The elements of B_p,k are of the form (μ,π), where μ is a pairing on {1,…,2p}, π is a partition into k blocks of the same set, and a certain relation holds between μ and π. (The set partitions π that can appear in B_p,k are called “shift-symmetric”, for reasons that are explained in the paper.) The direct bijection for B_p,k identifies it with a set of objects of the form (ρ,t), where ρ is a pairing on a 2(p-k+1)-subset of {1,…,2p} (a “partial pairing”), and t is an ordered tree with k vertices. If we specialize to the extreme case when p=k-1, then ρ is empty, and our bijection reduces to a well-known tree bijection.     

Largest 4-connected components of 3-connected planar triangulations

Let T_n be a 3-connected n-vertex planar triangulation chosen uniformly at random. Then the number of vertices in the largest 4-connected component of T_n is asymptotic to n/2 with probability tending to 1 as n → ∞. It follows that almost all 3-connected triangulations with n vertices have a cycle of length at least n/2 + o(n).     

Minimally 3-connected graphs

A constructive characterization of the class of minimally 3-connected graphs is presented. This yields a new characterization for the class of 3-connected graphs, which differs from the characterization provided by Tutte. Where Tutte's characterization requires the set of all wheels as a starting set, the new characterization requires only the graph K₄. The new characterization is based on the application of graph operations to appropriate vertex and edge sets in minimally 3-connected graphs.     

Uniformly 3-connected graphs

Let $k$ be a positive integer. A graph is said to be uniformly $k$-connected if between any pair of vertices the maximum number of independent paths is exactly $k$. Dawes showed that all minimally 3-connected graphs can be constructed from $K_4$ such that every graph in each intermediate step is also minimally 3-connected. In this paper, we generalize Dawes' result to uniformly 3-connected graphs. We give a constructive characterization of the class of uniformly 3-connected graphs which differs from the characterization provided by Göring et al., where their characterization requires the set of all 3-connected and 3-regular graphs as a starting set, the new characterization requires only the graph $K_4$. Eventually, we obtain a tight bound on the number of edges in uniformly 3-connected graphs.     

A strengthening of the Kuratowski planarity criterion for 3-connected graphs

We prove that any non-planar 3-connected graph with at least 6 vertices contains a cycle with three pairwise ‘interwoven’ chords.