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 (MSC 1991): 05C12
Full text available as PDF (smallest), as compressed PostScript (.ps.gz) or as raw PostScript (.ps).
Access to the full text of journal articles on this site is restricted to the subscribers of Myris Trade. To activate your access, please contact Myris Trade at myris@myris.cz.
