| Sbornik: Mathematics |
|
|
|
|
|
A circle criterion for a generalized cross graph in terms of minimal excluded minors V. P. Ilyutkoa, D. P. Ilyutkob a Faculty of Computational Mathematics and Cybernetics, Lomonosov Moscow State University, Moscow, Russia b Faculty of Mechanics and Mathematics, Lomonosov Moscow State University, Moscow, Russia
Russian version:
Matematicheskii Sbornik, 2022, Volume 213, Number 12, DOI: https://doi.org/10.4213/sm9670 
Bibliographic databases:
    § 1. IntroductionMany known properties of graphs are minor-closed, that is, closed under edge deletion, edge contraction and connected component deletion. Such properties of graphs include, for instance, their planarity, embeddability in a particular surface and knotless embeddability in three-dimensional space. Minors play a significant role in graph theory: for example, they are used in the design of polynomial-time algorithms for the decision of various graph properties such as embeddability, knotless embeddability and others. An important milestone in the development of graph theory was a series of works by Robertson, Seymour and Thomas (see [1] and the references there), in which they proved that any minor-closed property of a graph, that is, any property also shared by all of its minors, was characterized by a finite number of excluded graphs. In other words, if a graph does not possess such a property, then it contains a member of a finite list of excluded graphs as a minor. Note that the property of having the chromatic number not greater than a prescribed integer and the property of realizability as a chord diagram (of being a circle graph; see the definitions below) are not minor closed. It turns out that the property of nonrealizability as a chord diagram (of not being a circle graph) can be described in terms of a finite family of graphs and certain operations with graphs [2]. In [3] and [4] Manturov proposed to consider an analogue of minor-closed properties for cross graphs (see [5] and [6]). Cross graphs are intimately related to both graphs of general form and knot theory. For example, the Pontryagin-Kuratowski planarity criterion can be established using only cross graphs: see [7]. Another example is as follows. The property of being a bipartite graph is not minor-closed. However, if for a $4$-graph with cross structure the intersection graph of the chord diagram of a rotating circuit on it (see the definitions below) is bipartite, then all intersection graphs corresponding to all the rotating circuits are too, and this property is equivalent to the planarity of the original cross graph (see [8] and [9]; all definitions are given below). Thus, when from intersection graphs we go over to cross graphs, the property of being bipartite, which is not minor closed, turns to the minor-closed property of planarity. The aim of this work is to develop a kind of generalization of the theory of minors to cross graphs; see [3] and [4]. Namely, with each cross graph we associate an equivalence class of framed graphs with respect to certain transformations; see the definitions below. Note that this is not a one-to-one correspondence, but each graph in the class is a circle graph, which means that it can be realized as the intersection graph of a chord diagram. We consider the equivalence classes of all simple framed graphs with respect to the transformations obtained, introduce the notion of a minor so as to make the circle property of the class minor closed, and find all minimal excluded minors for the class of circle graphs. The same work was done in [10], but the main results of that paper rely on Lemmas 1.7 and 1.9, which are only partly true. The paper is organized as follows. In § 2 we introduce the main definitions. In § 3 we formulate and prove a circle criterion for a generalized cross graph. Most results were obtained by the authors using software for the Mathematica system, which they developed independently of each other. As soon as most of our results coincide with the results in [10], and those of our results that differ from [10] can be verified by hand, we dare suggesting that the list of minimal excluded minors for a circle generalized cross graph is correct. § 2. Main definitionsIn this section we give all necessary definitions. All graphs under consideration are assumed to be finite. Let $G$ be an arbitrary graph with vertex set $V(G)$ and edge set $E(G)$. An edge of the graph is the equivalence class of the two half-edges forming this edge. A vertex $v\in V(G)$ has degree $k$ if $v$ is incident to exactly $k$ half-edges. A graph all of whose vertices have the same degree $k$ is called $k$-valent or just a $k$-graph. It is convenient to assume that the free loop, that is, the graph without vertices but with one cyclic edge, is a $k$-graph for any $k$. Definition 2.1. A Hamiltonian cycle in a graph is a cycle that passes through all vertices of the graph exactly once. A chord diagram is a $3$-graph consisting of one distinguished nonoriented Hamiltonian cycle (a circle) and a set of nonoriented edges (chords) connecting points on this circle. Definition 2.2. We say that two chords are linked if the endpoints of one chord lie in the different connected components of the partition of the circle by the endpoints of the second chord. Otherwise the chords are said to be unlinked. Definition 2.3. The intersection graph (or the interlacement graph) of a chord diagram is a simple graph (that is, a graph without multiple edges or loops) whose vertices are in a one-to-one correspondence with the chords of the chord diagram and two vertices are adjacent whenever the corresponding chords are linked. A simple graph is called realizable if it is the intersection graph of an appropriate chord diagram. Definition 2.4. A $4$-graph is called a cross graph, a graph with cross structure, a graph with the structure of opposite edges, or a framed $4$-valent graph (see [3]–[6] and [8]) if for every vertex of it the four emanating half-edges are split into two pairs. The half-edges in one pair are called (formally) opposite to each other, while half-edges in different pairs are said to be adjacent. It is obvious that a simple graph is a circle graph if and only if its connected components are circle graphs. As we examine the circle property of simple graphs related to cross graphs, without loss of generality we can limit our considerations to connected cross graphs. Each connected cross graph contains an Euler tour (see [5], [8] or [11]), that is, a circuit traversing every edge of the graph exactly once. Moreover, there exists an Euler tour that moves from a half-edge to an adjacent half-edge at each vertex (see [5], [8] or [11]). Such an Euler tour is referred to as a rotating circuit. At each vertex we have one of two possibilities: either the Euler tour traverses the opposite half-edges in opposite directions or in the same direction (Figure 1). Given a rotating circuit on a cross graph, we obtain a framed chord diagram (each chord is assigned a label $0$ or $1$, which is called its framing) in accordance with the following rule. In traversing the circuit we put a point on the corresponding circle each time we visit a vertex. After that we join the points corresponding to the same vertex by an edge. A chord is assigned framing $0$ if the opposite half-edges at the corresponding vertex are opposite oriented, and framing $1$ otherwise. From a framed chord diagram one can construct a cross graph which has a rotating circuit that induces a framed chord diagram coinciding with the original framed chord diagram. There clearly are a lot of rotating circuits, and any two rotating circuits can be transformed one into the other using a sequence of transformations shown in Figure 2: see [5] and [11]. Let us generalize the notion of a cross graph. Given a framed chord diagram, we can construct its framed intersection graph by assigning the framing of the corresponding chord to each vertex. It is well known that different chord diagrams can have the same intersection graph (Figure 3), and there exist graphs that are not the intersection graphs of chord diagrams: see Figure 4 and [2]. Thus we define a generalized cross graph as an equivalence class of framed (simple) graphs with respect to certain transformations, to which we now turn. The set of vertices of a graph $G$ that are adjacent to $v$ and distinct from $v$ is called the neighbourhood of $v$ and denoted by $N_G(v)$. Definition 2.5. The local complementation of a graph $G$ at a vertex $v\in V(G)$ is the operation which toggles the adjacencies between all pairs $a,\,b\in N_G(v)$, $a\ne b$ (all other adjacencies remain unchanged). Denote the graph obtained from $G$ by local complementation at a vertex $v$ by $\mathrm{LC}(G;v)$. We define two operations on framed simple graphs: $\bullet$ $\mathrm{RC}_1$: in the graph $G$ we take two adjacent vertices $u$ and $v$ with framing $0$ and replace $G$ by the graph $\mathrm{LC}(\mathrm{LC}(\mathrm{LC}(G;u);v);u)$ (the framing of each vertex remains the same); $\bullet$ $\mathrm{RC}_2$: in the graph $G$ we take a vertex $v$ with framing $1$ and replace $G$ by the graph $\mathrm{LC}(G;v)$, changing at the same time the framing of each vertex in $N_{G}(v)$. Definition 2.6. The operation of replacing a graph $G$ by $\mathrm{LC}(\mathrm{LC}(\mathrm{LC}(G;u);v);u)$, where $u$ and $v$ are two adjacent vertices of $G$, is called the pivoting operation on $G$ at $u$ and $v$, and the graph obtained from $G$ by this operation is denoted by $\mathrm{piv}(G;u,v)$. The operation $\mathrm{RC}_1$ is called the framed pivoting transformation and $\mathrm{RC}_2$ is the framed local complementation. Remark 2.1. It is easily shown that if the vertices $u$ and $v$ are adjacent, then the graphs $\mathrm{piv}(G;u,v)$ and $\mathrm{piv}(G;v,u)$ are isomorphic. In terms of the framed intersection graphs of the corresponding chord diagrams, the modifications of rotating circuits on cross graphs shown in Figure 2 correspond to the operations $\mathrm{RC}_1$ and $\mathrm{RC}_2$. Definition 2.7. A generalized cross graph is an equivalence class of framed simple graphs with respect to the operations $\mathrm{RC}_1$ and $\mathrm{RC}_2$. § 3. A circle criterion of a generalized cross graphIt is easily seen that if some representative of a generalized cross graph is a circle graph, then any other representative of it is a circle graph too (see [12]). We say that a generalized cross graph is a circle graph if it has a representative that is a circle graph. A minor of a generalized cross graph $G$ is by definition the generalized cross graph generated by the graph obtained from a representative of $G$ by the removal of arbitrary $k$ vertices (recall that the removal of a vertex from the graph implies the removal of all edges incident to it). Note that in the case of a framed circle graph the removal of a vertex corresponds to resolving at the corresponding vertex of the cross graph, that is, to the operation Different representatives of the same generalized cross graph have the same number of vertices, and there exists a natural one-to-one correspondence between their vertices. Furthermore, the number of different minors of a generalized cross graph obtained by the removal of the same $k\geqslant0$ vertices is at most $2^k$. This is obvious in the realizable case; for the general case, see [12] and [13]. The lemma below follows from the geometric description of minors in the case of a circle generalized cross graph. Lemma 3.1. If a generalized cross graph is a circle graph, then each of its minors is a circle graph. Our aim is to give a description of all minors forbidden in a circle generalized cross graph, that is, to compose a list of graphs such that a generalized cross graph is a circle graph if and only if it contains no minors generated by any graph in the list; see [3] and [4]. Clearly, it suffices to describe the minimal excluded minors, that is, the graphs such that any of their minors on fewer vertices is a circle graph. Further, Theorem 1.1 in [2] states that a simple graph is not a circle graph if and only if there exists a graph locally equivalent to it (that is, a graph obtained from it by finitely many successive local complementations) and containing an induced subgraph isomorphic to one of the graphs shown in Figure 4. Thus, each representative of an excluded minor is locally equivalent to a graph that contains an induced subgraph isomorphic to one of the graphs in Figure 4. Recall that an induced subgraph is a subgraph obtained by the removal of some vertices from the graph in question. Let us describe all minors excluded in a circle generalized cross graph. We search for such minors with the use of the methods from [10]. Definition 3.1. A graph $H$ is called a vertex minor of a graph $G$ if $H$ is isomorphic to an induced subgraph of a graph locally equivalent to $G$. Lemma 3.2 (see [14]). Let $H$ be a vertex minor of a simple graph $G$, let $v\in V(G)\setminus V(H)$ and $w\in N_G(v)$. Then $H$ is a vertex minor of one of the three graphs $G\setminus v$, $\mathrm{LC}(G;v)\setminus v$ and $\mathrm{piv}(G;v,w)\setminus v$ (the vertex $v$ is removed from all three graphs). Remark 3.1. Note that for any two vertices $w_1,w_2\in N_G(v)$ the graphs ${\mathrm{piv}(G;v,w_1)\setminus v}$ and $\mathrm{piv}(G;v,w_2)\setminus v$ are locally equivalent. Since we consider graphs up to local equivalence, following the notation in [10] we denote the graph $\mathrm{piv}(G;v,w)\setminus v$, where $w\in N_G(v)$, by $G/v$. Definition 3.2. Let $H$ be an arbitrary simple graph. Then a simple graph $G$ is said to be $H$-unique if $H$ appears in $G$ as a vertex minor and for each vertex $v\in V(G)$ at most one of the graphs $G\setminus v$, $\mathrm{LC}(G;v)\setminus v$ and $G/v$ has a vertex minor isomorphic to $H$. Lemma 3.3 (cf. [10]). Let $G$ be a representative of a minimal excluded minor. Then $G$ is either $W_5$-, or $BW_3$-, or $W_7$-unique. Proof. The graph $G$ contains a vertex minor $H$ isomorphic to either $W_5$, or $BW_3$, or $W_7$: see [2], Theorem 1.1. Assume that $G$ is not $H$-unique. Then there exists a vertex $v$ such that at least two of the graphs $G\setminus v$, $\mathrm{LC}(G;v)\setminus v$ and $G/v$ have a vertex minor isomorphic to $H$. If $G\setminus v$ is one of them, then the generalized cross graph generated by $G\setminus v$ is an excluded minor. We arrive at a contradiction with the minimality of the excluded minor $\{G\}$.
Now assume that the graphs $\mathrm{LC}(G;v)\setminus v$ and $G/v$ have a vertex minor isomorphic to $H$. Consider the following cases (taking into account the fact that $G$ is connected): the vertex $v$ has framing $1$; the vertex $v$ has framing $0$ and there exists a vertex $w\in N_G(v)$ with framing $0$; the vertex $v$ has framing $0$ and any vertex $w\in N_G(v)$ has framing $1$. In the first case the framed graph $\mathrm{LC}(G;v)$ is a representative of the generalized cross graph $\{G\}$ generated by $G$. Consequently, $\mathrm{LC}(G;v)\setminus v$ generates an excluded minor, which means that we also arrive at a contradiction with the minimality of the excluded minor $\{G\}$. In the second case the framed graph $\mathrm{piv}(G;v,w)$ is a representative of the generalized cross graph $\{G\}$. Consequently, $G/v$ generates an excluded minor, which means that we again arrive at a contradiction with the minimality of the excluded minor $\{G\}$. In the third case the framed graph $\mathrm{LC}(\mathrm{LC}(G;w);v)$ is a representative of the generalized cross graph $\{G\}$. Since $\mathrm{LC}(\mathrm{LC}(G;w);v)\setminus v$ is locally equivalent to the graph $\mathrm{LC}(\mathrm{LC}(\mathrm{LC}(G;w);v);w)\setminus v\cong G/v$, the graph $\mathrm{LC}(\mathrm{LC}(G;w);v)\setminus v$ generates an excluded minor, which means that we obtain a contradiction with the minimality of the excluded minor $\{G\}$ again. The proof of the lemma is complete. Let us describe all $W_5$-, $BW_3$- and $W_7$-unique graphs. First, we present several lemmas which are useful for the description of such graphs. Lemma 3.4 (see [10]). Let $G$ be an $H$-unique graph and $H$ be a vertex minor of a graph $G'$ which in its turn is a vertex minor of $G$. Then $G'$ is $H$-unique too. Lemma 3.5 (see [10]). Let $H$ be a simple graph and let $k>|V(H)|$. If there exists no $H$-unique graph on $k$ vertices, then every $H$-unique graph has at most $k-1$ vertices. Lemma 3.6 (cf. [10]). 1) Every $W_5$-unique graph is locally equivalent to a graph that is isomorphic to one of the $14$ graphs shown in Figure 5. 2) Every $W_7$-unique graph is either locally equivalent to the graph $W_7$ or has a vertex minor isomorphic to $W_5$. 3) Every $BW_3$-unique graph is either locally equivalent to $BW_3$ or has a vertex minor isomorphic to $W_5$. Proof. Since an $H$-unique graph is determined up to local equivalence (see Corollary 3.1), we can assume that it contains an induced subgraph isomorphic to $H$.
1) Every $W_5$-unique graph contains at least six vertices. If a $W_5$-unique graph contains six vertices, then we can have only $W_5$ up to local equivalence (the local equivalence class has cardinality $2$). Assume that a $W_5$-unique graph contains seven vertices. Consider all nonisomorphic connected simple graphs on seven vertices that contain an induced subgraph isomorphic to $W_5$. Computer-aided search performed with the use of our program for Mathematica returns $15$ graphs, nine of which are $W_5$-unique and locally equivalent to one another. In this case we obtain only one $W_5$-unique graph $W_{5;7}$ up to local equivalence (the local equivalence class has cardinality $46$). Note that the graphs $BW_3$ and $W_7$ are not vertex minors of the graph $W_{5;7}$. Denote the set of remaining six graphs, which are not $W_5$-unique, by $\mathrm{FG}_7$. Assume that a $W_5$-unique graph contains eight vertices. Using Lemma 3.4 we consider all nonisomorphic connected simple graphs on eight vertices that contain an induced subgraph isomorphic to $W_{5;7}$ but no induced subgraphs isomorphic to any graph in $\mathrm{FG}_7$. With the use of our program we have obtained $55$ graphs, which form ten classes of local equivalence, four of which contain $W_5$-unique graphs. In this case we have four specimens of $W_5$-unique graphs: $W_{5;8.1}$, $W_{5;8.2}$, $W_{5;8.3}$ and $W_{5;8.4}$ (one representative of each class). The local equivalence classes have cardinalities $298$, $433$, $254$ and $117$, respectively. Note that the graph $W_7$ is not a vertex minor of any of $W_{5;8.1}$, $W_{5;8.2}$, $W_{5;8.3}$ and $W_{5;8.4}$, whereas $BW_3$ is a vertex minor of $W_{5;8.3}$ and $W_{5;8.4}$, and these graphs are $BW_3$-unique. Denote the set of remaining 25 graphs, which are not $W_5$-unique, by $\mathrm{FG}_8$. Assume that a $W_5$-unique graph contains nine vertices. Using Lemma 3.4 we consider all nonisomorphic connected simple graphs on nine vertices that contain induced subgraphs isomorphic to at least one of $W_{5;8.1}$, $W_{5;8.2}$, $W_{5;8.3}$ and $W_{5;8.4}$, but contain no induced subgraphs isomorphic to any graph in $\mathrm{FG}_7$ or $\mathrm{FG}_8$. With the use of our program we have obtained $278$ graphs, which form $47$ local equivalence classes, seven of which contain $W_5$-unique graphs. In this case we have obtained seven $W_5$-unique graphs $W_{5;9.1}$, $W_{5;9.2}$, $W_{5;9.3}$, $W_{5;9.4}$, $W_{5;9.5}$, $W_{5;9.6}$ and $W_{5;9.7}$ (one representative of each class). The local equivalence classes have cardinalities $806$, $818$, $844$, $305$, $1246$, $840$ and $166$, respectively. Note that $W_7$ is a vertex minor of the graphs $W_{5;9.5}$ and $W_{5;9.6}$, which are $W_7$-unique, and $BW_3$ is a vertex minor of $W_{5;9.1}$ and $W_{5;9.5}$, which are $BW_3$-unique. Denote the set of remaining 235 graphs, which are not $W_5$-unique, by $\mathrm{FG}_9$. Assume that a $W_5$-unique graph contains ten vertices. Using Lemma 3.4 we consider all nonisomorphic connected simple graphs on ten vertices that contain induced subgraphs isomorphic to at least one of the graphs $W_{5;9.1}$, $W_{5;9.2}$, $W_{5;9.3}$, $W_{5;9.4}$, $W_{5;9.5}$, $W_{5;9.6}$ and $W_{5;9.7}$ but contain no induced subgraphs isomorphic to any graph in $\mathrm{FG}_7$, $\mathrm{FG}_8$ or $\mathrm{FG}_9$. With the use of our program we have obtained $85$ graphs, which form $49$ local equivalence classes, one of which contains $W_5$-unique graphs. In this case we obtain a single $W_5$-unique graph $W_{5;10}$ (the local equivalence class has cardinality $267$). Note that $W_7$ is not a vertex minor of the graph $W_{5;10}$, while $BW_3$ is, and that $W_{5;10}$ is $BW_3$-unique. Denote the set of remaining $84$ graphs, which are not $W_5$-unique, by $\mathrm{FG}_{10}$. Considering all nonisomorphic connected simple graphs on $11$ vertices that contain an induced subgraph isomorphic to $W_{5;10}$ and no induced subgraphs isomorphic to any graph in $\mathrm{FG}_7$, $\mathrm{FG}_8$, $\mathrm{FG}_9$ or $\mathrm{FG}_{10}$, with the use of our program we have obtained three graphs, which are not $W_5$-unique. Thus, there are no $W_5$-unique graphs on more than ten vertices. 2) A $W_7$-unique graph must contain at least eight vertices. If a $W_7$-unique graph contains eight vertices, then this can only be the graph $W_7$ up to local equivalence (the local equivalence class has cardinality $22$). Assume that a $W_7$-unique graph contains nine vertices. Consider all nonisomorphic connected simple graphs on nine vertices that contain an induced subgraph isomorphic to $W_7$. With the use of our program we have obtained $35$ graphs, which form six local equivalence classes, four of which contain $W_7$-unique graphs. In this case we obtain four $W_7$-unique graphs $W_{7;9.1}$, $W_{7;9.2}$, $W_{7;9.3}$ and $W_{7;9.4}$ (one representative of each class); see Figure 6. The local equivalence classes have cardinalities $2408$, $1246$, $840$ and $672$, respectively. It remains to note that the graph $W_{7;9.2}$ is locally equivalent to $W_{5;9.5}$, and $W_{7;9.3}$ to $W_{5;9.6}$, and that $W_5$ is a vertex minor of the graphs $W_{7;9.1}$ and $W_{7;9.4}$, which are not $W_5$-unique ($W_{7;9.1}$ is $BW_3$-unique). 3) A $BW_3$-unique graph must contain at least seven vertices. If a $BW_3$-unique graph contains seven vertices, then this can only be $BW_3$ up to local equivalence (the local equivalence class has cardinality $9$). Assume that a $BW_3$-unique graph contains eight vertices. Consider all nonisomorphic connected simple graphs on eight vertices that contain an induced subgraph isomorphic to $BW_3$. With the use our program for Mathematica we have obtained $39$ graphs, which form seven classes of local equivalence, four of which contain $BW_3$-unique graphs. In this case we obtain four $BW_3$-unique graphs $BW_{3;8.1}$, $BW_{3;8.2}$, $BW_{3;8.3}$ and $BW_{3;8.4}$ (one representative of each class); see Figure 7. The local equivalence classes have cardinalities $254$, $117$, $476$ and $28$, respectively. It remains to note that the graph $BW_{3;8.1}$ is locally equivalent to $W_{5;8.3}$, and $BW_{3;8.2}$ to $W_{5;8.4}$, and that $W_5$ is a vertex minor of the graphs $BW_{3;8.3}$ and $BW_{3;8.4}$, which are not $W_5$-unique. The proof of Lemma 3.6 is complete. Remark 3.2. Lemma 1.7 in [10] states that there exist 11 $W_5$-unique graphs. As we see, this is not so. The integer under every graph in Figure 4 in [10] presumably indicates the cardinality of its local equivalence class. All these values, except the first, are not correct. Lemma 1.9 in [10] states that the graph $Q_3$, the 1-skeleton of the cube, is $BW_3$-unique. It is easily verified that this is also erroneous. Theorem 3.1. A generalized cross graph is a circle graph if and only if it contains no minors generated by any of the $166$ graphs shown in Figures 8–15 (loops at vertices correspond to framing 1, that is, exactly vertices with framing 1 are shown with loops in the figures). Proof. It follows from Lemmas 3.3 and 3.6 that the representative of each minimal excluded minor is locally equivalent to $BW_3$, $W_7$ or one of the $14$ graphs in Figure 5. For each of the $16$ graphs we consider all graphs that are locally equivalent to it, endow each graph obtained with all possible framings, partition the resulting set of graphs into equivalence classes with respect to the transformations $\mathrm{RC}_1$ and $\mathrm{RC}_2$, and check each class for being minimal. With the use of our program for Mathematica, we obtain the following results.
The graph $W_5$ admits $29$ different framings; the resulting framed graphs form five generalized cross graphs, all of which are minimal excluded minors; see Figure 8. The graph $BW_3$ admits $560$ different framings; the resulting framed graphs form $32$ generalized cross graphs, all of which are minimal excluded minors; see Figure 9. The graph $W_{5;7}$ admits $2226$ different framings; the resulting framed graphs form $114$ generalized cross graphs, $38$ of which are minimal excluded minors; see Figure 10. The graph $W_7$ admits $2711$ different framings; the resulting framed graphs form $48$ generalized cross graphs, all of which are minimal excluded minors; see Figure 11. The graph $W_{5;8.1}$ admits $5128$ different framings; the resulting framed graphs form $561$ generalized cross graphs, three of which are minimal excluded minors; see Figure 12. The graph $W_{5;8.2}$ admits $16594$ different framings; the resulting framed graphs form $933$ generalized cross graphs, $21$ of which are minimal excluded minors; see Figure 13. The graph $W_{5;8.3}$ admits $7840$ different framings; the resulting framed graphs form $579$ generalized cross graphs, $13$ of which are minimal excluded minors; see Figure 14. The graphs $W_{5;8.4}$, $W_{5;9.5}$, and $W_{5;9.6}$ admit $1484$, $5536$, and $6848$ different framings, respectively; the resulting framed graphs form $142$, $1330$, and $894$ generalized cross graphs, respectively, and none of these is a minimal excluded minor. The graphs $W_{5;9.1}$, $W_{5;9.2}$, $W_{5;9.3}$, $W_{5;9.4}$, $W_{5;9.7}$ and $W_{5;10}$ admit $5568$, $5960$, $7290$, $1690$, $662$ and $1210$ framings, respectively; the resulting framed graphs form $1339$, $1398$, $1490$, $530$, $267$ and $441$ generalized cross graphs, respectively, and six of them (one for every original graph) are minimal excluded minors; see Figure 15. The proof of Theorem 3.1 is complete.Remark 3.3. Thus, we obtain the same list of minimal excluded minors as the one in Figure 5 in [10]. The authors are grateful to V. O. Manturov and I. M. Nikonov for their attention to this work and helpful comments. 
Citation in format AMSBIB
\Bibitem{IlyIly22} |
|
||||||||||||||||||||||||||
|
Contact us: |
Terms of Use
|
Registration to the website |
Logotypes |
|