Limitando o número de arestas entre gráficos de estrelas, de modo que o gráfico seja plano

9

Eu tenho um gráfico que consiste apenas em gráficos em estrela. Um gráfico em estrela consiste em um nó central com arestas em todos os outros nós. Vamos ser diferentes gráficos estrela de tamanhos diferentes que estão presentes em . Chamamos o conjunto de todos os nós que são centros em qualquer gráfico estrela .H 1 , H 2 , , H n G RGH1,H2,,HnGR

Suponhamos agora que estes gráficos estrela está construindo bordas para outros gráficos estrela de tal forma que nenhuma aresta é incidente entre os nós em . Então, quantas arestas existem no máximo entre os nós em e os nós que não estão em , se o gráfico permanecer plano?R RRRR

Quero o limite superior do número dessas arestas. Um limite superior que tenho em mente é: considerá-los como grafo planar bipartido, onde é um conjunto de vértices e descanso dos vértices formam outro conjunto . Estamos interessados ​​em arestas entre esses conjuntos ( e ). Uma vez que é bipartido planar, o número de tais arestas é delimitada por duas vezes o número de nós em .A R A GRARAG

O que eu sinto é que há uma melhor obrigado, talvez duas vezes os nós mais o número de nós em .RAR

Caso você possa refutar minha intuição, isso também seria bom. Esperamos que alguns de vocês possam apresentar um bom vínculo, juntamente com alguns argumentos relevantes.

singhsumit
fonte
11
Deixe-me reafirmar o problema de maneira diferente: dado um gráfico bipartido planar, digamos H, queremos decompô-lo em subconjuntos, onde cada subconjunto corresponde ao gráfico de estrelas em G (decomposição disjunta em nó, digamos 'x' estrelas diferentes (supondo que ele exista)). então, qual é o limite mais restrito no número de arestas no gráfico bipartido planar H (o 'x' pode desempenhar algum papel nele ??).
precisa
6
cstheory.stackexchange.com/questions/5412/… pode ser relevante.
David Eppstein
quase parece uma duplicata da pergunta acima, mas não tenho certeza.
Suresh Venkat
A reformulação não esclarece completamente: se você possui um gráfico bipartido, particiona as bordas em estrelas, duplicando nós ou particionando, perdendo as bordas. Por exemplo, um quadrado fornece 2 estrelas de 3 nós ou 3 e 1 nó. Nos dois casos, porém, parece que a análise e o exemplo de @ David ( cstheory.stackexchange.com/questions/5412 ) respondem à sua pergunta.
Jack

Respostas:

2

Sua declaração é um pouco ambígua: primeiro você escreve que "... de tal forma que nenhuma aresta é incidente entre os nós em ", mas o próximo parágrafo implica que também não existem arestas entre vértices em . Também assumirei que as estrelas são disjuntas e que você conta todas as arestas (incluindo aquelas inicialmente presentes nas estrelas). Suponhamos também que haja pelo menos duas estrelas e pelo menos uma delas tenha grau .A 2RA2

Nesse caso, você não pode vencer o limite ( = número de todos os vértices). Considere um cenário um pouco diferente: comece com qualquer conjunto de vértices, alguns vermelhos e outros pretos, pelo menos dois de cada tipo. Em cada etapa, adicione arbitrariamente uma aresta entre um vértice vermelho e um preto, desde que não crie interseções ou arestas duplicadas. Eu afirmo que, quando você fica preso, todos os ciclos têm duração .N N 42N4NN4

Seu cenário é um caso especial desse processo em que você começa criando estrelas e depois adicionando as arestas restantes. Se todos os ciclos tiverem comprimento , o limite segue. De maneira mais geral, mostra que, independentemente do gráfico bipartido de onde você começa, você sempre pode concluí-lo em um gráfico quadrilátero (uma palavra que eu inventei).2 N - 442N4

Agora, vamos mostrar a reivindicação. Nesse processo, todos os caminhos terão vértices pretos e vermelhos alternados e cada ciclo terá duração de pelo menos . Se o gráfico não estiver conectado, você poderá conectar qualquer vértice vermelho na face externa de um componente com um vértice preto na outra face de outro componente. Portanto, podemos assumir que o gráfico já está conectado.4

Suponha que você tenha uma face de comprimento ou mais. deve ter pelo menos três vértices pretos (alguns possivelmente iguais). Se algum vértice é repetida em , tomar duas aparições no sentido horário consecutivos de , digamos . deve conter um vértice preto , portanto, dependendo da localização de , podemos conectar ou a dentro de sem duplicar as arestas. Se nenhum vértice for repetido, escolha uma seção no sentido horário de6 F x F x x - a - . . . - x - b . . . F z x z a b z F x - a - y - b - z F x , y , z a , b x b a z ( x , b ) ( a , z )F6FxFxxa...xb...FzxzabzFxaybzF, onde são pretos e são vermelhos. Se está ligado a , em seguida, não pode ser ligado a (por planaridade), de modo que pode adicionar um dos bordos , dentro .x,y,za,bxbaz(x,b)(a,z)F

Marek Chrobak
fonte
obrigado por responder. algumas pessoas postaram algum link relevante para um problema semelhante e agora tenho a resposta.
singhsumit 16/09/11