BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
The game of cops and robbers is a well-known game played on graphs. In this paper we consider the straight-ahead orientations of 4-regular quadrangulations of the torus and the Klein bottle and we prove that their cop number is bounded by a constant. We also show that the cop number of every k-regularly oriented toroidal grid is at most 13.
Weighted Szeged index is a recently introduced extension of the well-known Szeged index. In this paper, we present a new tool to analyze and characterize minimum weighted Szeged index trees. We exhibit the best trees with up to 81 vertices and use this information, together with our results, to propose various conjectures on the structure of minimum weighted Szeged index trees.
We establish a lower bound for the cop number of graphs of high girth in terms of the minimum degree, and more generally, in terms of a certain growth condition. We show, in particular, that the cop number of any graph with girth g and minimum degree δ is at least g1(δ−1)⌊4g−1⌋. We establish similar results for directed graphs. While exposing several reasons for conjecturing that the exponent 41g in this lower bound cannot be improved to (41+ε)g, we are also able to prove that it cannot be increased beyond 83g. This is established by considering a certain family of Ramanujan graphs. In our proof of this bound, we also show that the "weak" Meyniel's conjecture holds for expander graph families of bounded degree.
In 1999, De Simone and Körner conjectured that every graph without induced C5,C7,C7 contains a clique cover C and a stable set cover I such that every clique in C and every stable set in I have a vertex in common. This conjecture has roots in information theory and became known as the Normal Graph Conjecture. Here we prove that all graphs of bounded maximum degree and sufficiently large odd girth (linear in the maximum degree) are normal. This implies that for every fixed d, random d-regular graphs are a.a.s. normal.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.