### Article

## Characterizing and decomposing classes of threshold, split, and bipartite graphs via 1‐Sperner hypergraphs

A hypergraph is said to be 1-Sperner if for every two hyperedges the smallest of their two set differences is of size one. We present several applications of 1-Sperner hypergraphs to graphs. First, we consider several ways of associating hypergraphs to graphs, namely, vertex cover, clique, independent set, dominating set, and closed neighborhood hypergraphs. For each of them, we characterize graphs yielding 1-Sperner hypergraphs. These results give new characterizations of threshold and domishold graphs. Second, we apply a characterization of 1-Sperner hypergraphs to derive decomposition theorems for two classes of split graphs, a class of bipartite graphs, and a class of cobipartite graphs. These decomposition theorems, based on certain matrix partitions, lead to new classes of graphs of bounded clique-width and new polynomially solvable cases of three basic domination problems: domination, total domination, and connected domination.

We study the computational complexity of the dominating set problem for hereditary graph classes, i.e., classes of simple unlabeled graphs closed under deletion of vertices. Every hereditary class can be defined by a set of its forbidden induced subgraphs. There are numerous open cases for the complexity of the problem even for hereditary classes with small forbidden structures. We completely determine the complexity of the problem for classes defined by forbidding a five-vertex path and any set of fragments with at most five vertices. Additionally, we also prove polynomial-time solvability of the problem for some two classes of a similar type. The notion of a boundary class is a helpful tool for analyzing the computational complexity of graph problems in the family of hereditary classes. Three boundary classes were known for the dominating set problem prior to this paper. We present a new boundary class for it.

The book contains the necessary information from the algorithm theory, graph theory, combinatorics. It is considered partially recursive functions, Turing machines, some versions of the algorithms (associative calculus, the system of substitutions, grammars, Post's productions, Marcov's normal algorithms, operator algorithms). The main types of graphs are described (multigraphs, pseudographs, Eulerian graphs, Hamiltonian graphs, trees, bipartite graphs, matchings, Petri nets, planar graphs, transport nets). Some algorithms often used in practice on graphs are given. It is considered classical combinatorial configurations and their generating functions, recurrent sequences. It is put in a basis of the book long-term experience of teaching by authors the discipline «Discrete mathematics» at the business informatics faculty, at the computer science faculty* *of National Research University Higher School of Economics, and at the automatics and computer technique faculty of National research university Moscow power engineering institute. The book is intended for the students of a bachelor degree, trained at the computer science faculties in the directions 09.03.01 Informatics and computational technique, 09.03.02 Informational systems and technologies, 09.03.03 Applied informatics, 09.03.04 Software Engineering, and also for IT experts and developers of software products.

As communications are progressing, transport networks need to be monitored, more specifically, camera surveillance of violations is needed. Standards are being developed on how to install cameras, and the question of efficiently distributing surveillance devices across the road network ensue. This task is addressed in this paper by using the methods of the cooperative game theory. The vertex cover game is introduced, and its properties are studied. Since surveillance cameras are to cover all areas of the network, the characteristic function depends on the vertex covers of the graph. The Shapley–Shubik index is used as the measure of centrality. The Shapley–Shubik index is shown to be efficient in a vertex cover game for the allocation of cameras in a transport network. Proceeding from the Shapley–Shubik indices calculated in this study, recommendations were given for the allocation of surveillance cameras in a specific transport network in a district of the City of Petrozavodsk, Russia.

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.

We describe the hereditary class of graphs, whose every subgraph has the property that the maximum number of disjoint 5-paths (paths on 5 vertices) is equal to the minimum size of the sets of vertices having nonempty intersection with the vertex set of each 5-path. We describe this class in terms of the "forbidden subgraphs" and give an alternative description, using some operations on pseudographs.

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.