Two extremal problems in graph theory

MaRDI QIDQ1344395zbMATH OpenFDO

Authors Richard A. Brualdi, Stephen Mellendorf

Publication date 12 February 1995

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/118558, http://www.emis.de/journals/EJC/Volume_1/volume1.html#R2

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

extremal problems maximum number of edges

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Review text

Summary: We consider the following two problems. (1) Let \(t\) and \(n\) be positive integers with \(n\geq t\geq 2\). Determine the maximum number of edges of a graph of order \(n\) that contains neither \(K_ t\) nor \(K_{t,t}\) as a subgraph. (2) Let \(r\), \(t\) and \(n\) be positive integers with \(n\geq rt\) and \(t\geq 2\). Determine the maximum number of edges of a graph of order \(n\) that does not contain \(r\) disjoint copies of \(K_ t\). Problem 1 for \(n< 2t\) is solved by Turán's theorem and we solve it for \(n= 2t\). We also solve Problem 2 for \(n= rt\).

Recommendations

Cited in

(18)

This page was built for publication: Two extremal problems in graph theory

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