Intersecting all edges of convex polytopes by planes

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 Characterization of Astral (n 4 ) Configurations

A conjecture of Branko Grünbaum concerning what astral (n ₄ ) configurations exist is shown to be true. Received July 8, 2000, and in revised form February 14, 2001. Online publication August 28, 2001.     

Caterpillar arboricity of planar graphs

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 (E_i)_1?i?4 in such a way that G[E_i], 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.     

On Grünbaum's Conjecture about Inner Illumination of Convex Bodies

In 1964 Grünbaum conjectured that any primitive set illuminating from within a convex body in E ^d , d ≥ 3 , has at most 2 ^d 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 ⊂ E ^d with primitive illuminating sets of an arbitrarily large cardinality. Received December 1, 1997, and in revised form January 21, 1999.     

Some infinite classes of Hadamard matrices

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.     

Simplicial Arrangements with up to 27 Lines

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.     

Proof of a conjecture of Burr,Grünbaum,and Sloane

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.     

Graphs With Least Eigenvalue —2: A New Proof of the 31 Forbidden Subgraphs Theorem

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.     

Non-Hamiltonian non-Grinbergian graphs

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.     

Covering the vertex set of a graph with subgraphs of smaller degree

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.     

New results on affine invariant points

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.     

The graphs of polytopes with involutory automorphisms

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.     

Hamiltonian cycles in generalized petersen graphs

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.     

Dominating direct products of graphs

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.     

On acyclic colorings of planar graphs

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.     

On acyclic colorings of planar graphs

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.     

Large induced trees in sparse random graphs

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).     

Hamiltonian decomposition of lexicographic product

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.     

On the transversal number and VC-dimension of families of positive homothets of a convex body

Let F be a family of positive homothets (or translates) of a given convex body K in Rⁿ. 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 nⁿ. 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 Rⁿ 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.     

Pairs of Hamiltonian circuits in 5-connected planar graphs

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 $\text{1}\text{168}$ of their edges. We construct 4- and 5-valent, 3-connected non-Hamiltonian planar graphs.