ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 23 (2023) #P4.05
https://doi.org/10.26493/1855-3974.2853.b51
(Also available at http://amc-journal.eu)
Domination and independence numbers of large
2-crossing-critical graphs*
Vesna Iršič † , Maruša Lekše
Faculty of Mathematics and Physics, University of Ljubljana, Slovenia and
Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia
Mihael Pačnik, Petra Podlogar, Martin Praček
Faculty of Mathematics and Physics, University of Ljubljana, Slovenia
Received 23 March 2022, accepted 10 January 2023, published online 20 March 2023
Abstract
After 2-crossing-critical graphs were characterized in 2016, their most general subfam-
ily, large 3-connected 2-crossing-critical graphs, has attracted separate attention. This paper
presents sharp upper and lower bounds for their domination and independence numbers.
Keywords: Crossing-critical graphs, domination number, independence number.
Math. Subj. Class. (2020): 05C10, 05C62, 05C69
1 Introduction
The crossing number cr(G) of a graph G is the smallest number of edge crossings in a
drawing of G in the plane. The topic has been widely studied, see for example [7, 8, 17, 18,
20]. A graph G is k-crossing-critical if cr(G) ≥ k, but every proper subgraph H of G has
cr(H) < k. Note that subdividing an edge or its inverse operation (suppressing a vertex)
*The authors were introduced to the structure of 2-crossing-critical graphs in a workshop at the University of
Ljubljana, organized by prof. dr. Drago Bokal. We thank him for several illuminating conversations and ideas.
We would also like to thank Sandi Klavžar, Alen Vegi Kalamar, and Simon Brezovnik for co-organizing the
workshop. We would also like to thank the anonymous referees for valuable suggestions, especially for the idea
of how to simplify the proof of Theorem 3.4.
†Corresponding author. V. I. was supported by a postdoctoral fellowship at the Simon Fraser University
(Canada) and by the Slovenian Research Agency (research core funding P1-0297 and projects J1-2452, J1-1693,
N1-0095, N1-0218).
E-mail addresses: vesna.irsic@fmf.uni-lj.si (Vesna Iršič), marusa.lekse@imfm.si (Maruša Lekše),
mihapac@gmail.com (Mihael Pačnik), petra.podlogar@hotmail.com (Petra Podlogar), mpracek299@gmail.com
(Martin Praček)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
2 Ars Math. Contemp. 23 (2023) #P4.05
do not affect the crossing number of a graph. Thus we can restrict our studies to graphs
without degree 2 vertices. Under this restriction, Kuratowski’s Theorem tells us that the
only 1-crossing-critical graphs are K5 and K3,3. The classification of 2-crossing-critical
graphs has been of interest since the 1980s. Partial results on the topic have been reported
in [2, 9, 12, 16, 19], and some related results can be found in [1, 10, 13]. Crossing numbers
of graphs with a tile structure have been studied in [14, 15]. Finally, Bokal, Oporewski,
Richter, and Salazar [6] provided an almost complete characterization of 2-crossing-critical
graphs. In particular, they describe a tile structure of large 3-connected 2-crossing-critical
graphs (i.e., all but finitely many 3-connected 2-crossing-critical graphs). Recently, the
degree properties of crossing-critical graphs have been studied in [3, 5, 11].
The above-mentioned large 3-connected 2-crossing-critical graphs have since attracted
separate attention, see [4, 21, 22]. In [21, 22], the Hamiltonicity of these graphs is dis-
cussed, and the number of all Hamiltonian cycles is determined. In [4], several additional
properties of large 3-connected 2-crossing-critical graphs have been studied. In particular,
the number of vertices and edges can be determined from the signature of a graph, and
several results regarding their chromatic number, chromatic index, and tree-width are pre-
sented. In the present paper, we extend the studies of large 3-connected 2-crossing-critical
graphs to their domination and independence numbers.
The rest of the paper is organized as follows. In the next section, necessary definitions
and known results are listed. In Section 3, the sharp upper and lower bounds for the domi-
nation number of large 3-connected 2-crossing-critical graphs are given, while in Section 4
analogous results are proved for their independence number.
2 Preliminaries
Let G be a graph. Its vertex set is denoted by V (G) and its edge set by E(G). The (open)
neighborhood of a vertex v ∈ V (G) is N(v) = {u ∈ V (G); uv ∈ E(G)} and the closed
neighborhood of v is N [v] = {v}∪N(v). Similarly, for D ⊆ V (G), N [D] =
⋃
v∈D N [v]
is the closed neighborhood of D. Note also that [n] = {1, . . . , n} and that the reversed
sequence of a sequence a is denoted by a.
We now recall the definitions of the domination number and the independence number.
Definition 2.1. Let G be a graph. A subset D ⊆ V (G) dominates the set of vertices
X ⊆ V (G) if X ⊆ N [D]. If N [D] = V (G), then D is a dominating set of G. The
domination number γ(G) of a graph G is the size of a smallest dominating set in G.
Definition 2.2. Let G be a graph. A subset X ⊆ V (G) is independent if none of the
vertices from X are adjacent. The independence number α(G) of the graph G is the size
of a largest independent set.
In the rest of the section, we recall the characterization of 2-crossing-critical graphs
and provide the necessary definitions which help us describe large 3-connected 2-crossing-
critical graphs, i.e., graphs studied in this paper. Note that vertices of degrees 1 and 2 do
not affect the crossing number, thus the assumption that the minimum degree is at least
3 is reasonable. Note also that V10 is the graph obtained from C10 by adding the five
diagonal edges. We quote the following theorem from [6]. The detailed explanation of the
terminology used in this theorem is given afterwards.
Theorem 2.3 ([6, Theorem 1.1]). Let G be a 2-crossing-critical graph with a minimum
degree of at least 3. Then one of the following holds.
V. Iršič et al.: Domination and independence numbers of large 2-crossing-critical graphs 3
(i) G is 3-connected, contains a subdivision of V10, and has a very particular twisted
Möbius band tile structure, with each tile isomorphic to one of 42 possibilities.
(ii) G is 3-connected, does not have a subdivision of V10, and has at most 3 million
vertices.
(iii) G is not 3-connected and is one of 49 particular examples.
(iv) G is 2- but not 3-connected and is obtained from a 3-connected 2-crossing-critical
graph by replacing digons with digonal paths.
In the present paper, we study graphs from (i), i.e., 3-connected 2-crossing-critical
graphs that contain a subdivision of V10. Since 3-connected 2-crossing-critical graphs that
do not contain a subdivision of V10 have at most 3 million vertices, we may call graphs from
Theorem 2.3(i) large 3-connected 2-crossing-critical graphs or large 3-con 2-cc graphs for
short. This abbreviation is used throughout the paper. Note that it would also be interesting
to study other subclasses of graphs, especially graphs from (iv). However, like in [4], we
restrict our studies to graphs from (i).
To understand the tile structure of large 3-con 2-cc graphs, we need the following defi-
nitions that first appeared in [14, 15].
Definition 2.4. 1. A tile is a triplet T = (G,λ, ρ), where G is a graph and λ, ρ are
sequences of pairwise distinct vertices of G, where no vertex of G appears in both λ
and ρ. The left wall of T is λ, and the right wall of T is ρ.
2. A tile drawing is a drawing D of G in the unit square [0, 1] × [0, 1] for which the
intersection of the boundary of the square with D contains precisely the images of
the left wall λ and the right wall ρ, and these are drawn in {0}×[0, 1] and {1}×[0, 1],
respectively, such that the y-coordinates of the vertices are increasing with respect to
their orders in the sequences λ and ρ.
3. The tiles T = (G,λ, ρ) and T ′ = (G′, λ′, ρ′) are compatible if |ρ| = |λ′|.
4. A sequence (T0, . . . , Tm) of tiles is compatible if Ti−1 is compatible with Ti for
every i ∈ [m].
5. The join of compatible tiles (G,λ, ρ) and (G′, λ′, ρ′) is the tile, denoted as (G,λ, ρ)⊗
(G′, λ′, ρ′), whose graph is obtained from G and G′ by identifying the sequence ρ
term by term with the sequence λ′. The left wall of the obtained tile is λ and the right
wall is ρ′.
6. The join ⊗T of a compatible sequence T = (T0, . . . , Tm) of tiles is defined as
T0 ⊗ · · · ⊗ Tm.
7. A tile T is cyclically-compatible if T is compatible with itself. For a cyclically-
compatible tile T , the cyclization of T is the graph ◦T obtained by identifying the
respective vertices of the left wall with the right wall. Cyclization of a cyclically-
compatible sequence of tiles is ◦T = ◦(⊗T ).
8. Let T = (G,λ, ρ) be a tile. The right-inverted tile of T is T ↕ = (G,λ, ρ). The
left-inverted tile of T is ↕T = (G,λ, ρ). The inverted tile is ↕T ↕ = (G,λ, ρ). The
reversed tile is T↔ = (G, ρ, λ).
4 Ars Math. Contemp. 23 (2023) #P4.05
Note that ⊗T in Definition 2.4, 6. is well-defined since ⊗ is associative.
Definition 2.5. The set S of tiles consists of tiles obtained as a combination of one of the
two frames shown in Figure 1 and one of the 13 pictures shown in Figure 2 in such a way
that a picture is inserted into a frame by identifying the two geometric squares. (This can
mean subdividing the frame’s square.) A given picture can be inserted into a frame either
with the given orientation or with a 180◦ rotation.
Figure 1: Both possible frames.
Figure 2: All possible pictures. For later need, the red vertices mark a dominating set of
each of them.
Note that each picture yields either two or four tiles in S. Altogether the set S contains
42 different tiles. For example, in Figure 3 we see that picture V IA yields four different
tiles.
We can now define the tile structure of graphs that are of our interest. Their definition
first appeared in [6].
Definition 2.6. The set T (S) consists of all graphs of the form ◦((⊗T )↕), where T is
a sequence (T0,↕ T
↕
1 , T2, . . . ,
↕ T
↕
2m−1, T2m), where m ≥ 1 and Ti ∈ S for every i ∈
{0, . . . , 2m}. The obtained vertices of degree 2 are suppressed.
Suppressing a vertex of degree 2 is the inverse operation to subdividing an edge, and
it does not affect the crossing number of a graph. Note that for the case of calculating the
domination and independence numbers of graphs, double edges can be replaced with single
ones without changing the invariant.
V. Iršič et al.: Domination and independence numbers of large 2-crossing-critical graphs 5
Figure 3: All possible tiles that can be obtained from picture V IA.
Theorem 2.7 ([6, Theorems 2.18 and 2.19]). Each graph from T (S) is 3-connected and
2-crossing-critical. Moreover, all but finitely many 3-connected 2-crossing-critical graphs
are contained in T (S).
Theorem 2.7 gives a nice representation of large 3-con 2-cc graphs, i.e., graphs from
Theorem 2.3(i).
Graphs from the set T (S) can be described as sequences over the alphabet Σ =
{L, d,A,B,D,H, I, V } (see [22]). A signature of a tile T is
sig(T ) = Pt IdPb Fr,
where Pt ∈ {A,B,D,H, V } describes the top path of the picture, Id ∈ {I, ∅} indicates
a possible identifier of the picture, Pb ∈ {A,B,D, V, ∅} describes the bottom path of the
picture, and Fr ∈ {L, dL} describes the frame. Here, ∅ labels the empty word. See
Figure 1 for possible signatures of frames (Fr), Figure 2 for all possible signatures of
pictures (Pt IdPb), and Figure 3 for an additional example of how to describe a tile with
its signature.
For a graph G ∈ T (S), G = ◦((⊗T )↕) = (T0,↕ T ↕1 , T2, . . . ,↕ T
↕
2m−1, T2m), a signa-
ture is defined as
sig(G) = sig(T0) sig(T1) · · · sig(T2m).
Additionally, #X denotes the number of occurrences of X in sig(G), where X ∈ Σ. Given
a tile T , the join of a sequence of k tiles, starting with T and then alternating between T
and T ↕, is denoted by k · T .
3 Domination number
In this section, we present an upper bound and a lower bound for the domination number
of large 3-con 2-cc graphs, including equality cases for both bounds.
3.1 Upper bound
Theorem 3.1. If G is a large 3-con 2-cc graph, then
γ(G) ≤ #A+#B +#D +#V + 2 ·#H −#AIV −#V IA.
6 Ars Math. Contemp. 23 (2023) #P4.05
Proof. Each vertex lies on at least one picture. Thus, if D ⊆ V (G) dominates all vertices
in each picture, then D is a dominating set of G. Inside each picture we have at least one
path (by path we mean the top and the bottom path as in the definition of the signature of
a tile). We can see that domination of A, B, D, and V requires at least one vertex, while
domination of H requires two vertices. The only exceptions are pictures AIV and V IA,
where domination of the picture only requires one vertex and not two, which would be
the result of the summation of domination numbers of paths A and V . Figure 2 shows all
possible pictures with marked smallest dominating sets.
Edges between pictures only add edges between vertices and lower the domination
number. This means that the domination number has an upper bound of the sum of domi-
nation numbers for individual paths.
The upper bound from Theorem 3.1 is sharp, which can be seen in the following two
examples. They also show that the number of frames L and dL does not affect the upper
bound.
Example 3.2. Let G1 = n · V BdL, where n ≥ 3 is an odd number. Figure 4 shows a
dominating set of size 2n, meaning γ(G1) ≤ 2n. The formula from Theorem 3.1 shows
the same, as #A+#B +#D +#V + 2 ·#H −#AIV −#V IA = 2n.
Figure 4: Graph G1 with a marked dominating set of size 2n. Note that to obtain the desired
graph, vertices a are identified, vertices b are identified, and after this vertices of degree 2
are suppressed. The same simplification of drawings is used for the rest of the paper.
Assume γ(G1) < 2n. The Pigeonhole principle says that there exists at least one
picture, which is dominated by at most one vertex. Vertices in the corners of the picture can
be dominated by vertices from neighboring pictures. The remaining three inner vertices,
which we get from B and V and are painted orange in Figure 5, are yet to be dominated.
Since these three vertices cannot be dominated by one vertex, we need at least two vertices
to dominate this picture, which leads to a contradiction. Therefore γ(G1) ≥ 2n.
Figure 5: Picture V B, where we require that the inner vertices, marked orange, are domi-
nated by one vertex.
From this, it follows that γ(G1) = 2n.
Example 3.3. Let G2 = n · AIV L, where n ≥ 3 is an odd number. We can find a
dominating set of size n (see Figure 6), thus γ(G2) ≤ n. This also follows from the
formula in Theorem 3.1, as #A+#B +#D +#V + 2 ·#H −#AIV −#V IA = n.
V. Iršič et al.: Domination and independence numbers of large 2-crossing-critical graphs 7
Figure 6: Graph G2 with a marked dominating set of size n.
We next show that γ(G2) ≥ n. Divide the graph G2 into n disjoint subgraphs, as
shown in Figure 7. Each subgraph is induced on the closed neighborhood of the degree 3
vertex and is isomorphic to the paw graph. The position of degree 3 vertices in G2 ensures
that the obtained n subgraphs are all pairwise disjoint. We notice that the middle vertex of
each subgraph (the vertex of degree 3) can only be dominated by one of the vertices in the
same subgraph. Hence we must choose at least one vertex from each one of the n disjoint
subgraphs, which means that γ(G2) ≥ n.
Figure 7: Graph G2 with disjoint subgraphs marked orange and the middle vertex of each
subgraph marked blue. Recall that when vertex a is identified, the obtained vertex of degree
2 is suppressed.
It follows that γ(G2) = n.
3.2 Lower bound
Theorem 3.4. If G is a large 3-con 2-cc graph, then
γ(G) ≥
⌈
2
3
·#L
⌉
.
Before proving the result, we list two useful observations. Let G be a large 3-con 2-cc
graph.
1. Every vertex of G lies on at least one and at most two tiles.
2. All vertices of a picture P can be dominated by a single vertex v only if the picture
is V IA. Moreover, in this case, the vertex v only dominates vertices within picture
P .
Proof of Theorem 3.4. Let G be a 3-con 2-cc graph. We can assume that G only has
L frames, since replacing dL frames with L frames means that we contract some edges,
which can only decrease the domination number. Replacing dL frames with L frames
doesn’t change the number #L.
From Observation 1 we know that every vertex of G lies either on only one tile or on
two consecutive tiles. If it lies on only one tile, we say that it belongs to that tile. If it lies
on two tiles, we say that it belongs to the tile on the right. Hence every vertex belongs to
exactly one tile.
8 Ars Math. Contemp. 23 (2023) #P4.05
Let D be a smallest dominating set of G. First we show that for every trinity of consec-
utive tiles, there exist at least two vertices from the set D that belong to one of the tiles in
the trinity. Figure 8 shows frames of a trinity of tiles (without the pictures). Vertices that
are marked red belong to one of the tiles in the trinity. Vertices that are marked with a green
circle can only be dominated from one of the vertices that belong to the trinity of tiles.
From Observation 2 it follows that we need at least two elements from the set D to
dominate all green vertices. Hence there exist at least two vertices from the set D that
belong to the trinity of tiles.
Figure 8: A trinity of consecutive tiles. Vertices that are marked with a green circle can
only be dominated from one of the vertices that belong to this trinity of tiles.
Now we can prove that |D| ≥ 23#L. There are #L trinities of consecutive tiles in the
graph G, we denote them 1, 2, . . . ,#L. Let
D′ = {(d, k) | d ∈ D, d belongs to one of the tiles in the trinity k}.
Since each vertex belongs to exactly three trinities of consecutive tiles, it follows that
|D′| = 3 · |D|. For every trinity of tiles k, there exist at least two vertices from D that
belong to tiles in the trinity k. Hence there exist at least two elements in D′ with sec-
ond component k for every k = 1, 2, . . . ,#L. Therefore |D′| ≥ 2 · #L, hence it holds
that 3 · |D| ≥ 2 · #L. Because the domination number of G is an integer, it follows that
γ(G) ≥
⌈
2
3 ·#L
⌉
.
The lower bound from Theorem 3.4 is sharp, which can be seen in the following exam-
ple.
Example 3.5. Let G3 = n ·DDLDDLAIV L, where n ≥ 1 is an odd number. Figure 9
shows the dominating set of size 23 · 3 · n, meaning γ(G3) ≤ 2n. Our formula from
Theorem 3.4 shows the same, as
⌈
2
3 ·#L
⌉
=
⌈
2
3 · 3 · n
⌉
= 2n.
Figure 9: Graph G3 with a marked dominating set of size 2n.
Every trinity of consecutive pictures DDLDDLAIV L requires at least two vertices
from the dominating set to dominate all the inner vertices of the trinity, which are marked
orange in Figure 10. This means that at least two vertices are needed to dominate this trinity
of pictures. Therefore γ(G3) ≥ 2n.
From this follows that γ(G3) = 2n.
V. Iršič et al.: Domination and independence numbers of large 2-crossing-critical graphs 9
Figure 10: Trinity of consecutive pictures DDLDDLAIV L, where we want the inner
vertices, marked orange, to be dominated by one vertex. Note that none of these vertices
can be dominated by a vertex outside of this trinity of tiles.
4 Independence number
In this section, we present sharp upper and lower bounds for the independence number of
large 3-con 2-cc graphs.
4.1 Upper bound
Theorem 4.1. If G is a large 3-con 2-cc graph, then
α(G) ≤
⌊
|V(G)|
2
⌋
.
Proof. Since all large 3-con 2-cc graphs are Hamiltonian [22], and the independence num-
ber of Hamiltonian graphs is at most 12 |V(G)|, we obtain the desired upper bound.
The following example shows that the upper bound from Theorem 4.1 is sharp.
Example 4.2. Let G4 = n ·HdL, where n ≥ 3 is an odd number. Then |V(G4)| = 6n.
Figure 11 shows that we can choose 3n independent vertices from the graph G4, meaning
α(G4) ≥ 3n.
Figure 11: Graph G4 with a marked independent set of size 3n.
Every vertex of graph G4 lies in exactly one picture. Since we can choose at most three
independent vertices in each of the n pictures, α(G4) ≤ 3n, which is also the result of
Theorem 4.1. Therefore α(G4) = 3n =
⌊
|V(G4)|
2
⌋
.
4.2 Lower bound
Theorem 4.3. If G is a large 3-con 2-cc graph, then
α(G) ≥ min{#L+#d, 2 ·#L− 1}.
Proof. For every large 3-con 2-cc graph G we can construct the graph G′ from the same
frames used for G, without using the pictures. We notice that if we add pictures into the
frames in G′ to get the original graph G, we only add vertices and do not connect any
10 Ars Math. Contemp. 23 (2023) #P4.05
vertices that were previously not connected, thus any picture we add can only increase the
independence number, therefore α(G) ≥ α(G′). Note that the graph G′ will have the
same number of frames L and dL as the initial graph G. Therefore it suffices to prove the
proposed lower bound for the graph G′.
We distinguish two cases, the first case is if there are only dL frames and the second if
there is at least one L frame.
Case 1 If there are only dL frames, we can find 2 · #L − 1 independent vertices, as is
shown in Figure 12. Note that in this case min{#L+#d, 2 ·#L−1} = 2 ·#L−1.
Figure 12: Graph G′ from Case 1 with a marked independent set of size 2 ·#L− 1.
Case 2 If there is at least one L frame, then we can choose the independent set based on
the following method. Note that double edges can be ignored when studying the
independence number. The graph G′ is then composed of 3- and 4-cycles, which
are connected with additional edges (marked orange in Figure 13). These additional
edges come from where the top and bottom paths of the pictures were in G. To
obtain an independent set of appropriate size, we select one vertex from each 3-
cycle and two vertices from each 4-cycle. For every 3-cycle, we select the vertex of
degree 3 on its left side. If we have two consecutive 3-cycles, the vertices we chose
from them are independent. When selecting vertices in the 4-cycles, we consider all
consecutive 4-cycles between two 3-cycles and select vertices for the independent
set in these 4-cycles from right to left. The 3-cycle on the right of the consecutive
4-cycles determines how we choose the independent set in the right-most 4-cycle,
which in turn uniquely determines how we select two independent vertices in each
of these 4-cycles (in the same manner as in Figure 12). Notice that the 3-cycle on the
left of these 4-cycles gives no restriction on the selected vertices.
Figure 13: An example of the graph G′ from Case 2 with a marked independent set of size
#L+#d. The edges that connect the 3- and 4-cycles are marked orange.
We have thus chosen two vertices in each 4-cycle and one vertex in each 3-cycle.
Since the number of 3-cycles is #L − #d and the number of 4-cycles is #d, we
have found an independent set of size (#L−#d) + 2 ·#d = #L+#d. Note that
in this case min{#L+#d, 2 ·#L− 1} = #L+#d.
V. Iršič et al.: Domination and independence numbers of large 2-crossing-critical graphs 11
The following two examples show that the lower bound from Theorem 4.3 is sharp. The
first example naturally follows from the proof of Theorem 4.3, while the second example
provides a non-trivial family of sharpness examples. Additionally, examples are selected
in such a way that different parts of the minimum are attained.
Example 4.4. Let G5 be a large 3-con 2-cc graph built from tiles DDdL and DDL, so
that not all of the tiles are DDdL.
From Theorem 4.3 we know that α(G5) ≥ #L+#d. Similarly as in the proof, we can
find #d 4-cycles and #L−#d 3-cycles in G5, so that every vertex lies on exactly one of
them. Every 4-cycle is formed by the two vertices on the right of a DDdL tile and the two
vertices on the left of the next tile to the right. Every 3-cycle is formed by the two vertices
on the right of a DDL tile and the two vertices on the left of the next tile. Two of those
vertices are identified, thus giving us a 3-cycle. The 3-cycles and 4-cycles are marked in
Figure 14.
Figure 14: Graph G5 with marked 3-cycles and 4-cycles.
We can choose at most one independent vertex from every 3-cycle and at most two
independent vertices from every 4-cycle, therefore α(G5) ≤ 2 · #d + 1 · (#L − #d) =
#L+#d.
From this it follows that α(G5) = #L+#d.
Example 4.5. Let G6 be a large 3-con 2-cc graph that is built from DDdL, V IAdL, and
AIV dL tiles, but not all tiles are V IAdL, and not all tiles are AIV dL.
From Theorem 4.3 we know that α(G6) ≥ 2 · #L − 1. We can find at most two
independent vertices in each of the tiles DDdL, V IAdL, and AIV dL, therefore we can
find at most 2 ·#L independent vertices in G6.
For contradiction suppose that α(G6) ̸= 2 · #L − 1, meaning α(G6) = 2 · #L. We
try to construct an independent set A with 2 ·#L vertices. Set A must include exactly two
vertices from every tile because otherwise set A would have to include at least 3 vertices
from one tile, which is impossible.
There are two different ways in which we can choose two independent vertices from a
DDdL tile, and three different ways for tiles V IAdL and AIV dL. All options are shown
in Figure 15.
Even though tiles V IAdL and AIV dL have a third option for the choice of two inde-
pendent vertices (where the selected vertices are not diagonal), we can’t choose the vertices
in set A in this way, since we know that we have to choose two independent vertices from
every tile. If we choose the top and bottom right vertex in a V IAdL tile, then the only way
to choose two vertices in the next tile is if that tile is also a V IAdL tile and we choose
the top and bottom right vertices. We continue this for all tiles, but since not all tiles are
V IAdL, at some point we are not able to choose two independent vertices in the next tile.
For the same reason, we also cannot choose the two vertices on the left of an AIV dL tile.
12 Ars Math. Contemp. 23 (2023) #P4.05
Figure 15: Tiles DDdL, V IAdL, and AIV dL with two independent vertices marked.
This means that for all tiles, the two vertices that are included in set A are the diagonal
ones, without loss of generality we can assume that those diagonal vertices in the first tile
are the bottom left and the top-right vertex. This choice determines which vertices we must
choose in the tile to the right and so on, as is shown in Figure 16.
Figure 16: Graph G′6 was constructed from the same frames used for G6, without using the
pictures. The first tile of graph G′6 determines which two vertices are included in set A for
all other tiles. When we get to the last tile, we get a contradiction (marked orange).
When we get to the last tile we get a contradiction. Because of the tile to the left, the
only possible vertices from the last tile that can be included in A are the bottom left and
the top-right vertex. But the top-right vertex is connected to a vertex in the first tile that is
already included in set A, therefore set A cannot include two vertices from the last tile.
This means that the independent set A that has 2 · #L elements cannot exist and
α(G6) = 2 ·#L− 1.
ORCID iDs
Vesna Iršič https://orcid.org/0000-0001-5302-5250
References
[1] L. Beaudou, C. Hernández-Vélez and G. Salazar, Making a graph crossing-critical by multiply-
ing its edges, Electron. J. Comb. 20 (2013), research paper p61, 14, www.combinatorics.
org/ojs/index.php/eljc/article/view/v20i1p61.
[2] G. S. Bloom, J. W. Kennedy and L. V. Quintas, On crossing numbers and linguistic structures,
Graph theory in: Lecture Notes in Math., vol. 1018 (1983).
V. Iršič et al.: Domination and independence numbers of large 2-crossing-critical graphs 13
[3] D. Bokal, M. Bračič, M. Derňár and P. Hliněný, On degree properties of crossing-critical fam-
ilies of graphs, Electron. J. Comb. 26 (2019), research paper p1.53, 28, doi:10.37236/7753,
https://doi.org/10.37236/7753.
[4] D. Bokal, M. Chimani, A. Nover, J. Schierbaum, T. Stolzmann, M. H. Wagner and T. Wiedera,
Properties of large 2-crossing-critical graphs, J. Graph Algorithms Appl. 26 (2022), 111–147,
doi:10.7155/jgaa.00585, https://doi.org/10.7155/jgaa.00585.
[5] D. Bokal, Z. Dvořák, P. Hliněný, J. Leaños, B. Mohar and T. Wiedera, Bounded degree con-
jecture holds precisely for c-crossing-critical graphs with c ≤ 12, in: 35th International
Symposium on Computational Geometry, SoCG 2019, Portland, Oregon, USA, June 18–21,
2019. Proceedings, Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, p. 15, 2019,
doi:10.4230/LIPIcs.SoCG.2019.14, id/No 14, https://doi.org/10.4230/LIPIcs.
SoCG.2019.14.
[6] D. Bokal, B. Oporowski, R. B. Richter and G. Salazar, Characterizing 2-crossing-critical
graphs, Adv. Appl. Math. 74 (2016), 23–208, doi:10.1016/j.aam.2015.10.003, https://
doi.org/10.1016/j.aam.2015.10.003.
[7] M. Chimani, P. Kindermann, F. Montecchiani and P. Valtr, Crossing numbers of beyond-planar
graphs, Theor. Comput. Sci. 898 (2022), 44–49, doi:10.1016/j.tcs.2021.10.016, https://
doi.org/10.1016/j.tcs.2021.10.016.
[8] K. Clancy, M. Haythorpe and A. Newcombe, A survey of graphs with known or bounded
crossing numbers, Australas. J. Comb. 78 (2020), 209–296, https://ajc.maths.uq.
edu.au/pdf/78/ajc_v78_p209.pdf.
[9] G. Ding, B. Oporowski, R. Thomas and D. Vertigan, Large non-planar graphs and an ap-
plication to crossing-critical graphs, J. Comb. Theory, Ser. B 101 (2011), 111–121, doi:
10.1016/j.jctb.2010.12.001, https://doi.org/10.1016/j.jctb.2010.12.001.
[10] P. Hliněny, Crossing-number critical graphs have bounded path-width, J. Comb. Theory,
Ser. B 88 (2003), 347–367, doi:10.1016/S0095-8956(03)00037-6, https://doi.org/10.
1016/S0095-8956(03)00037-6.
[11] P. Hliněný and M. Korbela, On the achievable average degrees in 2-crossing-critical graphs,
Acta Math. Univ. Comen. 88 (2019), 787–793, http://www.iam.fmph.uniba.sk/
amuc/ojs/index.php/amuc/article/view/1178.
[12] M. Kochol, Construction of crossing-critical graphs, Discrete Math. 66 (1987), 311–313,
doi:10.1016/0012-365X(87)90108-7, https://doi.org/10.1016/0012-365X(87)
90108-7.
[13] J. Leaños and G. Salazar, On the additivity of crossing numbers of graphs, J. Knot Theory Ram-
ifications 17 (2008), 1043–1050, doi:10.1142/S0218216508006531, https://doi.org/
10.1142/S0218216508006531.
[14] B. Pinontoan and R. B. Richter, Crossing numbers of sequences of graphs. II: Planar tiles,
J. Graph Theory 42 (2003), 332–341, doi:10.1002/jgt.10097, https://doi.org/10.
1002/jgt.10097.
[15] B. Pinontoan and R. B. Richter, Crossing numbers of sequences of graphs. I: General tiles,
Australas. J. Comb. 30 (2004), 197–206, https://ajc.maths.uq.edu.au/pdf/30/
ajc_v30_p197.pdf.
[16] B. Richter, Cubic graphs with crossing number two, J. Graph Theory 12 (1988), 363–374,
doi:10.1002/jgt.3190120308, https://doi.org/10.1002/jgt.3190120308.
[17] F. Shahrokhi, L. A. Székely and I. Vrt’o, Crossing numbers of graphs, lower bound techniques
and algorithms: A survey, in: R. Tamassia and I. G. Tollis (eds.), Graph Drawing, Springer
14 Ars Math. Contemp. 23 (2023) #P4.05
Berlin Heidelberg, Berlin, Heidelberg, 1995 pp. 131–142, doi:10.1007/3-540-58950-3_364,
https://doi.org/10.1007/3-540-58950-3_364.
[18] A. C. Silva, A. Arroyo, R. B. Richter and O. Lee, Graphs with at most one crossing, Discrete
Math. 342 (2019), 3201–3207, doi:10.1016/j.disc.2019.06.031, https://doi.org/10.
1016/j.disc.2019.06.031.
[19] J. Širáň, Infinite families of crossing-critical graphs with a given crossing number, Discrete
Math. 48 (1984), 129–132, doi:10.1016/0012-365X(84)90140-7, https://doi.org/10.
1016/0012-365X(84)90140-7.
[20] L. A. Székely, An optimality criterion for the crossing number, Ars Math. Contemp. 1 (2008),
32–37, doi:10.26493/1855-3974.43.506, https://doi.org/10.26493/1855-3974.
43.506.
[21] A. Vegi Kalamar, T. Žerak and D. Bokal, Counting hamiltonian cycles in 2-tiled
graphs, Mathematics 9 (2021), doi:10.3390/math9060693, https://doi.org/10.3390/
math9060693.
[22] T. Žerak, Hamiltonian Cycles in Large 2-crossing-critical Graphs, Master’s thesis, University
of Maribor, 2019.