Homogeneously embedding stratified graphs in stratified graphs

Chartrand, Gary ; Vanderjagt, Donald W. ; Zhang, Ping

Mathematica Bohemica, Tome 130 (2005) no. 1, pp. 35-48.

Résumé

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^{\prime }$ of $H$ containing $y$ and a color-preserving isomorphism $\phi $ from $G$ to $H^{\prime }$ 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 $\mathop {\mathrm 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 $\mathop {\mathrm 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 $\mathop {\mathrm fe}(G) = 2n.$

Détail

DOI : 10.21136/MB.2005.134221

Classification : 05C10, 05C15
Keywords: stratified graph; homogeneous embedding; framing number; fencing number