19 citations · 20 across the 5 of their papers we have counts for
4 papers · 1 filter
Approximation algorithms and ratios for multiple domination in graphs
Lukas Dijkstra, Vadim Zverovich, Andrei Gagarin
We analyse approximation algorithms (greedy heuristics) for the classical domination number and two multiple domination numbers in simple graphs. First, we present a short self-con…
Embedding K3,3 and K5 on the Double Torus
William L. Kocay, Andrei Gagarin
The Kuratowski graphs and characterize planarity. Counting distinct 2-cell embeddings of these two graphs on orientable surfaces was previously done by using Burnsi…
Counting unlabelled toroidal graphs with no K33-subdivisions
Andrei Gagarin, Gilbert Labelle, Pierre Leroux
We provide a description of unlabelled enumeration techniques, with complete proofs, for graphs that can be canonically obtained by substituting 2-pole networks for the edges of co…
Characterization and enumeration of toroidal K_{3,3}-subdivision-free graphs
Andrei Gagarin, Gilbert Labelle, Pierre Leroux
We describe the structure of 2-connected non-planar toroidal graphs with no K_{3,3}-subdivisions, using an appropriate substitution of planar networks into the edges of certain gra…