Geodesic
Homogeneously embedding stratified graphs in stratified graphs
Mathematica Bohemica, Tome 130 (2005) no. 1, pp. 35-48

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

MR Zbl
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.$
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.$
DOI : 10.21136/MB.2005.134221
Classification : 05C10, 05C15
Keywords: stratified graph; homogeneous embedding; framing number; fencing number 
Chartrand, Gary; Vanderjagt, Donald W.; Zhang, Ping. Homogeneously embedding stratified graphs in stratified graphs. Mathematica Bohemica, Tome 130 (2005) no. 1, pp. 35-48. doi: 10.21136/MB.2005.134221
@article{10_21136_MB_2005_134221,
     author = {Chartrand, Gary and Vanderjagt, Donald W. and Zhang, Ping},
     title = {Homogeneously embedding stratified graphs in stratified graphs},
     journal = {Mathematica Bohemica},
     pages = {35--48},
     year = {2005},
     volume = {130},
     number = {1},
     doi = {10.21136/MB.2005.134221},
     mrnumber = {2128357},
     zbl = {1111.05021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2005.134221/}
}
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
SP  - 35
EP  - 48
VL  - 130
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2005.134221/
DO  - 10.21136/MB.2005.134221
LA  - en
ID  - 10_21136_MB_2005_134221
ER  - 
%0 Journal Article
%A Chartrand, Gary
%A Vanderjagt, Donald W.
%A Zhang, Ping
%T Homogeneously embedding stratified graphs in stratified graphs
%J Mathematica Bohemica
%D 2005
%P 35-48
%V 130
%N 1
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2005.134221/
%R 10.21136/MB.2005.134221
%G en
%F 10_21136_MB_2005_134221

[1] G. Chartrand, Heather J. Gavlas, M. Schultz: Framed! A graph embedding problem. Bull. Inst. Comb. Appl. 4 (1992), 35–50. | MR

[2] G. Chartrand, L. Eroh, R. Rashidi, M. Schultz, N. A. Sherwani: Distance, stratified graphs, and greatest stratified subgraphs. Congr. Numerantium 107 (1995), 81–96. | MR

[3] G. Chartrand, H. Gavlas, M. A. Henning, R. Rashidi: Stratidistance in stratified graphs. Math. Bohem. 122 (1997), 337–347. | MR

[4] G. Chartrand, T. W. Haynes, M. A. Henning, P. Zhang: Stratification and domination in graphs. Discrete Math. 272 (2003), 171–185. | DOI | MR

[5] G. Chartrand, T. W. Haynes, M. A. Henning, P. Zhang: Stratified claw domination in prisms. J. Comb. Math. Comb. Comput. 33 (2000), 81–96. | MR

[6] G. Chartrand, L. Hansen, R. Rashidi, N. A. Sherwani: Distance in stratified graphs. Czechoslovak Math. J. 125 (2000), 35–46. | MR

[7] P. Erdős, P. Kelly: 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. | MR

[8] D. König: Theorie der endlichen und unendlichen Graphen. Leipzig, 1936. Reprinted Chelsea, New York, 1950.

Cité par Sources :