The maximum number of edges in a graph with fixed edge-degree
type: Item
instance of: scholarly article
title: The maximum number of edges in a graph with fixed edge-degree
zbMATH Open document ID: 0894.05029
DOI: 10.1016/S0012-365X(97)00078-2
published in: Discrete Mathematics
publication date: 1998-03-18T00:00:00Z
review text: For \(t\geq 17\) and \(n\geq 2t+2\), let \(G\) be a graph with \(n\) vertices whose complement is connected, and such that for all non-adjacent vertices \(u,v\), there are at least \(t\) common neighbours. It is proved that \(| E(G)|\geq \lceil((2t+1)n- 2t^2- 3)/2\rceil\) for \(n\leq 3t-1\), and \(| E(G)|\geq (t+1)n- t^2- t-3\) for \(n\geq 3t\). Furthermore, it is shown that both of these results are sharp.
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1130767
zbMATH Keywords: maximum number of edges
zbMATH Keywords: fixed edge-degree
author: Ralph Faudree
author: J. Sheehan
reviewed by: Chris Jagger
MaRDI profile type: Publication
cites work: Q3976616
cites work: Q3680834
cites work: 2-linked graphs
description: scientific article; zbMATH DE number 1130767