On Graph-Lagrangians of Hypergraphs Containing Dense Subgraphs

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

Journal of Optimization Theory and Applications, 2014, vol. 163, issue 1, No 2, 56 pages

Abstract: Abstract Motzkin and Straus established a remarkable connection between the maximum clique and the Graph-Lagrangian of a graph 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 is useful in practice if similar results hold for hypergraphs. In this paper, we provide upper bounds on the Graph-Lagrangian of a hypergraph containing dense subgraphs when the number of edges of the hypergraph is in certain ranges. These results support a pair of conjectures introduced by Peng and Zhao (Graphs Comb. 29:681–694, 2013) and extend a result of Talbot (Comb. Probab. Comput. 11:199–216, 2002).

Keywords: Cliques of hypergraphs; Colex ordering; Graph-Lagrangians of hypergraphs; Polynomial optimization (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-013-0485-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:joptap:v:163:y:2014:i:1:d:10.1007_s10957-013-0485-3

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-013-0485-3

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

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