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

Vol 236, No 5 (2019)

Article

On the Relationship Between the Multiplicities of the Matrix Spectrum and the Signs of the Components of its Eigenvectors in a Tree-Like Structure

Buslov V.A.

Abstract

We obtain a tree-like parametric representation of the eigenspace corresponding to an eigenvalue ⋋ of a matrix G in the case where the matrix G − ⋋E has a nonzero principal basic minor. If the algebraic and geometric multiplicities of ⋋ coincide, then such a minor always exists. The coefficients of powers of the spectral parameter are sums of terms of the same sign. If there is no nonzero principal basic minor, then the tree-like form does not allow one to represent the coefficients as sums of terms of the same sign, the only exception being the case of an eigenvalue of geometric multiplicity 1.

Journal of Mathematical Sciences. 2019;236(5):477-489
pages 477-489 views

Decomposition of a 2-Connected Graph into Three Connected Subgraphs

Karpov D.V.

Abstract

Let n1+n2+n3 = n, and let G be a 2-connected graph on n vertices such that any 2-vertex cutset of G splits it into at most three parts. We prove that there exists a decomposition of the vertex set of G into three disjoint subsets V1, V2, V3 such that |Vi| = ni and the induced subgraph G(Vi) is connected for every i.

Journal of Mathematical Sciences. 2019;236(5):490-502
pages 490-502 views

For Which Graphs the Sages Can Guess Correctly the Color of at Least One Hat

Kokhas K., Latyshev A.

Abstract

Several sages wearing colored hats occupy the vertices of a graph. Each sage tries to guess the color of his own hat merely on the basis of observing the hats of his neighbors without exchanging any information. Each hat can have one of three colors. A predetermined guessing strategy is winning if it guarantees at least one correct individual guess for every assignment of colors. We completely solve the problem of describing all graphs for which the sages win.

Journal of Mathematical Sciences. 2019;236(5):503-520
pages 503-520 views

Counting Unlabelled Chord Diagrams of Maximal Genus

Krasko E.

Abstract

We enumerate maximal chord diagrams up to all isomorphisms. The enumeration formula is based on a bijection between the rooted one-vertex one-face maps on locally orientable surfaces and a certain class of symmetric chord diagrams. This result extends the result of Cori and Marcus on the enumeration of maximal chord diagrams up to rotations.

Journal of Mathematical Sciences. 2019;236(5):521-526
pages 521-526 views

Framings of Spatial Graphs

Nezhinskij V.M., Maslova Y.V.

Abstract

In the theory of spatial graphs, we state and prove an analog of the theorem on the isotopy classification of framings of classical knots.

Journal of Mathematical Sciences. 2019;236(5):527-531
pages 527-531 views

On Critical 3-Connected Graphs with Two Vertices of Degree 3. Part I

Pastor A.V.

Abstract

A 3-connected graph G is said to be critical if for any vertex υ ∈ V (G) the graph G − υ is not 3-connected. Entringer and Slater proved that any critical 3-connected graph contains at least two vertices of degree 3. In this paper, a classification of critical 3-connected graphs with two vertices of degree 3 is given in the case where these vertices are adjacent. The case of nonadjacent vertices of degree 3 will be studied in the second part of the paper, which will be published later.

Journal of Mathematical Sciences. 2019;236(5):532-541
pages 532-541 views

A Bound on the Number of Leaves in a Spanning Tree of a Connected Graph of Minimum Degree 6

Simarova E.N.

Abstract

We prove that a connected graph of minimum degree 6 has a spanning tree such that at least \( \frac{11\ }{21} \) of its vertices are leaves.

Journal of Mathematical Sciences. 2019;236(5):542-553
pages 542-553 views

Turán-Type Results for Distance Graphs in an Infinitesimal Plane Layer

Shabanov L.E.

Abstract

In this paper, we obtain a lower bound on the number of edges in a unit distance graph Γ in an infinitesimal plane layer 2 × [0, ε]d, which relates the number of edges e(Γ), the number of vertices ν(Γ), and the independence number α(Γ). Our bound \( e\left(\varGamma \right)\ge \frac{19\nu \left(\varGamma \right)-50\alpha \left(\varGamma \right)}{3} \) is a generalization of a previous bound for distance graphs in the plane and a strong improvement of Turán’s bound in the case where \( \frac{1}{5}\le \frac{\alpha \left(\varGamma \right)}{v\left(\varGamma \right)}\le \frac{2}{7} \).

Journal of Mathematical Sciences. 2019;236(5):554-578
pages 554-578 views