### Article

## Trees with a given number of leaves and the maximal number of maximum independent sets

A complete description of trees with maximal possible number of maximum independent setsamong all 𝑛-vertex trees with exactly 𝑙 leaves is obtained. For all values of the parameters 𝑛 and 𝑙, the extremal tree is unique and is the result of merging the endpoints of 𝑙 simple paths.

For any *n*, in the set of *n*-vertex trees such that any two leaves have no common adjacent vertex, we describe the trees with the smallest number of maximal independent sets.

We investigate the number of maximal independent sets in q-ary trees of height n, when q is fixed and n tends to infinity.

We say that a graph *G* has the CIS-property and call it a CIS-graph if every maximal clique and every maximal stable set of *G* intersects.

By definition, *G* is a CIS-graph if and only if the complementary graph \(\overline {G}\) is a CIS-graph. Let us substitute a vertex *v* of a graph *G′* by a graph *G*″ and denote the obtained graph by *G*. It is also easy to see that *G* is a CIS-graph if and only if both *G′* and *G*″ are CIS-graphs. In other words, CIS-graphs respect complementation and substitution. Yet, this class is not hereditary, that is, an induced subgraph of a CIS-graph may have no CIS-property. Perhaps, for this reason, the problems of efficient characterization and recognition of CIS-graphs are difficult and remain open. In this paper we only give some necessary and some sufficient conditions for the CIS-property to hold.

There are obvious sufficient conditions. It is known that *P*4-free graphs have the CIS-property and it is easy to see that *G* is a CIS-graph whenever each maximal clique of *G* has a simplicial vertex. However, these conditions are not necessary.

There are also simple necessary conditions. Given an integer *k* ≥ 2, a *comb* (or *k*-*comb*) *S**k* is a graph with 2*k* vertices *k* of which, *v*1, …, *v**k*, form a clique *C*, while others, \(v^{\prime }_1, \ldots , v^{\prime }_k,\) form a stable set *S*, and \((v_i,v^{\prime }_i)\) is an edge for all *i* = 1, …, *k*, and there are no other edges. The complementary graph \(\overline {S_k}\) is called an *anti-comb* (or *k*-anti-comb). Clearly, *S* and *C* switch in the complementary graphs. Obviously, the combs and anti-combs are not CIS-graphs, since *C* ∩ *S* = ∅. Hence, if a CIS-graph *G* contains an induced comb or anti-comb, then it must be settled, that is, *G* must contain a vertex *v* connected to all vertices of *C* and to no vertex of *S*. For *k* = 2 this observation was made by Claude Berge in 1985. However, these conditions are only necessary.

The following sufficient conditions are more difficult to prove: *G* is a CIS-graph whenever *G*contains no induced 3-combs and 3-anti-combs, and every induced 2-comb is settled in *G*, as it was conjectured by Vasek Chvatal in early 90s. First partial results were published by his student Wenan Zang from Rutgers Center for Operations Research. Then, the statement was proven by Deng, Li, and Zang. Here we give an alternative proof, which is of independent interest; it is based on some properties of the product of two Petersen graphs.

It is an open question whether *G* is a CIS-graph if it contains no induced 4-combs and 4-anti-combs, and all induced 3-combs, 3-anti-combs, and 2-combs are settled in *G*.

We generalize the concept of CIS-graphs as follows. For an integer *d* ≥ 2 we define a *d*-*graph* \(\mathcal {G} = (V; E_1, \ldots , E_d)\) as a complete graph whose edges are colored by *d*colors (that is, partitioned into *d* sets). We say that \(\mathcal {G}\) is a CIS-*d*-graph (has the CIS-*d*-property) if \(\bigcap _{i=1}^d C_i \neq \emptyset \) whenever for each *i* = 1, …, *d* the set *C**i* is a maximal color *i*-free subset of *V* , that is, (*v*, *v′*)∉*E**i* for any *v*, *v′*∈ *C**i*. Clearly, in case *d* = 2 we return to the concept of CIS-graphs. (More accurately, CIS-2-graph is a pair of two complementary CIS-graphs.) We conjecture that each CIS-*d*-graph is a Gallai graph, that is, it contains no triangle colored by 3 distinct colors. We obtain results supporting this conjecture and also show that if it holds then characterization and recognition of CIS-*d*-graphs are easily reduced to characterization and recognition of CIS-graphs.

We also prove the following statement. Let \(\mathcal {G} = (V; E_1, \ldots , E_d)\) be a Gallai *d*-graph such that at least *d* − 1 of its *d* chromatic components are CIS-graphs, then \(\mathcal {G}\) has the CIS-*d*-property. In particular, the remaining chromatic component of \(\mathcal {G}\) is a CIS-graph too. Moreover, all 2*d* unions of *d* chromatic components of \(\mathcal {G}\) are CIS-graphs.

A model for organizing cargo transportation between two node stations connected by a railway line which contains a certain number of intermediate stations is considered. The movement of cargo is in one direction. Such a situation may occur, for example, if one of the node stations is located in a region which produce raw material for manufacturing industry located in another region, and there is another node station. The organization of freight traﬃc is performed by means of a number of technologies. These technologies determine the rules for taking on cargo at the initial node station, the rules of interaction between neighboring stations, as well as the rule of distribution of cargo to the ﬁnal node stations. The process of cargo transportation is followed by the set rule of control. For such a model, one must determine possible modes of cargo transportation and describe their properties. This model is described by a ﬁnite-dimensional system of diﬀerential equations with nonlocal linear restrictions. The class of the solution satisfying nonlocal linear restrictions is extremely narrow. It results in the need for the “correct” extension of solutions of a system of diﬀerential equations to a class of quasi-solutions having the distinctive feature of gaps in a countable number of points. It was possible numerically using the Runge–Kutta method of the fourth order to build these quasi-solutions and determine their rate of growth. Let us note that in the technical plan the main complexity consisted in obtaining quasi-solutions satisfying the nonlocal linear restrictions. Furthermore, we investigated the dependence of quasi-solutions and, in particular, sizes of gaps (jumps) of solutions on a number of parameters of the model characterizing a rule of control, technologies for transportation of cargo and intensity of giving of cargo on a node station.

Let k be a field of characteristic zero, let G be a connected reductive algebraic group over k and let g be its Lie algebra. Let k(G), respectively, k(g), be the field of k- rational functions on G, respectively, g. The conjugation action of G on itself induces the adjoint action of G on g. We investigate the question whether or not the field extensions k(G)/k(G)^G and k(g)/k(g)^G are purely transcendental. We show that the answer is the same for k(G)/k(G)^G and k(g)/k(g)^G, and reduce the problem to the case where G is simple. For simple groups we show that the answer is positive if G is split of type A_n or C_n, and negative for groups of other types, except possibly G_2. A key ingredient in the proof of the negative result is a recent formula for the unramified Brauer group of a homogeneous space with connected stabilizers. As a byproduct of our investigation we give an affirmative answer to a question of Grothendieck about the existence of a rational section of the categorical quotient morphism for the conjugating action of G on itself.

Let G be a connected semisimple algebraic group over an algebraically closed field k. In 1965 Steinberg proved that if G is simply connected, then in G there exists a closed irreducible cross-section of the set of closures of regular conjugacy classes. We prove that in arbitrary G such a cross-section exists if and only if the universal covering isogeny Ĝ → G is bijective; this answers Grothendieck's question cited in the epigraph. In particular, for char k = 0, the converse to Steinberg's theorem holds. The existence of a cross-section in G implies, at least for char k = 0, that the algebra k[G]G of class functions on G is generated by rk G elements. We describe, for arbitrary G, a minimal generating set of k[G]G and that of the representation ring of G and answer two Grothendieck's questions on constructing generating sets of k[G]G. We prove the existence of a rational (i.e., local) section of the quotient morphism for arbitrary G and the existence of a rational cross-section in G (for char k = 0, this has been proved earlier); this answers the other question cited in the epigraph. We also prove that the existence of a rational section is equivalent to the existence of a rational W-equivariant map T- - - >G/T where T is a maximal torus of G and W the Weyl group.