


Vol 212, No 6 (2016)
- Year: 2016
- Articles: 8
- URL: https://journal-vniispk.ru/1072-3374/issue/view/14714
Article
On Coefficients of the Characteristic Polynomial of the Laplace Matrix of a Weighted Digraph and the All Minors Theorem
Abstract
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.



The Tree of Cuts and Minimal k-Connected Graphs
Abstract
A cut of a k-connected graph G is a k-element cutset of it, which contains at least one edge. The tree of cuts of a set, consisting of pairwise independent cuts of a k-connected graph, is defined in the following way. Its vertices are the cuts of the set
and the parts of the decomposition of G induced by these cuts. A part A is adjacent to a cut S if and only if A contains all the vertices of S and exactly one end of each edge of S. It is proved that the defined graph is a tree, some properties of which are similar to the corresponding properties of the classic tree of blocks and cutpoints.
In the second part of the paper, the tree of cuts is used to study minimal k-connected graphs for k ≤ 5. Bibliography: 11 titles.



Minimal k-Connected Graphs with Minimal Number of Vertices of Degree k
Abstract
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 Gk,T, where T is a tree the maximal vertex degree of which is at most k + 1. The graph Gk,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 a1, . . . , akare the corresponding vertices of the copies of T, then k + 1 − j new vertices of degree k, which are adjacent to {a1, . . . , ak}, are added. Bibliography: 10 titles.






On a Heawood-Type Problem for Maps with Tangencies
Abstract
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.



On the Structure of C3-Critical Minimal 6-Connected Graphs
Abstract
In this paper, C3-critical minimal 6-connected graphs are studied; they are defined as 6-connected graphs, any subgraph of which obtained by edge deletion is not 6-connected and in which any clique on at most 3 vertices is contained in a 6-cutset. It is proved that more than\( \frac{5}{9} \)of all vertices of such a graph have degree 6. Bibliography: 18 titles.



Almost Regular Decompositions of a Graph
Abstract
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 k0< k, there is at most one clique of size k0in this partition. Bibliography: 2 titles.



On Graphs, Which Can be Drawn on an Orientable Surface with Small Number of Intersections on an Edge
Abstract
Let k and g be nonnegative integers. A graph is said to be k-nearly g-spherical if it can be drawn on an orientable surface of genus g so that each edge intersects at most k other edges in interior points. It is proved that if k ≤ 4, then the edge number of a k-nearly g-spherical graph on v vertices does not exceed (k + 3)(v + 2g − 2). It is also shown that the chromatic number of a k-nearly g-spherical graph does not exceed\( \frac{2k+7+\sqrt{4{k}^2+12k+1+16\left(k+3\right)g}}{2} \). Bibliography: 4 titles.


