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
In 1995, Brass, Harborth and Nienborg disproved a conjecture of Erdős when they showed that a C4-free subgraph of the hypercube, Qn, can have at least (21+ω(1))e(Qn) edges. In this paper, we generalize the idea of Brass, Harborth and Nienborg to provide good constructions of Q3-free subgraphs of Qn for some small values of n.
In this paper, we address a particular variation of the Turán problem for the hypercube. Alon, Krech and Szabó (2007) asked "In an n-dimensional hypercube, Qn, and for l < d < n, what is the size of a smallest set, S, of Q_l's so that every Q_d contains at least one member of S?" Likewise, they asked a similar Ramsey type question: "What is the largest number of colors that we can use to color the copies of Q_l in Q_n such that each Q_d contains a Q_l of each color?" We give upper and lower bounds for each of these questions and provide constructions of the set S above for some specific cases.
An r-identifying code on a graph G is a set C⊂V(G) such that for every vertex in V(G), the intersection of the radius-r closed neighborhood with C is nonempty and different. Here, we provide an overview on codes for the n-dimensional lattice, discussing the case of 1-identifying codes, constructing a sparse code for the 4-dimensional lattice as well as showing that for fixed n, the minimum density of an r-identifying code is Θ(1/rn−1).
For any positive integer r, an r-identifying code on a graph G is a set C⊂V(G) such that for every vertex in V(G), the intersection of the radius-r closed neighborhood with C is nonempty and pairwise distinct. For a finite graph, the density of a code is ∣C∣/∣V(G)∣, which naturally extends to a definition of density in certain infinite graphs which are locally finite. We find a code of density less than 5/(6r), which is sparser than the prior best construction which has density approximately 8/(9r).
An r-identifying code on a graph G is a set C⊂V(G) such that for every vertex in V(G), the intersection of the radius-r closed neighborhood with C is nonempty and unique. On a finite graph, the density of a code is ∣C∣/∣V(G)∣, which naturally extends to a definition of density in certain infinite graphs which are locally finite. We present new lower bounds for densities of codes for some small values of r in both the square and hexagonal grids.
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.