On optimal orientations of \(G\) vertex-multiplications
type: Item
instance of: scholarly article
title: On optimal orientations of \(G\) vertex-multiplications
zbMATH Open document ID: 0946.05036
DOI: 10.1016/S0012-365X(99)00373-8
published in: Discrete Mathematics
publication date: 2000-10-18T00:00:00Z
review text: Given a connected graph \(G\) with vertex set \(V(G)=\{v_1, v_2, \dots, v_n\}\) and a sequence of positive integers \(s_1, s_2, \dots, s_n\) one can produce a new graph \(H=G(s_1,s_2,\dots,s_n)\) called \(G\) vertex-multiplication in such a way that each vertex \(v_i\) is multiplied by \(s_i\) (i.e. \(v_i\) is replaced by \(s_i\) independent vertices with equal neighborhoods). E.g. if \(G\) is a complete graph of order \(n\), then \(H\) is a complete \(n\)-partite graph. The authors study the relation between the diameter of \(G\), \(d(G)\), and the minimum diameter of an orientation of \(H\), \(\overline d(H)\). They show that if \(s_i\geq 2\) for each \(i=1,2,\dots,n\) where \(n\geq 3\), then \(\overline d(H)\leq d(G)+2\). As \(d(G)\leq \overline d(H)\), this gives rise to three classes of graphs according to \(\overline d(H)=d(G)+j\), for \(j=0,1,2\). The authors exhibit various families of graphs for each of the classes. E.g., they prove that if \(d(G)\geq 4\) and each \(s_i\geq 4\), then \(j=0\).
reviewed by: Ján Plesník
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 1462325
zbMATH Keywords: diameter
zbMATH Keywords: optimal orientation
zbMATH Keywords: digraph
Wikidata QID: Q114122920
author: K. M. Koh
author: E. G. Tay
MaRDI profile type: Publication
full work available at URL: s0012-365x(99)00373-8
OpenAlex ID: W2037578638
description: scientific article; zbMATH DE number 1462325