A characterization theorem is given for 3-dimensional convex polytopes Q having the following property: There exists a polytope P, isomorphic to Q, all edges of which can be cut by a pair of planes that miss all its vertices. The result yields an affirmative solution of a conjecture of B. Grünbaum. 相似文献
A conjecture of Branko Grünbaum concerning what astral (n4) configurations exist is shown to be true.
Received July 8, 2000, and in revised form February 14, 2001. Online publication August 28, 2001. 相似文献
We solve a conjecture of Roditty, Shoham and Yuster [P.J. Cameron (Ed.), Problems from the 17th British Combinatorial Conference, Discrete Math., 231 (2001) 469-478; Y. Roditty, B. Shoham, R. Yuster, Monotone paths in edge-ordered sparse graphs, Discrete Math. 226 (2001) 411-417] on the caterpillar arboricity of planar graphs. We prove that for every planar graph G=(V,E), the edge set E can be partitioned into four subsets (Ei)1?i?4 in such a way that G[Ei], for 1?i?4, is a forest of caterpillars. We also provide a linear-time algorithm which constructs for a given planar graph G, four forests of caterpillars covering the edges of G. 相似文献
In 1964 Grünbaum conjectured that any primitive set illuminating from within a convex body in Ed , d ≥ 3 , has at most 2d points. This was confirmed by V. Soltan in 1995 for the case d = 3 . Here we give a negative answer to Grünbaum's conjecture for all d ≥ 4 , by constructing a convex body K ⊂ Ed with primitive illuminating sets of an arbitrarily large cardinality.
Received December 1, 1997, and in revised form January 21, 1999. 相似文献
Some results of Williamson [Duke Math. J., 11 1944, Bull. Amer. Math. Soc., 53 1947] and Wallis (J. Combinatorial Theory, 6 1969] are considerably improved to establish that in each case referred to, the same stated condition or conditions, which according to either of the authors give rise to one Hadamard matrix, actually imply the existence of an infinite series of Hadamard matrices. Also proved is the existence of some infinite series of Williamson's matrices, which coupled with the interesting findings of Turyn [J. Combinatorial Theory Ser. A, 16 1974] establish the existence of infinitely many more series of Hadamard matrices than those known so far. 相似文献
We compute all isomorphism classes of simplicial arrangements in the real projective plane with up to 27 lines. It turns out that Grünbaum??s catalogue is complete up to 27 lines except for four new arrangements with 22, 23, 24, 25 lines, respectively. As a byproduct we classify simplicial arrangements of pseudolines with up to 27 lines. In particular, we disprove Grünbaum??s conjecture about unstretchable arrangements with at most 16 lines, and prove the conjecture that any simplicial arrangement with at most 14 pseudolines is stretchable. 相似文献
We establish a duality principle for arrangements of pseudolines in the projective plane, and thereby prove the conjecture of Burr, Grünbaum, and Sloane that the solution of the “orchard problem” for pseudoline arrangements and the solution t?(p) of the dual problem are equal. 相似文献
Generalized line graphs were introduced by Hoffman Proc. Calgary Internat. Conf. on Combinatorial Structures and their applications, Gordon and Breach, New York (1970); they were characterized in 1980 by a collection of 31 forbidden induced subgraphs, obtained independently by Cvetkovi et al., Comptes Rendus Math. Rep. Acad. Sci. Canada (1980) and S. B. Rao et al., Proc. Second Symp., Indian Statistical Institute, Calcutta, Lecture Notes in Math., (1981). Here a short new proof of this characterization theorem is given, based on an edge-colouring technique. 相似文献
Settling a question of Tutte and a similar question of Grünbaum and Zaks, we present a 3-valent 3-connected planar graph that has only pentagons and octagons, has 92 (200, respectively) vertices and its longest circuit (path, respectively) contains at most 90 (198, respectively) vertices; moreover, it is shown that the family of all 3-valent 3-connected planar graphs, having n-gons only if n≡ 2 (mod3) (or n≡ 1 (mod3)), has a shortness exponent which is less than one. 相似文献
The problem of covering the vertex set of a graph with subsets spanning subgraphs of smaller degree is studied. The result of this study is applied to give a new bound on the chromatic number of a graph in terms of the maximum vertex-degree of the graph and the maximum number of vertices in a clique of the graph. By using this bound, it is shown that if d is at least 7 and e is at least 4, then there is no regular graph of valency d, chromatic number d, whose smallest circuit has at least e edges; this settles a conjecture of Branko Grünbaum. 相似文献
We prove a conjecture of B. Grünbaum stating that the set of affine invariant points of a convex body equals the set of points invariant under all affine linear symmetries of the convex body. As a consequence we give a short proof of the fact that the affine space of affine linear points is infinite dimensional. In particular, we show that the set of affine invariant points with no dual is of the second category. We investigate extremal cases for a class of symmetry measures. We show that the centers of the John and Löwner ellipsoids can be far apart and we give the optimal order for the extremal distance between the two centers. 相似文献
Steinitz’ theorem states that a graph is the graph of a 3-dimensional convex polytope if and only if it is planar and 3-connected.
Grünbaum has shown that Steinitz’ proof can be modified to characterize the graphs of polytopes that are centrally symmetric
or have a plane of symmetry. We show how to modify Steinitz’ proof to take care of the remaining involutory case—polytopes
that are symmetric about a line.
Research supported by NSF Grant GP-3470. 相似文献
Watkins (J. Combinatorial Theory 6 (1969), 152–164) introduced the concept of generalized Petersen graphs and conjectured that all but the original Petersen graph have a Tait coloring. Castagna and Prins (Pacific J. Math. 40 (1972), 53–58) showed that the conjecture was true and conjectured that generalized Petersen graphs G(n, k) are Hamiltonian unless isomorphic to G(n, 2) where n ≡ 5(mod 6). The purpose of this paper is to prove the conjecture of Castagna and Prins in the case of coprime numbers n and k. 相似文献
An upper bound for the domination number of the direct product of graphs is proved. It in particular implies that for any graphs G and H, γ(G×H)?3γ(G)γ(H). Graphs with arbitrarily large domination numbers are constructed for which this bound is attained. Concerning the upper domination number we prove that Γ(G×H)?Γ(G)Γ(H), thus confirming a conjecture from [R. Nowakowski, D.F. Rall, Associative graph products and their independence, domination and coloring numbers, Discuss. Math. Graph Theory 16 (1996) 53-79]. Finally, for paired-domination of direct products we prove that γpr(G×H)?γpr(G)γpr(H) for arbitrary graphs G and H, and also present some infinite families of graphs that attain this bound. 相似文献
The conjecture of B. Grünbaum on existing of admissible vertex coloring of every planar graph with 5 colors, in which every bichromatic subgraph is acyclic, is proved and some corollaries of this result are discussed in the present paper. 相似文献
The conjecture of B. Grünbaum on existing of admissible vertex coloring of every planar graph with 5 colors, in which every bichromatic subgraph is acyclic, is proved and some corollaries of this result are discussed in the present paper. 相似文献
We consider the size of the largest induced tree in random graphs, random regular graphs and random regular digraphs where the average degree is constant. In all cases we show that with probability 1 − o(1), such graphs have induced trees of size order n. In particular, the first result confirms a conjecture of Erdos and Palka (Discrete Math.46 (1983), 145–150). 相似文献
In this paper we prove the conjecture of J.-C. Bermond (Ann. Discrete Math.36 (1978), 21–28): If two graphs are decomposable into Hamiltonian cycles, then their lexicographic product is decomposable, too. 相似文献
Let F be a family of positive homothets (or translates) of a given convex body K in Rn. We investigate two approaches to measuring the complexity of F. First, we find an upper bound on the transversal number τ(F) of F in terms of n and the independence number ν(F). This question is motivated by a problem of Grünbaum [L. Danzer, B. Grünbaum, V. Klee, Helly’s theorem and its relatives, in: Proc. Sympos. Pure Math., vol. VII, Amer. Math. Soc., Providence, RI, 1963, pp. 101-180]. Our bound is exponential in n, an improvement from the previously known bound of Kim, Nakprasit, Pelsmajer and Skokan [S.-J. Kim, K. Nakprasit, M.J. Pelsmajer, J. Skokan, Transversal numbers of translates of a convex body, Discrete Math. 306 (18) (2006) 2166-2173], which was of order nn. By a lower bound, we show that the right order of magnitude is exponential in n.Next, we consider another measure of complexity, the Vapnik-?ervonenkis dimension of F. We prove that vcdim(F)≤3 if n=2 and is infinite for some F if n≥3. This settles a conjecture of Grünbaum [B. Grünbaum, Venn diagrams and independent families of sets, Math. Mag. 48 (1975) 12-23]: Show that the maximum dual VC-dimension of a family of positive homothets of a given convex body K in Rn is n+1. This conjecture was disproved by Naiman and Wynn [D.Q. Naiman, H.P. Wynn, Independent collections of translates of boxes and a conjecture due to Grünbaum, Discrete Comput. Geom. 9 (1) (1993) 101-105] who constructed a counterexample of dual VC-dimension . Our result implies that no upper bound exists. 相似文献
Settling a problem raised by B. Grünbaum, J. Malkevitch, and the author, we present 5-valent 5-connected planar graphs that admit no pairs of edgedisjoint Hamiltonian circuits; our smallest example has 176 vertices. This is used to construct an infinite family of 5-valent 5-connected planar graphs, in which every member has the property that any pair of Hamiltonian circuits in it share at least about of their edges. We construct 4- and 5-valent, 3-connected non-Hamiltonian planar graphs. 相似文献