Families of $\{K_{2s},T_{ts,t}\}_{K_2}$-homogeneous graphs
Italo Jose Dejter · arXiv (Cornell University) · 2007
Let $\mathcal C$ be a class of graphs. A definition of $\mathcal C$-{\it homogeneous graph} $G$ is conceived that fills the need for a fitting generalization of $\mathcal C$-ul\-tra\-ho\-mo\-ge\-neous graph (Isaksen et al.) by considering each induced subgraph of $G$ in $\mathcal C$ tethered by means of an arc. Letting $2<r\in\Z$, $\sigma\in(0,r-1)\cap\Z$, $t=2^{\sigma+1}-1$, $s=2^{r-\sigma-1}$ and ${\mathcal C}=\{K_{2s},T_{ts,t}\}$, we say that a $\mathcal C$-homogeneous graph $G$ that has each edge shared by just one copy of the complete subgraph $K_{2s}$ and one of the Tur\'an graph $T_{ts,t}$ is a ${\mathcal C}_{K_2}$-{\it homogeneous graph}. Infinitely many connected ${\mathcal C}_{K_2}$-homogeneous graphs $G$ which are not line graphs of any other graph are constructed in terms of configurations of points and lines, one per pair $(r,\sigma)$. Moreover, if $r-\sigma=2$, then $G$ is $K_4$-ultrahomogeneous with order $(2^r-1)(2^r-2)$ and number $2^{\sigma+1}$ of edge-disjoint copies of $K_4$ incident to each vertex.