On Dimensional Parameters Of Graphs And Posets

TL;DRAbstract

In this thesis we study the following dimensional parameters : boxicity, cubicity, threshold dimension and poset dimension. While the first three parameters are defined on graphs, poset dimension is defined on partially ordered sets (or posets). We only consider finite graphs and posets. In addition, we assume that the graphs are simple and undirected. Boxicity and Cubicity: A k-box (k-cube) is a Cartesian product of closed intervals(unit-intervals) [a1,b1]x…x [ak,bk]. The boxicity (cubicity) of a graph G,box (G) (cub(G)) is the minimum integer k such that every vertex in G is mapped to a k-box(k-cube) in the k-dimensional Euclidean space and two boxes(cubes) intersect if and only if their corresponding vertices are adjacent in G. Boxicity and cubicity can be considered as extensions of the concept of interval graphs and unit-interval graphs respectively. Threshold Dimension: A graph G is a threshold graph if there is a real number p and a weight function w: V→ R such that for any two

Chat with Paper

AI Agents for this Paper