Name
Abstract | ||
|---|---|---|
In this paper we modify slightly Razborov's flag algebra machinery to be suitable for the hypercube. We use this modified method to show that the maximum number of edges of a 4-cycle-free subgraph of the n-dimensional hypercube is at most 0.6068 times the number of its edges. We also improve the upper bound on the number of edges for 6-cycle-free subgraphs of the n-dimensional hypercube from 2-1 to 0.3755 times the number of its edges. Additionally, we show that if the n-dimensional hypercube is considered as a poset then the maximum vertex density of three middle layers in an induced subgraph without 4-cycles is at most 2.15121(n@?n/2@?). |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.ejc.2013.06.003 | Eur. J. Comb. |
Keywords | Field | DocType |
modified method,induced subgraph,middle layer,flag algebra machinery,maximum vertex density,n-dimensional hypercube,4-cycle-free subgraph,6-cycle-free subgraphs,maximum number,upper bound | Discrete mathematics,Combinatorics,Vertex (geometry),Hypercube graph,Upper and lower bounds,Induced subgraph,Hypercube,Partially ordered set,Mathematics | Journal |
Volume | ISSN | Citations |
35, | 0195-6698 | 12 |
PageRank | References | Authors |
0.80 | 16 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| József Balogh | 1 | 862 | 89.91 |
| Ping Hu | 2 | 32 | 4.05 |
| Bernard Lidický | 3 | 181 | 23.68 |
| Hong Liu | 4 | 39 | 8.54 |