Regularizing irregular graphs
type: Item
instance of: scholarly article
title: Regularizing irregular graphs
zbMATH Open document ID: 0789.05085
DOI: 10.1016/0895-7177(93)90249-X
author: Fred Buckley
published in: Mathematical and Computer Modelling
publication date: 1994-01-02T00:00:00Z
review text: A connected graph is highly irregular if the neighbours of every vertex all have distinct degrees. It is known that for each positive integer \(k\) there exists a unique unicyclic highly irregular graph \(U_ k\) of girth \(4k\) and order \(6k\) and maximum degree 3. The author shows that for each \(k\) there is an embedding of \(U_ k\) as an induced subgraph of a cubic self-centered graph \(H\) having connectivity and edge-connectivity 3. Moreover, the graph \(H\) that is constructed is such that its diameter is 4 if \(k=2\) and \(k+1\) otherwise. It is known that there exists a unique highly irregular \(d\times d\) bipartite graph \(B_ d\) with maximum degree \(d\). The author shows that for each \(d \geq 2\), the highly irregular graph \(B_ d\) can be embedded as induced subgraph in a \(d\)-regular self- centered graph with diameter 2 and connectivity and edge-connectivity both equal to \(d\).
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 475036
zbMATH Keywords: highly irregular
zbMATH Keywords: embedding
zbMATH Keywords: connectivity
zbMATH Keywords: diameter
reviewed by: Ortrud R. Oellermann
MaRDI profile type: Publication
cites work: Highly irregular graphs
cites work: Highly irregular m-chromatic graphs
cites work: Q3347931
cites work: Characterization of line graphs
cites work: Cages—a survey
cites work: Q3900110
cites work: Q3861432
cites work: Q4294577
cites work: Extremal f-trees and embedding spaces for molecular graphs
description: scientific article; zbMATH DE number 475036