Highly irregular m-chromatic graphs
type: Item
instance of: scholarly article
title: Highly irregular m-chromatic graphs
zbMATH Open document ID: 0667.05052
DOI: 10.1016/0012-365X(88)90188-4
author: Yousef Alavi
author: Fred Buckley
author: Marc Shamula
author: Sergio Ruiz
published in: Discrete Mathematics
publication date: 1988-01-01T00:00:00Z
review text: As the authors note, regular graphs have been much studied. Therefore they have turned their attention to highly irregular graphs. These are characterised by the requirement that no two vertices with a common neighbour have the same valency. The bulk of this paper is devoted to trees and bipartite graphs. I will list most of the main results, not all in their strongest form. They observe that a highly irregular tree with maximum valency \(\Delta\) must have at least \(2^{\Delta}\) vertices. (The study of the class of trees with maximum valency \(\Delta\) is made more significant, in their view, by the fact that trees with maximum valency four are of interest in chemistry.) The authors prove that a highly irregular tree on n vertices exists for all n greater than 13, and that a highly irregular tree with maximum valency three on n vertices exists if and only if \(n>8\) and \(n\equiv 2,3\) or 4 (modulo 6). They then turn their attention to bipartite graphs. Here they prove that a highly irregular unicyclic graph with maximum valency three and girth g exists if and only if g is divisible by four. They prove that if a highly irregular bipartite graph with maximum valency four and girth g on n vertices exists then \(n\geq 3g/2\). Finally, they show that if \(n\geq 2\Delta \geq 8\) then there is highly irregular graph on n vertices with maximum valency \(\Delta\).
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 4091560
zbMATH Keywords: highly irregular graphs
zbMATH Keywords: irregular tree
zbMATH Keywords: bipartite graphs
MaRDI profile type: Publication
cites work: Highly irregular graphs
cites work: Q3347931
cites work: Q5782525
cites work: Q3900110
cites work: Extremal f-trees and embedding spaces for molecular graphs
cites work: Characterization of line graphs
cites work: Cages—a survey
description: scientific article; zbMATH DE number 4091560