An extremal problem in graph theory

It is proved that the maximum number of cut-vertices in a connected graph withn vertices andm edges is $$max\left\{ {q:m \leqq (_2^{n - q} ) + q} \right\}$$ All the extremal graphs are determined and the corresponding problem for cut-edges is also solved.     

On a valence problem in extremal graph theory

Let L ≠ Kinp be a p-chromatic graph and e be an edge of L such that L ? e is (p?1)-chromatic If Gⁿ is a graph of n vertices without containing L but containing K_p, then the minimum valence of Gⁿ is

$\text{?n}\text{1?}\text{1}\text{p?}\text{3}\text{2}\text{+}\text{O}\text{(1).}$

     

Two problems in extremal graph theory

Graphs and Combinatorics -     

Compactness results in extremal graph theory

Let L be a given family of so called prohibited graphs. Let ex (n, L) denote the maximum number of edges a simple graph of ordern can have without containing subgraphs from L. A typical extremal graph problem is to determine ex (n, L), or at least, find good bounds on it. Results asserting that for a given L there exists a much smaller L*⫅L for which ex (n, L) ≈ ex (n, L*) will be calledcompactness results. The main purpose of this paper is to prove some compactness results for the case when L consists of cycles. One of our main tools will be finding lower bounds on the number of pathsP ^k+1 in a graph ofn vertices andE edges., witch is, in fact, a “super-saturated” version of a wellknown theorem of Erdős and Gallai. Dedicated to Tibor Gallai on his seventieth birthday     

An optimal problem in graph theory

The following problem is solved: determine a point on a tree having the property that the sum of the products of the intensities of its vertices by the corresponding distances to that point is a minimum. The proposed algorithm is reduced to the stepwise application to the tree of truncation of its vertices. A feasible interpretation of the problem is given.Translated from Matematicheskie Zametki, Vol. 10, No. 3, pp. 355–359, September, 1971.     

Enumerating maximal independent sets with applications to graph colouring

We give tight upper bounds on the number of maximal independent sets of size k (and at least k and at most k) in graphs with n vertices. As an application of the proof, we construct improved algorithms for graph colouring and computing the chromatic number of a graph.     

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 extremal problem for operators

Let A be a Banach algebra, F a compact set in the complex plane, and h a function holomorphic in some neighborhood of the set F. Thus h(a) is meaningful for each element a ε A whose spectrum σ(a) is contained in F, and it is possible to evaluate the norm |h(a)|. Problem: Compute the supremum of the norms |h(a) as a ranges over all elements of A with spectrum contained in F and whose norm does not exceed one; that is, compute sup{|h(a)|; a ε A, σ(a) ⊂ F, |a| ⩽ 1}. This problem was first formulated and treated by the author in the particular case where A is the algebra of all linear operators on a finite-dimensional Hilbert space and F is the disc {z; |z| ⩽ r} for a given positive number r<1. The paper discusses motivation, connections with complex function theory, convergence of iterative processes, critical exponents, and the infinite companion matrix.     

On some extremal problems in graph theory

The author proves that ifC is a sufficiently large constant then every graph ofn vertices and [Cn ^3/2] edges contains a hexagonX ₁,X ₂,X ₃,X ₄,X ₅,X ₆ and a seventh vertexY joined toX ₁,X ₃ andX ₅. The problem is left open whether our graph contains the edges of a cube, (i.e. an eight vertexZ joined toX ₂,X ₄ andX ₆).     

An extremal problem in the theory of hardy functions

It is proved that ifj is an inner function and ρ(T)=sup|∫(e^iγT/j(γ))f(γ)dγ| overf in the unit ball ofH ¹, then eitherρ ≡ 1 for allT≧0, or elseρ(T) ↓ 0 exponentially fast asT ↑ ∞. The inner functionsj corresponding to each alternative are classified.     

An extremal problem for polynomials

We give a solution to an extremal problem for polynomials, which asks for complex numbers α₀,…,α_n${\alpha }_0,\dots ,{\alpha }_n$ of unit magnitude that minimise the largest supremum norm on the unit circle for all polynomials of degree n whose k  -th coefficient is either α_k${\alpha }_k$ or −α_k$-{\alpha }_k$.     

On one extremal problem of Pompeiu sets

We determine upper bounds for the least radius of a ball in which a given set is a Pompeiu set (the set considered is a half right circular cone). The obtained estimates significantly improve known results. Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 61, No. 1, pp. 61–72, January, 2009.     

An extremal problem related to probability

Summary We consider a walk from a stateA ₁ to a stateA _n+1 in which the probability of remaining atA _i isp _i , and the probability of progressing fromA _i toA _i+1 is 1 –p _i . The probabilityW _nk of reachingA _n+1 fromA ₁ in exactlyn + k steps can then be expressed as a polynomial of degreen + k in then variablesp ₁,,p _n . We determine the maximum value ofW _nk and the (unique) choice (p ₁,,p _n ) for which this extremum occurs.Dedicated to Professor Otto Haupt with best wishes on his 100th birthday