共查询到20条相似文献,搜索用时 15 毫秒
1.
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. 相似文献
2.
3.
4.
5.
6.
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. 相似文献
7.
8.
We prove that a 3-connected cubic graph contains a cycle through any nine points. 相似文献
9.
G Mullineux 《Journal of Combinatorial Theory, Series A》1980,28(2):115-124
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. 相似文献
10.
D. W. Barnette 《Israel Journal of Mathematics》1994,86(1-3):397-407
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. 相似文献
11.
William J. Keith 《The Ramanujan Journal》2012,27(2):163-167
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. 相似文献
12.
Thomas Harmuth 《Discrete Applied Mathematics》2002,120(1-3):117-140
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. 相似文献
13.
João Paulo Costalonga 《European Journal of Combinatorics》2012,33(1):72-81
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. 相似文献
14.
I.P. Goulden 《Journal of Combinatorial Theory, Series A》2005,111(2):224-238
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 Bp,k, the enumeration of which is equivalent to the Harer-Zagier formula. The elements of Bp,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 Bp,k are called “shift-symmetric”, for reasons that are explained in the paper.) The direct bijection for Bp,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. 相似文献
15.
Edward A. Bender L. Bruce Richmond Nicholas C. Wormald 《Random Structures and Algorithms》1995,7(4):273-285
Let Tn be a 3-connected n-vertex planar triangulation chosen uniformly at random. Then the number of vertices in the largest 4-connected component of Tn 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). 相似文献
16.
Vincent Vajnovszki 《Discrete Applied Mathematics》2011,159(14):1453-1459
17.
Xiaoyun Lu 《Discrete Mathematics》2010,310(13-14):2054-2058
18.
《Journal of Combinatorial Theory, Series B》1986,40(2):159-168
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 K4. The new characterization is based on the application of graph operations to appropriate vertex and edge sets in minimally 3-connected graphs. 相似文献
19.
Liqiong Xu 《Journal of Graph Theory》2024,105(3):403-412
Let be a positive integer. A graph is said to be uniformly -connected if between any pair of vertices the maximum number of independent paths is exactly . Dawes showed that all minimally 3-connected graphs can be constructed from 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 . Eventually, we obtain a tight bound on the number of edges in uniformly 3-connected graphs. 相似文献
20.
A.K. Kelmans 《Discrete Mathematics》1984,51(3):215-220
We prove that any non-planar 3-connected graph with at least 6 vertices contains a cycle with three pairwise ‘interwoven’ chords. 相似文献