Stratified Graphs and Distance Graphs

Abstract

We address questions of Chartrand et al. about $k$-stratified graphs and distance graphs. A $k$-stratified graph $G$ is a graph whose vertices have been partitioned into $k$ distinct color classes, or strata. An underlying graph $G^{\prime }$ is obtained by ignoring the colors of $G$. We prove that for every pair of positive integers $k$ and $l$, there exists a pair of $2$-stratified graphs with exactly $k$ greatest common stratified subgraphs such that their underlying graphs have exactly $l$ greatest common subgraphs.

A distance graph $D(A)$ has vertices from some set $A$ of $0-1$ sequences of a fixed length and fixed weight. Two vertices are adjacent if one of the corresponding sequences can be obtained from the other by the interchange of a $0$ and $1$. If $G$ is a graph of order $m$ that can be realized as the distance graph of $0-1$ sequences, then we prove that the $0-1$ sequences require length at most $2m-2$. We present a list of minimal forbidden induced subgraphs of distance graphs of $0-1$ sequences.

A distance graph $D(G)$ has vertices from some set $G$ of graphs or $k$-stratified graphs. Two vertices are adjacent if one of the corresponding graphs can be obtained from the other by a single edge rotation. We prove that $K_n$ minus an edge is a distance graph of a set of graphs. We fully characterize which radius one graphs are distance graphs of $0-1$ sequences and which are distance graphs of graphs with distinctly labelled vertices.