Source author record

Joshua D. Laison

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.GR

Catalog footprint

Research overview

4works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Area, Perimeter, Height, and Width of Rectangle Visibility Graphs

A rectangle visibility graph (RVG) is represented by assigning to each vertex a rectangle in the plane with horizontal and vertical sides in such a way that edges in the graph correspond to unobstructed horizontal and vertical lines of sight between their corresponding rectangles. To discretize, we consider only rectangles whose corners have integer coordinates. For any given RVG, we seek a representation with smallest bounding box as measured by its area, perimeter, width, or height (height is assumed not to exceed width). We derive a number of results regarding these parameters. Using these results, we show that these four measures are distinct, in the sense that there exist graphs $G_1$ and $G_2$ with $area(G_1)<area(G_2)$ but $perimeter(G_2)<perimeter(G_1)$ , and analogously for all other pairs of these parameters. We further show that there exists a graph $G_3$ with representations $S_1$ and $S_2$ such that $area(G_3)=area(S_1)<area(S_2)$ but $perimeter(G_3)=perimeter(S_2)<perimeter(S_1)$ . In other words, $G_3$ requires distinct representations to minimize area and perimeter. Similarly, such graphs exist to demonstrate the independence of all other pairs of these parameters. Among graphs with $n \leq 6$ vertices, the empty graph $E_n$ requires largest area. But for graphs with $n=7$ and $n=8$ vertices, we show that the complete graphs $K_7$ and $K_8$ require larger area than $E_7$ and $E_8$ , respectively. Using this, we show that for all $n \geq 8$ , the empty graph $E_n$ does not have largest height, width, area, or perimeter among all RVGs on $n$ vertices.

preprint2016arXiv

Prime Power and Prime Product Distance Graphs

A graph $G$ is a $k$ -prime product distance graph if its vertices can be labeled with distinct integers such that for any two adjacent vertices, the difference of their labels is the product of at most $k$ primes. A graph has prime product number $ppn(G)=k$ if it is a $k$ -prime product graph but not a $(k-1)$ -prime product graph. Similarly, $G$ is a prime $k$ th-power graph (respectively, strict prime $k$ th-power graph) if its vertices can be labeled with distinct integers such that for any two adjacent vertices, the difference of their labels is the $j$ th power of a prime, for $j \leq k$ (respectively, the $k$ th power of a prime exactly). We prove that $ppn(K_n) = \lceil \log_2(n)\rceil - 1$ , and for a nonempty $k$ -chromatic graph $G$ , $ppn(G) = \lceil \log_2(k)\rceil - 1$ or $ppn(G) = \lceil \log_2(k)\rceil$ . We determine $ppn(G)$ for all complete bipartite, 3-partite, and 4-partite graphs. We prove that $K_n$ is a prime $k$ th-power graph if and only if $n < 7$ , and we determine conditions on cycles and outerplanar graphs $G$ for which $G$ is a strict prime $k$ th-power graph. We find connections between prime product and prime power distance graphs and the Twin Prime Conjecture, the Green-Tao Theorem, and Fermat's Last Theorem.

preprint2014arXiv

Base Size Sets and Determining Sets

Bridging the work of Cameron, Harary, and others, we examine the base size set B(G) and determining set D(G) of several families of groups. The base size set is the set of base sizes of all faithful actions of the group G on finite sets. The determining set is the subset of B(G) obtained by restricting the actions of G to automorphism groups of finite graphs. We show that for finite abelian groups, B(G)=D(G)={1,2,...,k} where k is the number of elementary divisors of G. We then characterize B(G) and D(G) for dihedral groups of the form D_{p^k} and D_{2p^k}. Finally, we prove B(G) is not equal to D(G) for dihedral groups of the form D_{pq} where p and q are distinct odd primes.

preprint2011arXiv

Weighted pebbling numbers on graphs

We expand the theory of pebbling to graphs with weighted edges. In a weighted pebbling game, one player distributes a set amount of weight on the edges of a graph and his opponent chooses a target vertex and places a configuration of pebbles on the vertices. Player one wins if, through a series of pebbling moves, he can move at least one pebble to the target. A pebbling move of p pebbles across an edge with weight w leaves the floor of pw pebbles on the next vertex. We find the weighted pebbling numbers of stars, graphs with at least 2|V|-1 edges, and trees with given targets. We give an explicit formula for the minimum total weight required on the edges of a length-2 path, solvable with p pebbles and exhibit a graph which requires an edge with weight 1/3 in order to achieve its weighted pebbling number.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.