The extremal graph problem of the icosahedron

P. Turán has asked the following question:Let I¹² be the graph determined by the vertices and edges of an icosahedron. What is the maximum number of edges of a graph Gⁿ of n vertices if Gⁿ does not contain I¹² as a subgraph?We shall answer this question by proving that if n is sufficiently large, then there exists only one graph having maximum number of edges among the graphs of n vertices and not containing I¹². This graph Hⁿ can be defined in the following way:Let us divide n ? 2 vertices into 3 classes each of which contains [$\text{(n?2)}\text{3}$] or $\text{[}\text{(n?2)}\text{3}\text{] + 1}$ vertices. Join two vertices iff they are in different classes. Join two vertices outside of these classes to each other and to every vertex of these three classes.     

On the minimum order of graphs with given semigroup

Denote by M(n) the smallest positive integer such that for every n-element monoid M there is a graph G with at most M(n) vertices such that End(G) is isomorphic to M. It is proved that $\text{2}\text{(1 + o(1))n}\text{log}{}_2\text{n}\text{≤M(n)≤n ·}\text{2n}\text{+ O(n)}$. Moreover, for almost all n-element monoids M there is a graph G with at most 12 · n · log₂n + n vertices such that End(G) is isomorphic to M.     

Minimum number of edges in graphs that are both P2- and Pi-connected

A simple graph with n vertices is called P_i-connected if any two distinct vertices are connected by an elementary path of length i. In this paper, lower bounds of the number of edges in graphs that are both P₂- and P_i-connected are obtained. Namely if $\text{i?}\text{1}\text{2}\text{(n+1)}$, then |E(G)|?((4i?5)/(2i?2))(n?1), and if $\text{i >}\text{1}\text{2}\text{(n+ 1)}$, then |E(G)|?2(n?1) apart from one exeptional graph. Furthermore, extremal graphs are determined in the former.     

Bounds on the number of disjoint spanning trees

It is shown that an n-edge connected graph has at least ?$\text{(n ? 1)}\text{2}$? pairwise edge-disjoint spanning trees. This bound is best possible in general. A maximal planar graph with four or more vertices contains two edge-disjoint spanning trees. For a maximal toroidal graph, this number is three.     

Lower bounds on the independence number in terms of the degrees

Wei discovered that the independence number of a graph G is at least Σ_v(1 + d(v))^?1. It is proved here that if G is a connected triangle-free graph on n ≥ 3 vertices and if G is neither an odd cycle nor an odd path, then the bound above can be increased by $\text{n}\text{Δ(Δ + 1)}$, where Δ is the maximum degree. This new bound is sharp for even cycles and for three other graphs. These results relate nicely to some algorithms for finding large independent sets. They also have a natural matrix theory interpretation. A survey of other known lower bounds on the independence number is presented.     

Spanning subgraphs of k-connected digraphs

It is shown that every k-edge-connected digraph with m edges and n vertices contains a spanning connected subgraph having at most $\text{2m + 6(k ?1)(n ? 1))}\text{(5k ? 3)}$ edges. When k = 2 the bound is improved to $\text{(3m + 8(n ? 1))}\text{10}$, which implies that a 2-edge-connected digraph is connected by less than 70% of its edges. Examples are given which require almost two-thirds of the edges to connect all vertices.     

Arbres avec un nombre maximum de sommets pendants

This article is an attempt to study the following problem: Given a connected graph G, what is the maximum number of vertices of degree 1 of a spanning tree of G? For cubic graphs with n vertices, we prove that this number is bounded by $\text{1}\text{4}\text{n}$ and $\text{1}\text{2}\text{(n ? 2)}$.     

Degrees and cycles in digraphs

In this article, we give conditions on the total degrees of the vertices in a strong digraph implying the existence of a cycle of length at least $\text{?}\text{(n?1)}\text{h}\text{? + 1}$, where n is the number of vertices of the graph and h an integer, 1?h?n?1. The same conditions imply the existence of a path of length $\text{?}\text{(n?1)}\text{h}\text{? + ?}\text{(n?2)}\text{h}\text{?}$. In the case of strong oriented graphs (antisymmetric digraphs) we improve these conditions. In both cases, we show that the given conditions are the best possible.     

On a problem of C. C. Chen and D. E. Daykin

Let α(k, p, h) be the maximum number of vertices a complete edge-colored graph may have with no color appearing more than k times at any vertex and not containing a complete subgraph on p vertices with no color appearing more than h times at any vertex. We prove that $\text{α(k, p, h) ≤ h + 1 + (k ? 1){(p ? h ? 1) × (h}{}^{\mathrm{p}}\text{+ 1)}}{}^{\mathrm{<mtext>1</mtext><mtext>h</mtext>}}$ and obtain a stronger upper bound for α(k, 3, 1). Further, we prove that a complete edge-colored graph with n vertices contains a complete subgraph on p vertices in which no two edges have the same color if

$\text{(}\text{n}\text{3}\text{)>(}\text{p}\text{3}\text{)}\text{Σ}\text{i=1}\text{t}\text{(}\text{e}{}_{\mathrm{i}}\text{2}\text{)}$

where e_i is the number of edges of color i, 1 ≤ i ≤ t.     

On a conjecture of bondy

Bondy conjectured [1] that: if G is a k-connected graph, where k ≥ 2, such that the degree-sum of any k + 1 independent vertices is at least m, then G contains a cycle of length at least: $\text{Min}\text{(}\text{2m}\text{(k + 1)}\text{, n)}$ (n denotes the order of G). We prove here that this result is true.     

A sufficient condition for hamiltonian circuits

A theorem is proved that is (in a sense) the best possible improvement on the following theme: If G is an undirected graph on n vertices in which $\text{|Γ(S)| ≥}\text{1}\text{3}\text{(n + | S | + 3)}$ for every non-empty subset S of the vertices of G, then G is Hamiltonian.     

A property of the colored complete graph

If the lines of the complete graph K_n are colored so that no point is on more than $\text{1}\text{7}\text{(n?1)}$ lines of the same color or so that each point lies on more than $\text{1}\text{7}\text{(5n+8)}$ lines of different colors, then K_n contains a cycle of length n with adjacent lines having different colors.     

Graphs without quadrilaterals

Let f(n) denote the maximum number of edges of a graph on n vertices not containing a circuit of length 4. It is well known that $\text{f(n) ～}\text{1}\text{2}\text{n}\text{n}$. The old conjecture $\text{f(q}{}^2\text{+ q + 1) =}\text{1}\text{2}\text{q(q + 1)}{}^2$ is proved for infinitely many q (whenever q = 2^k).     

Orientable and nonorientable genus of the complete bipartite graph

K_m,n is the complete bipartite graph with m and n vertices in its chromatic classes. G. Ringel has proved that the orientable genus of K_m,n is equal to $\text{{}\text{(m ? 2)(n ? 2)}\text{4}\text{}}\text{if}\text{m ≥ 2}\text{and}\text{n ≥ 2}$ and that its nonorientable genus is equal to $\text{{}\text{(m ? 2)(n ? 2)}\text{2}\text{}}\text{if}\text{m ≥ 3}\text{and}\text{n ≥ 3}$. We give new proofs of these results.     

A lower estimate for the achromatic number of irreducible graphs

The achromatic number of a graph is the largest number of independent sets its vertex set can be split into in such a way that the union of any two of these sets is not independent. A graph is irreducible if no two vertices have the same neighborhood. The achromatic number of an irreducible graph with n vertices is shown to be $\text{≥(}\text{1}\text{2}\text{?0(1))log}\text{n?}\text{log log}\text{n,}$ while an example of Erdös shows that it need not be log n/log 2+2 for any n. The proof uses an indiscernibility argument.     

Spheres tangent to all the faces of a simplex

There are at most 2ⁿ spheres tangent to all n + 1 faces of an n-simplex. It has been shown that the minimum number of such spheres is $\text{2}{}^{\mathrm{n}}\text{? c(n,}\text{1}\text{2}\text{(n + 1))}$ if n is odd and $\text{2}{}^{\mathrm{n}}\text{? c(n,}\text{1}\text{2}\text{(n + 1))}$ if n is even. The object of this note is to show that this result is a consequence of a theorem in graph theory.     

Some new results on the Littlewood-Offord problem

We consider the 2ⁿ sums of the form Σ?_ia_i with the a_i's vectors, | a_i | ? 1, and ?_i = 0, 1 for each i. We raise a number of questions about their distribution.We show that if the a_i lie in two dimensions, then at most $\text{n}\text{(}\text{n}\text{2}\text{)}$) sums can lie within a circle of diameter √3, and if n is even at most the sum of the three largest binomial coefficients can lie in a circle of diameter √5. These are best results under the indicated conditions.If two a's are more than 60° but less than 120° apart in direction, then the bound ($\text{n}\text{[}\text{n}\text{2}\text{]}$) on sums lying within a unit diameter sphere is improved to ($\text{n+1}\text{[}\text{n}\text{2}\text{]}\text{) ? 2(}\text{n?1}\text{[(n?}\text{1}\text{2}\text{)])}$.The method of Katona and Kleitman is shown to lead to a significant improvement on their two dimensional result.Finally, Lubell-type relations for sums lying in a unit diameter sphere are examined.     

Minimally k-connected graphs of low order and maximal size

Let G be a minimally k-connected graph of order n and size e(G).Mader [4] proved that (i) $\text{e(G)?kn?(}\text{k+1}\text{2}\text{)}$; (ii) e(G)?k(n?k) if n?3k?2, and the complete bipartite graph K_k,n?k is the only minimally k-connected graph of order; n and size k(n?k) when k?2 and n?3k?1.The purpose of the present paper is to determine all minimally k-connected graphs of low order and maximal size. For each n such that k+1?n?3k?2 we prove $\text{e(G)??}\text{(n+k)}{}^2\text{8}\text{?}$ and characterize all minimally k-connected graphs of order n and size $\text{?(}\text{(n+k)}{}^2\text{8}\text{?}$.