Homogeneously embedding stratified graphs in stratified graphs

Chartrand, Gary, Vanderjagt, Donald W., and Zhang, Ping. "Homogeneously embedding stratified graphs in stratified graphs." Mathematica Bohemica 130.1 (2005): 35-48. <http://eudml.org/doc/249415>.

@article{Chartrand2005,
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^\{\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 \{f\}r\}(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 \{f\}e\}(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 \{f\}e\}(G) = 2n.$},
author = {Chartrand, Gary, Vanderjagt, Donald W., Zhang, Ping},
journal = {Mathematica Bohemica},
keywords = {stratified graph; homogeneous embedding; framing number; fencing number; homogeneous embedding; framing number; fencing number},
language = {eng},
number = {1},
pages = {35-48},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Homogeneously embedding stratified graphs in stratified graphs},
url = {http://eudml.org/doc/249415},
volume = {130},
year = {2005},
}

TY - JOUR
AU - Chartrand, Gary
AU - Vanderjagt, Donald W.
AU - Zhang, Ping
TI - Homogeneously embedding stratified graphs in stratified graphs
JO - Mathematica Bohemica
PY - 2005
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 130
IS - 1
SP - 35
EP - 48
AB - 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 {f}r}(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 {f}e}(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 {f}e}(G) = 2n.$
LA - eng
KW - stratified graph; homogeneous embedding; framing number; fencing number; homogeneous embedding; framing number; fencing number
UR - http://eudml.org/doc/249415
ER -