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:
An extremal problem for Graham-Rothschild parameter words
Combinatorica - - 1989
This paper exposes connections between the theory of Möbius functions and extremal problems, extending ideas of Frankl and Pach [8]. Extremal results concerning the trace of objects in geometric lattices and Graham—Rothschild parameter posets are proved, covering previous results due to Sauer [16] and Perles and Shelah [17].
G-parking functions and tree inversions
Combinatorica - Tập 37 - Trang 269-282 - 2015
A depth-first search version of Dhar’s burning algorithm is used to give a bijection between the parking functions of a graph and labeled spanning trees, relating the degree of the parking function with the number of inversions of the spanning tree. Specializing to the complete graph solves a problem posed by R. Stanley.
The Erdős–Pósa Property for Odd Cycles in Highly Connected Graphs
Combinatorica - Tập 21 - Trang 267-278 - 2001
In [9] Thomassen proved that a
-connected graph either contains k vertex disjoint odd cycles or an odd cycle cover containing at most 2k-2 vertices, i.e. he showed that the Erdős–Pósa property holds for odd cycles in highly connected graphs. In this paper, we will show that the above statement is still valid for 576k-connected graphs which is essentially best p......
Graph Connectivity After Path Removal
Combinatorica - Tập 23 - Trang 185-203 - 2003
Let G be a graph and
u, v be two distinct vertices of
G. A u—v path P is called nonseparating if
G—V(P) is connected. The purpose of this
paper is to study the number of nonseparating
u—v path for two arbitrary
vertices u and
v of a given graph. For a
positive integer k, we will
show that there is a minimum integer α(k) so that if G is an α(k)-connected graph and
u and v are two arbitrary vertices......
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......
On low-dimensional faces that high-dimensional polytopes must have
Combinatorica - Tập 10 - Trang 271-280 - 1990
We prove that every five-dimensional polytope has a two-dimensional face which is a triangle or a quadrilateral. We state and discuss the following conjecture: For every integerk≥1 there is an integer f(k) such that everyd-polytope,d≥f(k), has ak-dimensional face which is either a simplex or combinatorially isomorphic to thek-dimensional cube. We give some related results concerning facet-forming ......
Perfect matchings in planar cubic graphs
Combinatorica - Tập 32 - Trang 403-424 - 2012
A well-known conjecture of Lovász and Plummer from the mid-1970’s, still open, asserts that for every cubic graph G with no cutedge, the number of perfect matchings in G is exponential in |V (G)|. In this paper we prove the conjecture for planar graphs; we prove that if G is a planar cubic graph with no cutedge, then G has at least
......
On Ramsey—Turán type theorems for hypergraphs
Combinatorica - Tập 2 - Trang 289-295 - 1982
LetH
r
be anr-uniform hypergraph. Letg=g(n;H
r
) be the minimal integer so that anyr-uniform hypergraph onn vertices and more thang edges contains a subgraph isomorphic toH
r
. Lete =f(n;H
......
Matchings of cycles and paths in directed graphs
Combinatorica - Tập 27 - Trang 383-398 - 2008
In this paper we present a Berge-Tutte-type theorem for a matching problem in directed graphs. This extends the maximum matching problem in undirected graphs, the maximum even factor problem in weakly symmetric directed graphs proposed by W. H. Cunningham and J. F. Geelen in [6], and a packing problem for cycles and edges in undirected graphs. We show an Edmonds-Gallai-type structural description ......
Tổng số: 1,194
- 1
- 2
- 3
- 4
- 5
- 6
- 10