The maximum number of edges in a graph with fixed edge-degree

DOI10.1016/S0012-365X(97)00078-2MaRDI QIDQ1382818zbMATH OpenFDO

Authors Ralph Faudree, J. Sheehan

Publication date 18 March 1998

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0012-365X(97)00078-2

zbMATH Keywords

fixed edge-degreemaximum number of edges

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

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.

Cites work

• 2-linked graphs
• scientific article; zbMATH DE number 3902655 (Why is no real title available?)
• scientific article; zbMATH DE number 19187 (Why is no real title available?)

Cited in

(3)

• The number of edges in a maximum cycle-distributed graph
• scientific article; zbMATH DE number 5159426 (Why is no real title available?)
• scientific article; zbMATH DE number 721636 (Why is no real title available?)

This page was built for publication: The maximum number of edges in a graph with fixed edge-degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1382818)