# Homogeneously embedding stratified graphs in stratified graphs

Gary Chartrand; Donald W. Vanderjagt; Ping Zhang

Mathematica Bohemica (2005)

- Volume: 130, Issue: 1, page 35-48
- ISSN: 0862-7959

## Access Full Article

top## Abstract

top## How to cite

topChartrand, 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 -

## References

top- Framed! A graph embedding problem, Bull. Inst. Comb. Appl. 4 (1992), 35–50. (1992) MR1147971
- Distance, stratified graphs, and greatest stratified subgraphs, Congr. Numerantium 107 (1995), 81–96. (1995) MR1369256
- Stratidistance in stratified graphs, Math. Bohem. 122 (1997), 337–347. (1997) MR1489394
- 10.1016/S0012-365X(03)00078-5, Discrete Math. 272 (2003), 171–185. (2003) MR2009541DOI10.1016/S0012-365X(03)00078-5
- Stratified claw domination in prisms, J. Comb. Math. Comb. Comput. 33 (2000), 81–96. (2000) MR1772755
- Distance in stratified graphs, Czechoslovak Math. J. 125 (2000), 35–46. (2000) MR1745456
- The minimum regular graph containing a given graph, A Seminar on Graph Theory, F. Harary (ed.), Holt, Rinehart and Winston, New York, 1967, pp. 65–69. (1967) MR0223264
- Theorie der endlichen und unendlichen Graphen, Leipzig, 1936. Reprinted Chelsea, New York, 1950.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.