Source author record

Drago Bokal

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

3works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

Counting Hamiltonian cycles in 2-tiled graphs

In 1930, Kuratowski showed that $K_{3,3}$ and $K_5$ are the only two minor-minimal non-planar graphs. Robertson and Seymour extended finiteness of the set of forbidden minors for any surface. Širáň and Kochol showed that there are infinitely many $k$ -crossing-critical graphs for any $k\ge 2$ , even if restricted to simple $3$ -connected graphs. Recently, $2$ -crossing-critical graphs have been completely characterized by Bokal, Oporowski, Richter, and Salazar. We present a simplified description of large 2-crossing-critical graphs and use this simplification to count Hamiltonian cycles in such graphs. We generalize this approach to an algorithm counting Hamiltonian cycles in all 2-tiled graphs, thus extending the results of Bodroža-Pantić, Kwong, Doroslovački, and Pantić for $n = 2$ .

preprint2013arXiv

Characterizing 2-crossing-critical graphs

It is very well-known that there are precisely two minimal non-planar graphs: $K_5$ and $K_{3,3}$ (degree 2 vertices being irrelevant in this context). In the language of crossing numbers, these are the only 1-crossing-critical graphs: they each have crossing number at least one, and every proper subgraph has crossing number less than one. In 1987, Kochol exhibited an infinite family of 3-connected, simple 2-crossing-critical graphs. In this work, we: (i) determine all the 3-connected 2-crossing-critical graphs that contain a subdivision of the Möbius Ladder $V_{10}$ ; (ii) show how to obtain all the not 3-connected 2-crossing-critical graphs from the 3-connected ones; (iii) show that there are only finitely many 3-connected 2-crossing-critical graphs not containing a subdivision of $V_{10}$ ; and (iv) determine all the 3-connected 2-crossing-critical graphs that do not contain a subdivision of $V_{8}$ .

preprint2011arXiv

Minor crossing number is additive over arbitrary cuts

We prove that if $G$ is a graph with an minimal edge cut $F$ of size three and $G_1$ , $G_2$ are the two (augmented) components of $G-F$ , then the crossing number of $G$ is equal to the sum of crossing numbers of $G_1$ and $G_2$ . Combining with known results, this implies that crossing number is additive over edge-cuts of size $d$ for $d\in\{0, 1, 2, 3\}$ , whereas there are counterexamples for every $d\ge 4$ . The techniques generalize to show that minor crossing number is additive over edge cuts of arbitrary size, as well as to provide bounds for crossing number additivity in arbitrary surfaces. We point out several applications to exact crossing number computation and crossing critical graphs, as well as provide a very general lower bound for the minor crossing number of the Cartesian product of an arbitrary graph with a tree.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.