Premium
Nearly uniform distribution of edges among k ‐subgraphs of a graph
Author(s) -
Širáň Jozef,
Tuza Zsolt
Publication year - 1992
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190160606
Subject(s) - combinatorics , mathematics , graph , complement (music) , complement graph , path graph , integer (computer science) , multiple edges , discrete mathematics , graph power , line graph , computer science , biochemistry , chemistry , complementation , programming language , gene , phenotype
We investigate the behavior of the function f = f(n, k, e) defined as the smallest integer with the following property: If in a graph on n vertices, the numbers of edges in any two induced subgraphs on k vertices differ by at most e , then the graph or its complement has at most f edges. One of the results states that\documentclass{article}\pagestyle{empty}\begin{document}$$ f(n,k,e) =e\;{\rm for}\,n \ge (2\sqrt 2 + \varepsilon)e^{3/2} \,{\rm and}\,{\rm 2e + 2} \le {\rm k} \le n - 4e - 3 $$\end{document} . © 1929 John Wiley & Sons, Inc.