Algebraic Cayley graphs over finite fields

A new algebraic Cayley graph is constructed using finite fields. It provides a more flexible source of expander graphs. Its connectedness, the number of connected components, and diameter bound are studied via Weil's estimate for character sums. Furthermore, we study the algorithmic problem of computing the number of connected components and establish a link to the integer factorization problem.     

Probabilistische analyse von heuristiken der kombinatorischen optimierung – ein überbllck

To various problems of combinatorial optimization we consider the question how the value of the optimal solution resp. the values of some approximative solutions are predetermined with high probability to a given distribution. We present results to probabilistic analysis of heuristics. We consider the problems Traveling Salesman, Minimum Perfect Matching. Minimum Spanning Tree, Linear Optimization, Bin Packing, Multi-processor-Scheduling, Subset Sum and some problems to random graphs.     

On a connection between facility location and perfect graphs

We characterize the graphs for which a linear relaxation of a facility location problem defines a polytope with all integral extreme points. We use a transformation to a stable set problem in perfect graphs. Based on this transformation, these graphs can be recognized in polynomial time.     

两类特殊图的逆符号边控制数

设G=(V,E)是一个图,对于图G的一个函数f:E→{-1,1},如果对任意e∈E(G),均有Σe′∈N[e]f(e′)≤1,则称f为图G的一个逆符号边控制函数.图G的逆符号边控制数γ′s(G)=max{Σe∈E(G)f(e)|f为图G的一个逆符号边控制函数}.在逆符号边控制数定义基础上,得到了所有轮图和扇图的逆符号边控制数.     

探讨几类具有完全图核心的网络模型的优美性

在复杂网络研究中,人们需要建立网络模型,无标度图就是这样的一种网络模型.我们发现具有完全图核心的网络模型可以演变成无标度图.具有完全图核心的几种网络模型的优美性得到研究.     

A threshold for the Maker‐Breaker clique game

We study the Maker‐Breaker k‐clique game played on the edge set of the random graph G(n, p). In this game, two players, Maker and Breaker, alternately claim unclaimed edges of G(n, p), until all the edges are claimed. Maker wins if he claims all the edges of a k‐clique; Breaker wins otherwise. We determine that the threshold for the graph property that Maker can win this game is at , for all k > 3, thus proving a conjecture from Ref. [Stojakovi? and Szabó, Random Struct Algor 26 (2005), 204–223]. More precisely, we conclude that there exist constants such that when the game is Maker's win a.a.s., and when it is Breaker's win a.a.s. For the triangle game, when k = 3, we give a more precise result, describing the hitting time of Maker's win in the random graph process. We show that, with high probability, Maker can win the triangle game exactly at the time when a copy of K₅ with one edge removed appears in the random graph process. As a consequence, we are able to give an expression for the limiting probability of Maker's win in the triangle game played on the edge set of G(n, p). © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 45, 318–341, 2014     

The Inducibility of Graphs on Four Vertices

We consider the problem of determining the maximum induced density of a graph H in any graph on n vertices. The limit of this density as n tends to infinity is called the inducibility of H. The exact value of this quantity is known only for a handful of small graphs and a specific set of complete multipartite graphs. Answering questions of Brown–Sidorenko and Exoo, we determine the inducibility of K_{1, 1, 2} and the paw graph. The proof is obtained using semidefinite programming techniques based on a modern language of extremal graph theory, which we describe in full detail in an accessible setting.     

Bipartite graphs with the maximum sum of squares of degrees

In this paper we determine all the bipartite graphs with the maximum sum of squares of degrees among the ones with a given number of vertices and edges.