What type of study is this?

This is a Quantitative Study study.

October 20, 2025Open Access

Conectividade hamiltoniana de alguns gráficos base-cobase

Key Points

A conectividade hamiltoniana é mostrada para gráficos base-cobase das extensões série-paralela de matroides de caminho de rede, revelando propriedades estruturais.
O método para estabelecer a conectividade hamiltoniana se estende apenas a certas classes de matroides idênticos auto-duais, indicando limites à generalização.
Os gráficos base-cobase de rodas e redemoinhos são confirmados como Hamiltoniano conectados, contribuindo para a compreensão das propriedades dos gráficos.
O matroid regular R_{10} apresenta um contraexemplo, fornecendo insights sobre as complexidades das estruturas de gráficos base-cobase.

Abstract

Há um grande interesse em entender quais propriedades dos gráficos base de matroides se estendem aos gráficos base-cobase de matroides. Um resultado significativo de Naddef e Pulleyblank (1984) mostra que o 1-esqueleto de qualquer poliedro (0, 1) é um hipercubo ou é Hamiltoniano-conectado, ou seja, existe um caminho Hamiltoniano conectando quaisquer dois vértices. Em particular, isso é verdadeiro para os gráficos base de matroides. Uma questão natural levantada por Farber, Richter e Shank (1985) é se isso se estende aos gráficos base-cobase. Primeiro, usamos a abordagem poliedral para mostrar a conectividade Hamiltoniana dos gráficos base-cobase das extensões série-paralela dos matroides de caminho de rede. Por outro lado, mostramos que esse método se estende apenas a classes muito especiais relacionadas a matroides idênticos auto-duais. Segundo, mostramos que os gráficos base-cobase de rodas e redemoinhos são Hamiltoniano conectados. Por último, mostramos que o matroid regular R₁₀ apresenta uma resposta negativa à questão de Farber, Richter e Shank.

Conectividade hamiltoniana de alguns gráficos base-cobase

Key Points

Abstract

Cite This Study

Also Consider

Also Consider