MATHEMATICA BOHEMICA, Vol. 122, No. 4, pp. 337-347 (1997)

Stratidistance in stratified graphs

Gary Chartrand, Heather Gavlas, Michael A. Henning, Reza Rashidi

Gary Chartrand, Department of Mathematics & Statistics, Western Michigan University, Kalamazoo, MI 49008; Heather Gavlas, Department of Mathematics & Statistics, Grand Valley State University, Allendale, MI 49401; Michael A. Henning, Department of Mathematics, University of Natal, Private Bag X01, Scottwsville, Pietermaritzburg 3209, South Africa; Reza Rashidi, University Computing Services, Western Michigan University, Kalamazoo, MI 49008

Abstract: A graph $G$ is a stratified graph if its vertex set is partitioned into classes (each of which is a stratum or a color class). A stratified graph with $k$ strata is $k$-stratified. If $G$ is a connected $k$-stratified graph with strata $S_i$ $(1\le i\le k)$ where the vertices of $S_i$ are colored $X_i$ $(1\le i\le k)$, then the $X_i$-proximity $\rho_{X_i} (v)$ of a vertex $v$ of $G$ is the distance between $v$ and a vertex of $S_i$ closest to $v$. The strati-eccentricity $ se(v)$ of $v$ is $\max\{\rho_{X_i}(v)\mid1\le i\le k\}$. The minimum strati-eccentricity over all vertices of $G$ is the stratiradius $ sr(G)$ of $G$; while the maximum strati-eccentricity is its stratidiameter $ sd(G)$. For positive integers $a,b,k$ with $a\le b$, the problem of determining whether there exists a $k$-stratified graph $G$ with $ sr(G)=a$ and $ sd(G)=b$ is investigated.

A vertex $v$ in a connected stratified graph $G$ is called a straticentral vertex if $ se(v)= sr(G)$. The subgraph of $G$ induced by the straticentral vertices of $G$ is called the straticenter of $G$. It is shown that every $\ell$-stratified graph is the straticenter of some $k$-stratified graph. Next a stratiperipheral vertex $v$ of a connected stratified graph $G$ has $ se(v)= sd(G)$ and the subgraph of $G$ induced by the stratiperipheral vertices of $G$ is called the stratiperiphery of $G$. Almost every stratified graph is the stratiperiphery of some $k$-stratified graph. Also, it is shown that for a $k_1$-stratified graph $H_1$, a $k_2$-stratified graph $H_2$, and an integer $n\ge2$, there exists a $k$-stratified graph $G$ such that $H_1$ is the straticenter of $G$, $H_2$ is the stratiperiphery of $G$, and $d(H_1,H_2)=n$.

Keywords: graph, distance, center and periphery

Classification (MSC2000): 05C12

Full text of the article:

[Next Article] [Contents of this Number] [Journals Homepage]
© 1999--2000 ELibM for the EMIS Electronic Edition