Combinatorica
Công bố khoa học tiêu biểu
* Dữ liệu chỉ mang tính chất tham khảo
Sắp xếp:
Isomorphic factorizations VIII: Bisectable trees
Combinatorica - Tập 4 - Trang 169-179 - 1984
A tree is called even if its line set can be partitioned into two isomorphic subforests; it is bisectable if these forests are trees. The problem of deciding whether a given tree is even is known (Graham and Robinson) to be NP-hard. That for bisectability is now shown to have a polynomial time algorithm. This result is contained in the proof of a theorem which shows that if a treeS is bisectable t......
Simultaneous reduction of a lattice basis and its reciprocal basis
Combinatorica - Tập 13 - Trang 363-376 - 1993
Given a latticeL we are looking for a basisB=[b
1, ...b
n
] ofL with the property that bothB and the associated basisB
*=[b
1
*
, ...,b
*
] of the reciprocal latticeL
* consist of short vectors. For any such basisB wit......
Nonexistence of universal graphs without some trees
Combinatorica - Tập 17 - Trang 163-171 - 1997
IfG is a finite tree with a unique vertex of largest, and ≥4 degree which is adjacent to a leaf then there is no universal countableG-free graph.
Integral representation of certain combinatorial recurrences
Combinatorica - Tập 35 - Trang 309-315 - 2014
Many recurrences that occur in combinatorics incorporate linear and self-convolutive terms. The generating function associated to these is usually not well defined because it has zero radius of convergence. However, the sequence may be identifiable as the asymptotic expansion of a function, and then contour integration can be applied to obtain an expression as the moment sequence of a (possibly si......
The constructive characterization of (κ,ℓ)-edge-connected digraphs
Combinatorica - Tập 31 - Trang 201-223 - 2011
We give a constructive characterization for (κ, ℓ)-edge-connected digraphs, proving a conjecture of Frank.
Triangulations of the sphere, bitrades and abelian groups
Combinatorica - Tập 34 - Trang 527-546 - 2014
Let
$$\mathcal{G}$$
be a triangulation of the sphere with vertex set V, such that the faces of the triangulation are properly coloured black and white. Motivated by applications in the theory of bitrades, Cavenagh and Wanless defined
......
The splittance of a graph
Combinatorica - - 1981
The splittance of an arbitrary graph is the minimum number of edges to be added or removed in order to produce a split graph (i.e. a graph whose vertex set can be partitioned into a clique and an independent set). The splittance is seen to depend only on the degree sequence of the graph, and an explicit formula for it is derived. This result allows to give a simple characterization of the degree s......
Partition of graphs with condition on the connectivity and minimum degree
Combinatorica - Tập 3 - Trang 95-99 - 1983
C. Thomassen and M. Szegedy proved the existence of a functionf(s, t) such that the points of anyf(s, t)-connected graph have a decomposition into two non-empty sets such that the subgraphs induced by them ares-connected andt-connected, respectively. We prove, thatf(s, t) ≦ 4s+4t − 13 and examine a similar problem for the minimum degree.
Tổng số: 1,194
- 1
- 2
- 3
- 4
- 5
- 6
- 10