Previous |  Up |  Next

Article

Keywords:
graph; distance center; periphery; center and periphery
Summary:
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$.
References:
[1] G. Chartrand L. Eroh R. Rashidi M. Schultz, and N. A. Sherwani: Distance, stratified graphs, and greatest stratified subgraphs. Congress. Numer. 107(1995), 81-96. MR 1369256
[2] G. Chartrand L. Holley R. Rashidi, and N. A. Sherwani: Distance in stratified graphs. Preprint.
[3] R. Rashidi: The Theory and Applications of Stratified Graphs. Ph. D. Dissertation, Western Michigan University (1994). MR 2692329
Partner of
EuDML logo