### Top 10 Arxiv Papers Today in Discrete Mathematics

##### #1. Generalized Cops and Robbers: A Multi-Player Pursuit Game on Graphs
###### Athanasios Kehagias
We introduce and study the Generalized Cops and Robbers game (GCR), an N-player pursuit game in graphs. The two-player version is essentially equivalent to the classic Cops and Robbers (CR) game. The three-player version can be understood as two CR games played simultaneously on the same graph; a player can be at the same time both pursuer and evader. The same is true for four or more players. We formulate GCR as a discounted stochastic game of perfect information and prove that, for three or more players, it has at least two Nash Equilibria: one in positional deterministic strategies and another in non-positional ones. We also study the capturing properties of GCR Nash Equilibria in connection to the cop-number of a graph. Finally, we briefly discuss GCR as a member of a wider family of multi-player graph pursuit games with rather interesting properties.
more | pdf | html
None.
###### Tweets
360unfiltered: RT @DO: Generalized Cops and Robbers: A Multi-Player Pursuit Game on Graphs. https://t.co/Xb1AhcYSUd
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 1
Total Words: 13144
Unqiue Words: 2012

##### #2. Shared Processor Scheduling of Multiprocessor Jobs
###### Dariusz Dereniowski, Wieslaw Kubiak
We study shared processor scheduling of $\textit{multiprocessor}$ weighted jobs where each job can be executed on its private processor and simultaneously on possibly $\textit{many}$ processors shared by all jobs in order to reduce their completion times due to processing time overlap. Each of $m$ shared processors may charge different fee but otherwise the processors are identical. The total weighted overlap of all jobs is to be maximized. This problem is key to subcontractor scheduling in extended enterprises and supply chains, and divisible load scheduling in computing. We prove that, quite surprisingly, $\textit{synchronized}$ schedules that complete each job using shared processors at the same time on its private and shared processors include optimal schedules. We show that optimal $\alpha$-$\textit{private}$ schedules that require each job to use its private processor for at least $\alpha=1/2+1/(4(m+1))$ of the time required by the job guarantee more than an $\alpha$ fraction of the total weighted overlap of the optimal...
more | pdf | html
None.
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 15457
Unqiue Words: 2165

##### #3. On a reduction of the weighted induced bipartite subgraph problem to the weighted independent set problem
###### Yotaro Takazawa, Shinji Mizuno
We study the weighted induced bipartite subgraph problem (WIBSP). The goal of WIBSP is, given a graph and nonnegative weights for the nodes, to find a set W of nodes with the maximum total weight such that a subgraph induced by W is bipartite. WIBSP is also referred as to the graph bipartization problem or the odd cycle transversal problem. In this paper, we show that WIBSP can be reduced to the weighted independent set problem (WISP) where the number of nodes becomes twice and the maximum degree increase by 1. WISP is a well-studied combinatorial optimization problem. Thus, by using the reduction and results about WISP, we can obtain nontrivial approximation and exact algorithms for WIBSP.
more | pdf | html
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 1665
Unqiue Words: 571

##### #4. Counting short cycles of (c,d)-regular bipartite graphs
Recently, working on the Tanner graph which represents a low density parity check (LDPC) code becomes an interesting research subject. Finding the number of short cycles of Tanner graphs motivated Blake and Lin to investigate the multiplicity of cycles of length girth in bi-regular bipartite graphs, by using the spectrum and degree distribution of the graph. Although there were many algorithms to find the number of cycles, they preferred to investigate in a computational way. Dehghan and Banihashemi counted the number of cycles of length $g+2$ and $g+4,$ where $G$ is a bi-regular bipartite graph and $g$ is the length of the girth $G.$ But they just proposed a descriptive technique to compute the multiplicity of cycles of length less than $2g$ for bi-regular bipartite graphs. In this paper, we find the number of cycles of length less than $2g$ by using spectrum and degree distribution of a bi-regular bipartite graph such that the formula depends only on the partitions of positive integers and the number of closed cycle-free walks...
more | pdf | html
None.
###### Tweets
MathPaper: Counting short cycles of (c,d)-regular bipartite graphs. https://t.co/tcxhs48tiM
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 6414
Unqiue Words: 1226

##### #5. The 2-domination and Roman domination numbers of grid graphs
###### Michaël Rao, Alexandre Talon
We investigate the 2-domination number for grid graphs, that is the size of a smallest set $D$ of vertices of the grid such that each vertex of the grid belongs to $D$ or has at least two neighbours in $D$. We give a closed formula giving the 2-domination number of any $n \!\times\! m$ grid, hereby confirming the known results (for $n \leq 5$). The proof relies on some dynamic programming algorithms, using transfer matrices in (min,+)-algebra We also apply the method to solve the Roman domination problem on grid graphs.
more | pdf | html
None.
###### Tweets
MathPaper: The 2-domination and Roman domination numbers of grid graphs. https://t.co/sbzNzVyAdC
MUKULBHALLA7: https://t.co/ZwE26TBF9V
None.
None.
###### Other stats
Sample Sizes : [2, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 2, 5]
Authors: 2
Total Words: 5893
Unqiue Words: 1303

##### #6. The Simplex Geometry of Graphs
###### Karel Devriendt, Piet Van Mieghem
Graphs are a central object of study in various scientific fields, such as discrete mathematics, theoretical computer science and network science. These graphs are typically studied using combinatorial, algebraic or probabilistic methods, each of which highlights the properties of graphs in a unique way. Here, we discuss a novel approach to study graphs: the simplex geometry (a simplex is a generalized triangle). This perspective, proposed by Miroslav Fiedler, introduces techniques from (simplex) geometry into the field of graph theory and conversely, via an exact correspondence. We introduce this graph-simplex correspondence, identify a number of basic connections between graph characteristics and simplex properties, and suggest some applications as example.
more | pdf | html
None.
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 9330
Unqiue Words: 1928

##### #7. Crossing Numbers and Stress of Random Graphs
###### Markus Chimani, Hanna Döring, Matthias Reitzner
Consider a random geometric graph over a random point process in $\mathbb{R}^d$. Two points are connected by an edge if and only if their distance is bounded by a prescribed distance parameter. We show that projecting the graph onto a two dimensional plane is expected to yield a constant-factor crossing number (and rectilinear crossing number) approximation. We also show that the crossing number is positively correlated to the stress of the graph's projection.
more | pdf | html
None.
###### Tweets
MathPaper: Crossing Numbers and Stress of Random Graphs. https://t.co/JjxoHHQsv3
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 8485
Unqiue Words: 1851

##### #8. Level Planarity: Transitivity vs. Even Crossings
###### Guido Brückner, Ignaz Rutter, Peter Stumpf
Recently, Fulek et al. have presented Hanani-Tutte results for (radial) level planarity, i.e., a graph is (radial) level planar if it admits a (radial) level drawing where any two (independent) edges cross an even number of times. We show that the 2-Sat formulation of level planarity testing due to Randerath et al. is equivalent to the strong Hanani-Tutte theorem for level planarity. Further, we show that this relationship carries over to radial level planarity, which yields a novel polynomial-time algorithm for testing radial level planarity.
more | pdf | html
None.
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 12791
Unqiue Words: 1787

##### #9. Topological Data Analysis Made Easy with the Topology ToolKit
###### Guillaume Favelier, Charles Gueunet, Attila Gyulassy, Julien Kitware, Joshua Levine, Jonas Lukasczyk, Daisuke Sakurai, Maxime Soler, Julien Tierny, Will Usher, Qi Wu
This tutorial presents topological methods for the analysis and visualization of scientific data from a user's perspective, with the Topology ToolKit (TTK), a recently released open-source library for topological data analysis. Topological methods have gained considerably in popularity and maturity over the last twenty years and success stories of established methods have been documented in a wide range of applications (combustion, chemistry, astrophysics, material sciences, etc.) with both acquired and simulated data, in both post-hoc and in-situ contexts. While reference textbooks have been published on the topic, no tutorial at IEEE VIS has covered this area in recent years, and never at a software level and from a user's point-of-view. This tutorial fills this gap by providing a beginner's introduction to topological methods for practitioners, researchers, students, and lecturers. In particular, instead of focusing on theoretical aspects and algorithmic details, this tutorial focuses on how topological methods can be useful in...
more | pdf | html
###### Tweets
ballforest: RT @arxiv_csgr: Topological Data Analysis Made Easy with the Topology ToolKit https://t.co/O5NtqBGijK
DA1KE: RT @arxiv_cscv: Topological Data Analysis Made Easy with the Topology ToolKit https://t.co/TAWIKUcaak
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 11
Total Words: 3707
Unqiue Words: 1494

##### #10. Optimal Grid Drawings of Complete Multipartite Graphs and an Integer Variant of the Algebraic Connectivity
###### Ruy Fabila-Monroy, Carlos Hidalgo-Toscano, Clemens Huemer, Dolores Lara, Dieter Mitsche
How to draw the vertices of a complete multipartite graph $G$ on different points of a bounded $d$-dimensional integer grid, such that the sum of squared distances between vertices of $G$ is (i) minimized or (ii) maximized? For both problems we provide a characterization of the solutions. For the particular case $d=1$, our solution for (i) also settles the minimum-2-sum problem for complete bipartite graphs; the minimum-2-sum problem was defined by Juvan and Mohar in 1992. Weighted centroidal Voronoi tessellations are the solution for (ii). Such drawings are related with Laplacian eigenvalues of graphs. This motivates us to study which properties of the algebraic connectivity of graphs carry over to the restricted setting of drawings of graphs with integer coordinates.
more | pdf | html
###### Tweets
MathPaper: Optimal Grid Drawings of Complete Multipartite Graphs and an Integer Variant of the Algebraic Connectivity. https://t.co/pipNKLewnZ
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 5
Total Words: 5758
Unqiue Words: 1374

Assert is a website where the best academic papers on arXiv (computer science, math, physics), bioRxiv (biology), BITSS (reproducibility), EarthArXiv (earth science), engrXiv (engineering), LawArXiv (law), PsyArXiv (psychology), SocArXiv (social science), and SportRxiv (sport research) bubble to the top each day.

Papers are scored (in real-time) based on how verifiable they are (as determined by their Github repos) and how interesting they are (based on Twitter).

To see top papers, follow us on twitter @assertpub_ (arXiv), @assert_pub (bioRxiv), and @assertpub_dev (everything else).

To see beautiful figures extracted from papers, follow us on Instagram.

Tracking 72,893 papers.

###### Search
Sort results based on if they are interesting or reproducible.
Interesting
Reproducible
Online
###### Stats
Tracking 72,893 papers.