Representing Asteroidal Sets on Subdivisions of Stars

Abstract

Consider a simple undirected graph $G=(V,E)$. A family of subtrees, $\{T_v{\}}_{v\in V}$, of a tree $\mathcal{T}$ is called a $(\mathcal{T};t)$-representation of $G$ provided $uv\in E$ if and only if $|T_u\cap T_v|\ge t$. In this paper, we consider $(\mathcal{T};t)$-representations for graphs containing large asteroidal sets, where $\mathcal{T}$ is a subdivision of the $n$-star $K_{1,n}$. An asteroidal set in a graph $G$ is a subset $A$ of the vertex set such that for all 3-element subsets of $A$, there exists a path in $G$ between any two of these vertices which avoids the neighborhood of the third vertex. We construct a representation of an asteroidal set of size $n+\sum _{k=2}^n(\genfrac{}{}{0ex}{}{n}{k})(\genfrac{}{}{0ex}{}{t-2}{k-1})$ and show that no graph containing a larger asteroidal set can be represented.