MATHEMATICA BOHEMICA, Vol. 130, No. 1, pp. 35-48, 2005

# Homogeneously embedding stratified graphs in stratified graphs

## Gary Chartrand, Donald W. VanderJagt, Ping Zhang

Gary Chartrand, Department of Mathematics, Western Michigan University, Kalamazoo, Michigan 49008, USA; Donald W. VanderJagt, Department of Mathematics, Grand Valley State University, Allendale, Michigan 49401, USA; Ping Zhang, Department of Mathematics, Western Michigan University, Kalamazoo, Michigan 49008, USA, e-mail: ping.zhang@wmich.edu

Abstract: A 2-stratified graph $G$ is a graph whose vertex set has been partitioned into two subsets, called the strata or color classes of $G$. Two $2$-stratified graphs $G$ and $H$ are isomorphic if there exists a color-preserving isomorphism $\phi$ from $G$ to $H$. A $2$-stratified graph $G$ is said to be homogeneously embedded in a $2$-stratified graph $H$ if for every vertex $x$ of $G$ and every vertex $y$ of $H$, where $x$ and $y$ are colored the same, there exists an induced $2$-stratified subgraph $H'$ of $H$ containing $y$ and a color-preserving isomorphism $\phi$ from $G$ to $H'$ such that $\phi(x) = y$. A $2$-stratified graph $F$ of minimum order in which $G$ can be homogeneously embedded is called a frame of $G$ and the order of $F$ is called the framing number $\fr(G)$ of $G$. It is shown that every $2$-stratified graph can be homogeneously embedded in some $2$-stratified graph. For a graph $G$, a $2$-stratified graph $F$ of minimum order in which every $2$-stratification of $G$ can be homogeneously embedded is called a fence of $G$ and the order of $F$ is called the fencing number $\fe(G)$ of $G$. The fencing numbers of some well-known classes of graphs are determined. It is shown that if $G$ is a vertex-transitive graph of order $n$ that is not a complete graph then $\fe(G) = 2n.$

Keywords: stratified graph, homogeneous embedding

Classification (MSC 2000): 05C10, 05C15

Full text available as PDF (smallest), as compressed PostScript (.ps.gz) or as raw PostScript (.ps).