Vol 212, No 6 (2016)

Let L be the Laplace matrix of a weighted digraph. The aim of the paper is to establish a simple way for computing any coefficient of the characteristic polynomial of L as a constant sign sum over the incoming spanning forests. The idea is to express L as the product of generalized (weighted) incidence matrices. It turns out that the minors of them can be studied in terms of the tree-like structure of the digraph. This makes it possible to compute the minors of L.

A graph is k-connected if it has at least k+1 vertices and remains connected after deleting any k−1 vertices. A k-connected graph is said to be minimal if any its subgraph obtained by deleting any edge is not k-connected. W. Mader proved that any minimal k-connected graph with n vertices has at least\( \frac{\left(k-1\right)n+2k}{2k-1} \)vertices of degree k. The main result of the present paper is that any minimal k-connected graph with minimal number of vertices of degree k is isomorphic to a graph G_k,T, where T is a tree the maximal vertex degree of which is at most k + 1. The graph G_k,Tis constructed from k disjoint copies of the tree T in the following way. If a is a vertex of T of degree j and a₁, . . . , a_kare the corresponding vertices of the copies of T, then k + 1 − j new vertices of degree k, which are adjacent to {a₁, . . . , a_k}, are added. Bibliography: 10 titles.

The class of maps on a surface of genus g > 0 such that each point belongs to at most k ≥ 3 regions is studied. The problem is to estimate in terms of g and k the chromatic number of such a map (it is assumed that the regions having a common point must have distinct colors). In general case, an upper bound of the chromatic number is established. For k = 4, it is proved that the problem is equivalent to finding the maximal chromatic number for analogs of 1-planar graphs on a surface of genus g. In this case, a more strong bound is obtained and a method of constructing examples, for which this bound is achieved, is presented. In addition, for analogs of 2-planar graphs on a surface of genus g, an upper bound on maximal chromatic number is proved.

Let k ≤ 8 be a positive integer, and let G be a graph on n vertices such that the degree of each its vertex is at least\( \frac{k-1}{k} \). It is proved that the vertex set of G can be partitioned into several cliques of size at most k so that for each positive integer k₀< k, there is at most one clique of size k₀in this partition. Bibliography: 2 titles.