Stratified Graphs and Distance Graphs

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’\) 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.