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 infinite tumbling block graph is a bipartite graph, where each vertex in one partite set is of degree 3 and each vertex in the other partite set is of degree 6. It is a 2-dimensional array of blocks of seven vertices and nine edges, a planar graph that has 3-D looks. This paper introduces tumbling block graphs and considers various graphical parameters for different classes of infinite and finite tumbling blocks.
We introduce the notion of a centroidal locating set of a graph G, that is, a set L of vertices such that all vertices in G are uniquely determined by their relative distances to the vertices of L. A centroidal locating set of G of minimum size is called a centroidal basis, and its size is the centroidal dimension CD(G). This notion, which is related to previous concepts, gives a new way of identifying the vertices of a graph. The centroidal dimension of a graph G is lower- and upper-bounded by the metric dimension and twice the location-domination number of G, respectively. The latter two parameters are standard and well-studied notions in the field of graph identification. We show that for any graph G with n vertices and maximum degree at least~2, (1+o(1))lnlnnlnn≤CD(G)≤n−1. We discuss the tightness of these bounds and in particular, we characterize the set of graphs reaching the upper bound. We then show that for graphs in which every pair of vertices is connected via a bounded number of paths, CD(G)=Ω(∣E(G)∣), the bound being tight for paths and cycles. We finally investigate the computational complexity of determining CD(G) for an input graph G, showing that the problem is hard and cannot even be approximated efficiently up to a factor of o(logn). We also give an O(nlnn)-approximation algorithm.
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.