Skip to main content
Article
On a Problem of Ahlswede and Katona
Studia Scientiarum Mathematicarum Hungarica
  • Stephan G. Wagner, Stellenbosch University
  • Hua Wang, Georgia Southern University
Document Type
Article
Publication Date
7-4-2009
DOI
10.1556/SScMath.2009.1107
Disciplines
Abstract

Let p ( G ) denote the number of pairs of adjacent edges in a graph G . Ahlswede and Katona considered the problem of maximizing p ( G ) over all simple graphs with a given number n of vertices and a given number N of edges. They showed that p ( G ) is either maximized by a quasi-complete graph or by a quasi-star. They also studied the range of N (depending on n ) for which the quasi-complete graph is superior to the quasi-star (and vice versa) and formulated two questions on distributions in this context. This paper is devoted to the solution of these problems.

Citation Information
Stephan G. Wagner and Hua Wang. "On a Problem of Ahlswede and Katona" Studia Scientiarum Mathematicarum Hungarica Vol. 46 Iss. 3 (2009) p. 423 - 435 ISSN: 1588-2896
Available at: http://works.bepress.com/hua_wang/93/