Открытый доступ
Доступ предоставлен
Только для подписчиков
Том 236, № 5 (2019)
- Год: 2019
- Статей: 8
- URL: https://ogarev-online.ru/1072-3374/issue/view/14982
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
Аннотация
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.
477-489
Decomposition of a 2-Connected Graph into Three Connected Subgraphs
Аннотация
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.
490-502
For Which Graphs the Sages Can Guess Correctly the Color of at Least One Hat
Аннотация
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.
503-520
Counting Unlabelled Chord Diagrams of Maximal Genus
Аннотация
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.
521-526
527-531
On Critical 3-Connected Graphs with Two Vertices of Degree 3. Part I
Аннотация
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.
532-541
542-553
Turán-Type Results for Distance Graphs in an Infinitesimal Plane Layer
Аннотация
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} \).
554-578