| Switching of G and of Σ are related: switching the same vertices in both yields a graph H and its corresponding signed complete graph. | Переключения G и Σ связаны - переключение одних и тех же вершин даёт граф H и соответствующий ему знаковый полный граф. |
| Additionally, every outer-1-planar graph (that is, a graph drawn with one crossing per edge with all vertices on the outer face of the drawing) has a RAC drawing. | Кроме того, любой 1-внешнепланарный граф (это граф с одним пересечением на ребро, в котором все вершины лежат на внешней грани рисунка) имеет РПУ представление. |
| In this way, the path decomposition nodes containing v correspond to the representative points in the interval for v. The intersection graph of the intervals formed from the vertices of G is an interval graph that contains G as a subgraph. | Тогда древесная декомпозиция вершин, содержащих v, соответствует представляющим (т.е. конечным точкам) интервала для v. Граф пересечений интервалов, образованный из вершин G - это интервальный граф, содержащий G в качестве подграфа. |
| If a graph is represented with segments having only k directions and no two segments belong to the same line, then the graph can be colored using k colors, one color for each direction. | Если граф представим отрезками, имеющими только к направления, и никакие два отрезка не лежат на одной прямой, граф можно выкрасить с помощью к цветов, по одному цвету на каждое направление. |
| If H is a two-vertex complete graph K2, then for any graph G, the rooted product of G and H has domination number exactly half of its number of vertices. | Если Н - полный граф с двумя вершинами K2, то для любого графа G корневое произведение графов G и H имеет число доминирования, равное ровно половине числа его вершин. |
| Instead of using a row or column of a grid graph, George partitions the graph into four pieces by using the union of a row and a column as a separator. | Вместо использования строк и столбцов графа, Джордж разделяет граф на четыре части путём объединения строк и столбцов в качестве сепаратора. |
| If a family of graphs has bounded clique-width, then either it has bounded treewidth or every complete bipartite graph is a subgraph of a graph in the family. | Если семейство графов имеет ограниченную кликовую ширину, то оно либо имеет ограниченную древесную ширину, либо любой полный двудольный граф является подграфом какого-либо графа в семействе. |
| If a graph G is factor-critical, then so is the Mycielskian of G. For instance, the Grötzsch graph, the Mycielskian of a five-vertex cycle-graph, is factor-critical. | Если граф G является фактор-критическим, то он является мычельскианом графа G. Например, граф Грёча, мычельскиан цикла с пятью вершинами, является фактор-критическим. |
| A graph G is a block graph if and only if the intersection of every two connected subsets of vertices of G is empty or connected. | Граф G {\displaystyle G} является блоковым тогда и только тогда, когда пересечение любых двух связных подмножеств вершин графа G {\displaystyle G} либо пусто, либо связно. |
| A poset is graded if and only if every connected component of its comparability graph is graded, so further characterizations will suppose this comparability graph to be connected. | ЧУМ является градуированным тогда и только тогда, когда любая связная компонента его графа сравнимости является градуированной, так что дальнейшее описание предполагает, что этот граф сравнимости связен. |
| A closely related configuration, the Möbius-Kantor configuration formed by two mutually inscribed quadrilaterals, has the Möbius-Kantor graph, a subgraph of Q4, as its Levi graph. | Близкая конфигурация Мёбиуса - Кантора, образованная двумя взаимно вписанными четырёхугольниками, имеет граф Мёбиуса-Кантора, подграф графа Q4, в качестве графа Леви. |
| In particular, there is an automorphism taking any ordered pair of adjacent vertices to any other such ordered pair, so the Rado graph is a symmetric graph. | В частности, существует автоморфизм, переводящий любую упорядоченную пару смежных в любую другую такую пару, так что граф Радо является симметричным графом. |
| These graphs are of some importance in lattice theory as well as in graph drawing: the Hasse diagram of a two-dimensional lattice is necessarily st-planar, and every transitively reduced st-planar graph represents a two-dimensional lattice in this way. | Эти графы играют важную роль в теории решёток, а также в визуализации графов - диаграмма Хассе двумерной решётки обязательно st-планарна, а любой транзитивно сокращённый st-планарный граф представляет двумерную решётку этим способом. |
| The Erdős-Stone theorem extends Turán's theorem by bounding the number of edges in a graph that does not have a fixed Turán graph as a subgraph. | Теорема Эрдёша-Стоуна расширяет теорему Турана, ограничивая число рёбер в графе, не имеющем фиксированный граф Турана в качестве подграфа. |
| A graph G is a permutation graph if and only if both G and its complement G - {\displaystyle {\overline {G}}} are comparability graphs. | Граф G является графом перестановки тогда и только тогда, когда и G и его дополнение G - {\displaystyle {\overline {G}}} являются графами сравнимости. |
| Choosing S to be any of these central rows or columns, and removing S from the graph, partitions the graph into two smaller connected subgraphs A and B, each of which has at most n/2 vertices. | Выбрав в качестве S эти центральные строки и столбцы и удалив S из графа, разбиваем граф на два меньших связных подграфа A и B, каждый из которых имеет не более n/2 вершин. |
| The bipartite double cover may also be constructed using adjacency matrices (as described below) or as the derived graph of a voltage graph in which each edge of G is labeled by the nonzero element of the two-element group. | Двудольное двойное покрытие может также быть построено с помощью матриц смежности (как описано ниже) или как производный граф графа напряжений, в котором каждое ребро графа G помечено ненулевыми элементами двухэлементной группы. |
| The Levi graph of the Fano plane is the Heawood graph, in which the triangles of the Fano plane are represented by 6-cycles. | Графом Леви плоскости Фано служит граф Хивуда, в котором треугольники плоскости Фано представлены 6-циклами. |
| The pathwidth of an arbitrary undirected graph G may be defined as the smallest number w such that there exists an interval graph H containing G as a subgraph, with the largest clique in H having w + 1 vertices. | Путевая ширина произвольного неориентированного графа G может быть определена как наименьшее число w, такое, что существует интервальный граф H, содержащий G в качестве подграфа, такой, что наибольшая клика графа H имеет w + 1 вершин. |
| The Franklin graph is named after Philip Franklin, who disproved the Heawood conjecture on the number of colors needed when a two-dimensional surface is partitioned into cells by a graph embedding. | Граф назван именем Филипа Франклина, опровергшего гипотезу Хивуда о числе цветов, необходимых для раскраски двумерных поверхностей, разделённых на ячейки при вложении графа. |
| One graph from the tiny nucleus and the other from the vastness of space point to the same magical atom. | Один граф от крошечного ядра и другой от необъятности места указывают на тот же самый волшебный атом. |
| The graph shows which packages are out of date in a private archive and the order in which they should be rebuilt. | Граф показывает, какие пакеты в частном архиве устарели, и порядок их пересборки. |
| As a simple example, a connected graph with diameter D will have at least D+1 distinct values in its spectrum. | В качестве простого примера, связный граф с диаметром D будет иметь по меньшей мере D+1 различных значений в своём спектре. |
| If this graph is also a forest, then we call this a F(a, b)-decomposition. | Если этот граф тоже является лесом, такое разложение называется F(a, b)-разложением. |
| Every chordal graph is strangulated, because the only induced cycles in chordal graphs are triangles, so there are no longer cycles to delete. | Любой хордальный граф является сжатым, поскольку лишь порождённые циклы в хордальных графах являются треугольниками, так что нет больше циклов для удаления. |