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
H. Lefmann
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
David Perkinson, Qiaoyu Yang, Kuai Yu
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
Dieter Rautenbach, Bruce Reed
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 possible.... hiện toàn bộ
On modp transversals
Combinatorica - Tập 11 - Trang 17-22 - 1991
Jeff Kahn, Roy Meshulam
Graph Connectivity After Path Removal
Combinatorica - Tập 23 - Trang 185-203 - 2003
Guantao Chen*, Ronald J. Gould†, Xingxing Yu‡
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... hiện toàn bộ
Isomorphic factorizations VIII: Bisectable trees
Combinatorica - Tập 4 - Trang 169-179 - 1984
Frank Harary, Robert W. Robinson
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... hiện toàn bộ
On low-dimensional faces that high-dimensional polytopes must have
Combinatorica - Tập 10 - Trang 271-280 - 1990
G. Kalai
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 ... hiện toàn bộ
Perfect matchings in planar cubic graphs
Combinatorica - Tập 32 - Trang 403-424 - 2012
Maria Chudnovsky, Paul Seymour
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 $$2^{{{\left| {V(G)} \right|} \mathord{\left/ {\vphantom {{\left| ... hiện toàn bộ
On Ramsey—Turán type theorems for hypergraphs
Combinatorica - Tập 2 - Trang 289-295 - 1982
P. Erdős, Vera T. Sós
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 r ,εn) denote the minimal integer such that everyr-uniform hypergraph onn vertices with more thane edges and with no independent set ofεn vertices contains a subgraph isomorphic toH r . We show that ifr>2 andH r... hiện toàn bộ
Matchings of cycles and paths in directed graphs
Combinatorica - Tập 27 - Trang 383-398 - 2008
Gyula Pap, László Szegő
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 ... hiện toàn bộ
Tổng số: 1,194   
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 10