The direct expansion of graphs
type: Item
instance of: scholarly article
title: The direct expansion of graphs
zbMATH Open document ID: 0990.05088
DOI: 10.1016/S0012-365X(01)00066-8
author: Boštjan Brešar
published in: Discrete Mathematics
publication date: 2002-05-21T00:00:00Z
review text: 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…
reviewed by: Oriol Serra
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 1743008
zbMATH Keywords: direct product
zbMATH Keywords: expansion
zbMATH Keywords: connectivity
MaRDI profile type: Publication
full work available at URL: s0012-365x(01)00066-8
OpenAlex ID: W1996265432
description: scientific article; zbMATH DE number 1743008