Sobre o número de cruzamentos do grafo de Kneser K(n,2)

  • A. D. R. de Sousa UERJ
  • J. C. Carneiro UERJ
  • L. Faria UERJ
  • M. V. Pabon Université Paris-13

Resumo


O número de cruzamentos $\nu(G)$ de um grafo $G=(V,E)$ é o menor número de cruzamentos em um desenho $D(G)$ no plano de $G$. Dada uma reta $r$, chamada espinha, $p\geq 1$, e $S_1,\ldots,S_p$ serem $p$ semiplanos distintos limitados por $r$, um desenho de $G=(V,E)$ em $p$-páginas tem os vértices de $V$ desenhados em $r$ e cada aresta de $G$ é desenhada em um $S_1,\ldots,S_p$. O número de cruzamentos em $p$-páginas $\nu_p(G)$ de $G$ é o menor número de cruzamentos em um desenho de $G$ em $p$ páginas. Nós provamos que se $n=2q\geq 6$, então $\frac{n^8} {2^{13}} - 9\frac{n^7}{2^{13}} - \frac{n^6}{2^{10}} - \frac{n^4} {2^{7}} - \frac{n^3}{2^{9}} \leq \nu(K(n,2))\leq \nu_2(K(n,2))\ leq \frac{n^8}{2^{10}} - \frac{3n^7}{2^8} + \frac{31n^6}{2^83} + \ frac{7n^5}{2^6} - \frac{563n^4}{2^73} + \frac{517n^3}{2^53} - \ frac{267n^2}{2^5} + \frac{107n}{2^33}$. Como os grafos completos $\nu_2(K(n,2))=\Theta(|V(K(n,2)|^4)=\nu(K(n,2))$ cujo termo líder $\ell(n)$ satisfaz $\frac{1}{2^{13}}\leq \ell(n)\leq \frac{1}{2^{10}}$.

Palavras-chave: número de cruzamentos, Grafo de Kneser K(n, 2)

Referências

Ábrego, B. M., Aichholzer, O., Fernández-Merchant, S., Ramos, P., and Salazar, G. (2013). The 2-page crossing number of Kn. Discret. Comput. Geom., 49(4):747–777.

Berge, C. (1973). Graphs and hypergraphs. North-Holland Pub. Co.

de Klerk, E., Pasechnik, D. V., and Salazar, G. (2013). Improved lower bounds on book crossing numbers of complete graphs. SIAM J. Discret. Math., 27(2):619–633.

Faria, L., de Figueiredo, C. M. H., Richter, R. B., and Vrt’o, I. (2016). The same upper bound for both: The 2-page and the rectilinear crossing numbers of the n-cube. J. Graph Theory, 83(1):19–33.

Hlinený, P. (2006). Crossing number is hard for cubic graphs. J. Comb. Theory, Ser. B, 96(4):455–471. Kneser, M. (1955). Aufgabe 360, Jber. Deutsch. Math. Verein, 58:27.

Székely, L. A. (1997). Crossing numbers and hard Erdos problems in discrete geometry. Combinatorics, Probability and Computing, 6(3):353–358.
Publicado
31/07/2022
SOUSA, A. D. R. de; CARNEIRO, J. C.; FARIA, L.; PABON, M. V.. Sobre o número de cruzamentos do grafo de Kneser K(n,2). In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 7. , 2022, Niterói. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2022 . p. 61-64. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2022.222905.