On Graph-Lagrangians of Hypergraphs Containing Dense Subgraphs |
| |
Authors: | Qingsong Tang Yuejian Peng Xiangde Zhang Cheng Zhao |
| |
Institution: | 1. College of Sciences, Northeastern University, Shenyang, 110819, P.R. China 2. School of Mathematics, Jilin University, Changchun, 130012, P.R. China 3. College of Mathematics, Hunan University, Changchun, 410082, P.R. China 4. Department of Mathematics and Computer Science, Indiana State University, Terre Haute, IN, 47809, USA
|
| |
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: | |
本文献已被 SpringerLink 等数据库收录! |
|