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.     

An upper bound on the path number of a digraph

A proof is presented of the conjecture of Alspach and Pullman that for any digraph G on n ≥ 4 vertices, the path number of G is at most [$\text{n}{}^2\text{4}$].     

On graphs which contain all small trees

We investigate those graphs G_n with the property that any tree on n vertices occurs as subgraph of G_n. In particular, we consider the problem of estimating the minimum number of edges such a graph can have. We show that this number is bounded below and above by $\text{1}\text{2}\text{n}\text{log}\text{n}$ and $\text{n}{}^{\mathrm{<mtext>1+</mtext><mtext>1</mtext><mtext>log\; log</mtext><mtext>\; n</mtext>}}$, respectively.     

Bounds for equidistant codes and partial projective planes

A strongly connected digraphGwithnvertices satisfying the condition that the sum of degrees for any two nonadjacent vertices is at least 2nis pancyclic unlessGis a tournament ornis even and $\text{G=}\text{K}\text{→}{}_{\mathrm{<mtext>n</mtext><mtext>2</mtext><mtext>n</mtext><mtext>2</mtext>}}$     

On the chromatic forcing number of a random graph

When we wish to compute lower bounds for the chromatic number χ(G) of a graph G, it is of interest to know something about the ‘chromatic forcing number’ f_χ(G), which is defined to be the least number of vertices in a subgraph H of G such that χ(H) = χ(G). We show here that for random graphs G_n,p with n vertices, f_χ(G_n,p) is almost surely at least ($\text{1}\text{2}$?ε)n, despite say the fact that the largest complete subgraph of G_n,p has only about log n vertices.     

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.     

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.     

Factorizing the complete graph into factors with large star number

The graph G has star number n if any n vertices of G belong to a subgraph which is a star. Let f(n, k) be the smallest number m such that the complete graph on m vertices can be factorized into k factors with star number n. In the present paper we prove that $\text{c}{}_1{}^{\mathrm{n}}\text{k ≤ f(n, k) < c}{}_2{}^{\mathrm{n}}\text{k}$.     

Hamiltonicity in (0–1)-polyhedra

The graph G(P) of a polyhedron P has a node corresponding to each vertex of P and two nodes are adjacent in G(P) if and only if the corresponding vertices of P are adjacent on P. We show that if P ? $\text{R}$ⁿ is a polyhedron, all of whose vertices have (0–1)-valued coordinates, then (i) if G(P) is bipartite, the G(P) is a hypercube; (ii) if G(P) is nonbipartite, then G(P) is hamilton connected. It is shown that if P ? $\text{R}$ⁿ has (0–1)-valued vertices and is of dimension d (≤n) then there exists a polyhedron P′ ? $\text{R}$^d having (0–1)-valued vertices such that $\text{G(P) ? G(P′)}$. Some combinatorial consequences of these results are also discussed.     

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.     

On subgraph number independence in trees

For finite graphs F and G, let N_F(G) denote the number of occurrences of F in G, i.e., the number of subgraphs of G which are isomorphic to F. If $\text{F}$ and $\text{G}$ are families of graphs, it is natural to ask then whether or not the quantities N_F(G), F∈$\text{F}$, are linearly independent when G is restricted to $\text{G}$. For example, if $\text{F}$ = {K₁, K₂} (where K_n denotes the complete graph on n vertices) and $\text{F}$ is the family of all (finite) trees, then of course N_K1(T) ? N_K2(T) = 1 for all T∈$\text{F}$. Slightly less trivially, if $\text{F}$ = {S_n: n = 1, 2, 3,…} (where S_n denotes the star on n edges) and $\text{G}$ again is the family of all trees, then Σ_n=1^∞(?1)ⁿ⁺¹N_Sn(T)=1 for all T∈$\text{G}$. It is proved that such a linear dependence can never occur if $\text{F}$ is finite, no F∈$\text{F}$ has an isolated point, and $\text{G}$ contains all trees. This result has important applications in recent work of L. Lovász and one of the authors (Graham and Lovász, to appear).     

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.     

Extremal values of the interval number of a graph,II

It is shown that the interval number of a graph on n vertices is at most $\text{[}\text{1}\text{4}\text{(n+1)]}$, and this bound is best possible. This means that we can represent any graph on n vertices as an intersection graph in which the sets assigned to the vertices each consist of the union of at most $\text{[}\text{1}\text{4}\text{(n+1)]}$ finite closed intervals on the real line. This upper bound is attained by the complete bipartite graph K_[n/2],[n/2].     

A lower bound for the independence number of a planar graph

A subset of the vertices of a graph is independent if no two vertices in the subset are adjacent. The independence number α(G) is the maximum number of vertices in an independent set. We prove that if G is a planar graph on N vertices then $\text{α(G)/N ?}\text{2}\text{9}$.     

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.     

Balancing signed graphs

A signed graph based on F is an ordinary graph F with each edge marked as positive or negative. Such a graph is called balanced if each of its cycles includes an even number of negative edges. Psychologists are sometimes interested in the smallest number d=d(G) such that a signed graph G may be converted into a balanced graph by changing the signs of d edges. We investigate the number D(F) defined as the largest d(G) such that G is a signed graph based on F. We prove that $\text{1}\text{2}\text{m?}\text{nm}\text{≤D(F)≤}\text{1}\text{2}\text{m}$ for every graph F with n vertices and m edges. If F is the complete bipartite graph with t vertices in each part, then $\text{D(F)≤}\text{1}\text{2}\text{t}{}^2\text{?ct}{}^{\mathrm{<mtext>3</mtext><mtext>2</mtext>}}$ for some positive constant c.     

On the radius of graphs

Let G be any 3-connected graph containing n vertices and r the radius of G. Then the inequality $\text{r <}\text{1}\text{4}\text{n + O(}\text{log}\text{n)}$ is proved. A similar theorem concerning any (2m ?1)-connected graph G can be proved too.     

Lower bounds for the clique and the chromatic numbers of a graph

G is any simple graph with m edges and n vertices where these vertices have vertex degrees d(1)≥d(2)≥?≥d(n), respectively. General algorithms for the exact calculation of χ(G), the chromatic number of G, are almost always of ‘branch and bound’ type; this type of algorithm requires an easily constructed lower bound for χ(G). In this paper it is shown that, for a number of such bounds (many of which are described here for the first time), the bound does not exceed cl(G) where cl(G) is the clique number of G.In 1972 Myers and Liu showed that cl(G)≥n?(n?2m?n). Here we show that cl(G)≥ n?[n?(2m?n)(1+c²_v)^{$\text{1}\text{2}$}], where c_v is the vertex degree coefficient of variation in G, that cl(G)≥ Bondy's constructive lower bound for χ(G), and that cl(G)≥n?(n?W(G)), where W(G) is the largest positive integer such that W(G)≤d(W(G)+1) [W(G)+1 is the Welsh and Powell upper bound for χ(G)]. It is also shown that cl(G)+$\text{1}\text{3}$>n?(n?L(G))≥n?(n?λ₁) and that χ(G)≥ n?(n?λ₁); λ₁ is the largest eigenvalue of A, the adjacency matrix of G, and L(G) is a newly defined single-valued function of G similar to W(G) in its construction from the vertex degree sequence of G [L(G)≥W(G)].Finally, a ‘greedy’ lower bound for cl(G) is constructed from A and it is shown that this lower bound is never less than Bondy's bound; thereafter, for 150 random graphs with varying numbers of vertices and edge densities, the values of lower bounds given in this paper are listed, thereby illustrating that this last greedily obtained lower bound is almost always better than each of the other bounds.     

Cycles of even length in graphs

In this paper we solve a conjecture of P. Erdös by showing that if a graph Gⁿ has n vertices and at least $\text{100kn}{}^{\mathrm{<mtext>1+</mtext><mtext>1</mtext><mtext>k</mtext>}}$ edges, then G contains a cycle C^2l of length 2l for every integer $\text{l ∈ [k, kn}{}^{\mathrm{<mtext>1</mtext><mtext>k</mtext>}}\text{]}$. Apart from the value of the constant this result is best possible. It is obtained from a more general theorem which also yields corresponding results in the case where Gⁿ has only cn(log n)^α edges (α ≥ 1).     

Some Asymptotic ith Ramsey numbers

Let G be a graph with chromatic number χ(G) and let t(G) be the minimum number of vertices in any color class among all χ(G)-vertex colorings of G. Let H′ be a connected graph and let H be a graph obtained by subdividing (adding extra vertices to) a fixed edge of H′. It is proved that if the order of H is sufficiently large, the ith Ramsey number r_i(G, H) equals $\text{[}\text{((χ(G)?1)(|}\text{H}\text{|?1)+t(G)?1)}\text{i}\text{]+1}$.