| viXra.org > Combinatorics and Graph Theory > 2202 |
 |
 |
| viXra.org > Combinatorics and Graph Theory > 2202 |
|
|
[2] viXra:2202.0143 [pdf] replaced on 2022-05-03 05:50:54
Authors: Majid Zohrehbandian
Comments: 7 Pages. Due to some comments, I preferred to add some explanations.
Vertex cover problem is a famous combinatorial problem, which its complexity has been heavily studied over the years and we know that there is not any mathematical formulation that approximates it better than 2-o(1). In other words, it is known that it is hard to approximate to within any constant factor better than 2, while a 2-approximation for it can be trivially obtained. In this paper, by a combination of a well-known semidefinite programming formulation and a rounding procedure, along with satisfying new properties, we introduce an approximation algorithm for the vertex cover problem with a performance ratio of 1.885903 on arbitrary graphs, en route answering an open question about the unique games conjecture.
Category: Combinatorics and Graph Theory
[1] viXra:2202.0001 [pdf] submitted on 2022-02-01 11:55:59
Authors: Yixin Li
Comments: 34 Pages.
Bridge graphs are special type of graphs which are constructed by connecting identical connected graphs with path graphs. We discuss different type of bridge graphs $B_{n\times l}^{m\times k}$ in this paper. In particular, we discuss the following: complete-type bridge graphs, star-type bridge graphs, and full binary tree bridge graphs. We also bound the second eigenvalues of the graph Laplacian of these graphs using methods from Spectral Graph Theory. In general, we prove that for general bridge graphs, $B_{n\times l}^2$, the second eigenvalue of the graph Laplacian should between $0$ and $2$, inclusive. At the end, we talk about the future work about infinite bridge graphs. We create definitions and found the related theorems to support our future work about infinite bridge graphs.
Category: Combinatorics and Graph Theory
| Third-Party Links: |
|