On the maxima of motzkin-straus programs and cliques of graphs

Qingsong Tang (), Xiangde Zhang (), Cheng Zhao () and Peng Zhao ()
Additional contact information
Qingsong Tang: Northeastern University
Xiangde Zhang: Northeastern University
Cheng Zhao: Shandong University
Peng Zhao: Indiana State University

Journal of Global Optimization, 2022, vol. 84, issue 4, No 7, 989-1003

Abstract: Abstract In this paper, we establish a connection between the local maximizers (global maximizers) of a Motzkin-Straus quadratic program and a specific type of regular multipartite cliques. Our work extends a remarkable connection between the maximum cliques and the global maximizers of the Motzkin-Straus quadratic program. This connection and its extensions can be successfully employed in optimization to provide heuristics for the maximal cliques in graphs. We provide two counterexamples to the results from previous work about the global and local maximizers of the Motzkin-Straus quadratic program. We then amend the previous theorems by introducing a new structure. We also answer two questions raised by Pelillo and Jagota about the maxima of the Motzkin-Straus quadratic program.

Keywords: Cliques of graphs; Lagrangian of graphs; Quadratic program; Motzkin-Straus; 05C35; 05C65; 05D99; 90C27; 90C30 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-022-01187-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:jglopt:v:84:y:2022:i:4:d:10.1007_s10898-022-01187-3

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-022-01187-3

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

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