On Lagrangians of r-uniform hypergraphs

Yuejian Peng (), Qingsong Tang () and Cheng Zhao ()
Additional contact information
Yuejian Peng: Hunan University
Qingsong Tang: Northeastern University
Cheng Zhao: Jilin University

Journal of Combinatorial Optimization, 2015, vol. 30, issue 3, No 24, 812-825

Abstract: Abstract A remarkable connection between the order of a maximum clique and the Lagrangian of a graph was established by Motzkin and Straus in Can J Math 17:533–540 (1965). This connection and its extensions were successfully employed in optimization to provide heuristics for the maximum clique number in graphs. It has been also applied in spectral graph theory. Estimating the Lagrangians of hypergraphs has been successfully applied in the course of studying the Turán densities of several hypergraphs as well. It is useful in practice if Motzkin–Straus type results hold for hypergraphs. However, the obvious generalization of Motzkin and Straus’ result to hypergraphs is false. We attempt to explore the relationship between the Lagrangian of a hypergraph and the order of its maximum cliques for hypergraphs when the number of edges is in certain range. In this paper, we give some Motzkin–Straus type results for r-uniform hypergraphs. These results generalize and refine a result of Talbot in Comb Probab Comput 11:199–216 (2002) and a result in Peng and Zhao (Graphs Comb, 29:681–694, 2013).

Keywords: Cliques of hypergraphs; Lagrangians of hypergraphs; Optimization (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-013-9671-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:30:y:2015:i:3:d:10.1007_s10878-013-9671-3

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-013-9671-3

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().