| Title:
|
Homogeneously embedding stratified graphs in stratified graphs (English) |
| Author:
|
Chartrand, Gary |
| Author:
|
Vanderjagt, Donald W. |
| Author:
|
Zhang, Ping |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
130 |
| Issue:
|
1 |
| Year:
|
2005 |
| Pages:
|
35-48 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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.$ (English) |
| Keyword:
|
stratified graph |
| Keyword:
|
homogeneous embedding |
| Keyword:
|
framing number |
| Keyword:
|
fencing number |
| MSC:
|
05C10 |
| MSC:
|
05C15 |
| idZBL:
|
Zbl 1111.05021 |
| idMR:
|
MR2128357 |
| DOI:
|
10.21136/MB.2005.134221 |
| . |
| Date available:
|
2009-09-24T22:17:47Z |
| Last updated:
|
2020-07-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/134221 |
| . |
| Reference:
|
[1] G. Chartrand, Heather J. Gavlas, M. Schultz: Framed! A graph embedding problem.Bull. Inst. Comb. Appl. 4 (1992), 35–50. MR 1147971 |
| Reference:
|
[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 1369256 |
| Reference:
|
[3] G. Chartrand, H. Gavlas, M. A. Henning, R. Rashidi: Stratidistance in stratified graphs.Math. Bohem. 122 (1997), 337–347. MR 1489394 |
| Reference:
|
[4] G. Chartrand, T. W. Haynes, M. A. Henning, P. Zhang: Stratification and domination in graphs.Discrete Math. 272 (2003), 171–185. MR 2009541, 10.1016/S0012-365X(03)00078-5 |
| Reference:
|
[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 1772755 |
| Reference:
|
[6] G. Chartrand, L. Hansen, R. Rashidi, N. A. Sherwani: Distance in stratified graphs.Czechoslovak Math. J. 125 (2000), 35–46. MR 1745456 |
| Reference:
|
[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 0223264 |
| Reference:
|
[8] D. König: Theorie der endlichen und unendlichen Graphen.Leipzig, 1936. Reprinted Chelsea, New York, 1950. |
| . |
