The maximum clique or maximum independent set of graph is a classical problem in graph theory. Com- bined with Boolean algebra and integer programming, two integer programming models for maximum clique problem, which ...The maximum clique or maximum independent set of graph is a classical problem in graph theory. Com- bined with Boolean algebra and integer programming, two integer programming models for maximum clique problem, which improve the old results were designed in this paper. Then, the programming model for maximum independent set is a corollary of the main results. These two models can be easily applied to computer algorithm and software, and suitable for graphs of any scale. Finally the models are presented as Lingo algorithms, verified and compared by sev- eral examples.展开更多
Two definitions are given that Definitionl： an induced subgraph by a vertex vie G and its neighbors in G is defined as a vertex adjacent closed subgraph, and denoted by Qi （=G[V（Nvi）]）, with the vertex vi called ...Two definitions are given that Definitionl： an induced subgraph by a vertex vie G and its neighbors in G is defined as a vertex adjacent closed subgraph, and denoted by Qi （=G[V（Nvi）]）, with the vertex vi called the hub; and Definition2： A r（k,I）-I vertices graph is called the （k,l）-Ramsey graph, denoted by RG（k,1）, if RG（k,1） only contains cliques Kk.1 and the intersect QiNQj of any two nonadjacent vertices vi and vj of RG（k,I） contains only Kk-2. Meanwhile, the RG（k,l）＇s complement RG（I,k） contains only cliques Kl.l, and the intersect QiNQj of any two nonadjacent vertices vi and vj of RG（I,k） contains only Ki.2. On the basis of those definitions, two theorems are put forward and proved in this paper. They are Theoreml： the biggest clique in G is contained in some Qi of G, and Theorem 2： r（k,1） = [V（RG（k,I））I ＋ 1. With those definitions and theorems as well as analysis of chord property, a method for quick inspection and building RG（k,1） is proposed. Accordingly, RG（4,6） is built, it is a strongly 14-regular graph on order 35. We have tested RG（4,6） and its complement, as a result, they meet the defintion2, so we proclaim that r（4,6）=36.展开更多
文摘The maximum clique or maximum independent set of graph is a classical problem in graph theory. Com- bined with Boolean algebra and integer programming, two integer programming models for maximum clique problem, which improve the old results were designed in this paper. Then, the programming model for maximum independent set is a corollary of the main results. These two models can be easily applied to computer algorithm and software, and suitable for graphs of any scale. Finally the models are presented as Lingo algorithms, verified and compared by sev- eral examples.
文摘Two definitions are given that Definitionl： an induced subgraph by a vertex vie G and its neighbors in G is defined as a vertex adjacent closed subgraph, and denoted by Qi （=G[V（Nvi）]）, with the vertex vi called the hub; and Definition2： A r（k,I）-I vertices graph is called the （k,l）-Ramsey graph, denoted by RG（k,1）, if RG（k,1） only contains cliques Kk.1 and the intersect QiNQj of any two nonadjacent vertices vi and vj of RG（k,I） contains only Kk-2. Meanwhile, the RG（k,l）＇s complement RG（I,k） contains only cliques Kl.l, and the intersect QiNQj of any two nonadjacent vertices vi and vj of RG（I,k） contains only Ki.2. On the basis of those definitions, two theorems are put forward and proved in this paper. They are Theoreml： the biggest clique in G is contained in some Qi of G, and Theorem 2： r（k,1） = [V（RG（k,I））I ＋ 1. With those definitions and theorems as well as analysis of chord property, a method for quick inspection and building RG（k,1） is proposed. Accordingly, RG（4,6） is built, it is a strongly 14-regular graph on order 35. We have tested RG（4,6） and its complement, as a result, they meet the defintion2, so we proclaim that r（4,6）=36.
