Open Access Open Access  Restricted Access Access granted  Restricted Access Subscription Access

Vol 212, No 6 (2016)

Article

On Coefficients of the Characteristic Polynomial of the Laplace Matrix of a Weighted Digraph and the All Minors Theorem

Buslov V.A.

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.

Journal of Mathematical Sciences. 2016;212(6):643-653
pages 643-653 views

The Tree of Cuts and Minimal k-Connected Graphs

Karpov D.V.

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 setand 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.

Journal of Mathematical Sciences. 2016;212(6):654-665
pages 654-665 views

Minimal k-Connected Graphs with Minimal Number of Vertices of Degree k

Karpov D.V.

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.

Journal of Mathematical Sciences. 2016;212(6):666-682
pages 666-682 views

Deleting Vertices from a 2-Connected Graph with Preserving 2-Connectedness

Karpov D.V.

Abstract

Let G be a 2-connected graph, and let W be a set of internal vertices of block parts of G that contains at least one vertex in each of these parts. It is proved that the graph G−W is 2-connected.

Journal of Mathematical Sciences. 2016;212(6):683-687
pages 683-687 views

On a Heawood-Type Problem for Maps with Tangencies

Nenashev G.V.

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.

Journal of Mathematical Sciences. 2016;212(6):688-697
pages 688-697 views

On the Structure of C3-Critical Minimal 6-Connected Graphs

Pastor A.V.

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.

Journal of Mathematical Sciences. 2016;212(6):698-707
pages 698-707 views

Almost Regular Decompositions of a Graph

Savenkov K.S.

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.

Journal of Mathematical Sciences. 2016;212(6):708-713
pages 708-713 views

On Graphs, Which Can be Drawn on an Orientable Surface with Small Number of Intersections on an Edge

Samoilova O.E.

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.

Journal of Mathematical Sciences. 2016;212(6):714-720
pages 714-720 views