The direct expansion of graphs (Q1349072)

Expansion procedures introduced by \textit{H. M. Mulder} [The expansion procedure for graphs, in: Contemporary methods in graph theory. In honour of Prof. Dr. K. Wagner, 459-477 (1990; Zbl 0744.05064)] proved to be useful in recognition of median, quasi-median and partial Hamming graphs. Here the author focuses on connectivity properties of one particular such procedure, the direct expansion. Given a covering of a graph \(G\) by two induced subgraphs \(G_1\) and \(G_2\) with intersection \(G_0\) (no edges linking \(V(G_1)-V (G_0)\) with \(V(G_2)-V(G_0)\)), the direct expansion \(G'\) of \(G\) (relative to this covering) is obtained by replacing \(G_0\) by the direct product \(G_0\times K_2\), leaving \(G_1-G_0\) and \(G_2-G_0\) unchanged, and edges linking \(V(G_1)-V (G_0)\) (resp. \(V(G_2)-V(G_0)\)) with \(V(G_0)\) in \(G\) correspond to edges linking \(V(G_1)-V(G_0)\) with \(V(G_0)\times \{ 1\}\) (resp. \(V(G_2)-V(G_0)\) with \(V(G_0) \times \{ 2\})\) in \(G'\). The questions addressed in the paper are the following ones: (1) when is a direct expansion a connected graph and (2) what is the length \(\text{del} (G)\) of the longer sequence of iterative direct expansions on a given graph \(G\) which produce a disconnected graph only in the last step (a measure of robustness with respect to direct expansion). In both questions, trivial direct expansions, i.e. \(G_2=K_1\), are excluded since they always produce disconnected graphs. A characterization of coverings whose direct expansion give rise to a connected graph is given in terms of parity of cycles or expanding walks in each of the two copies of \(G_0\) in the expanded graph. As a result, it is shown that trees are the only connected graphs such that direct expansions are always disconnected, and there is a characterization of graphs such that all nontrivial direct expansions are connected. In particular, graphs with del\((G)=0\) are nonconnected graphs and trees are the ones with del\((G)=1\). Characterization of graphs with del\((G)=2\) is given and it is proved that graphs containing \(K_4\) have del\((G)=\infty \).