Nomeie a classe do gráfico: União separada de uma clique e um conjunto independente

9

Seja  um gráfico que seja a união disjunta de um clique e um conjunto independente, ou seja, G

G=Kn1 1+Kn2¯=Kn1 1+Eun2.

A classe de gráficos de todos esses gráficos é caracterizada pelos subgráficos induzidos proibidos configurados e, portanto, é a interseção de um gráfico de cluster e um gráfico de divisão (ou limite).H={2K2,P3}

Essa classe de gráfico (muito simples) tem um nome? Não consegui encontrar a classe de gráfico no  ISGCI , e os artigos que conheço sobre o tópico (por exemplo, Edição de gráficos simples e Sobre o problema de edição de clique ) não se referem à classe por um nome.

Aqui está uma figura desse gráfico:

gráfico de divisão de cluster

reference-request graph-theory graph-classes Pål GD
fonte
11
Infelizmente, "gráficos de cluster dividido" parece estar em uso para um conceito diferente (gráficos nos quais cada componente conectado é dividido).
David Eppstein 5/05

Respostas:

7

O complemento de borda dos gráficos da sua classe são gráficos divididos completos: eles podem ser particionados em um conjunto independente e em um clique, de modo que todos os vértices do conjunto independente sejam adjacentes a todos os vértices do clique (consulte, por exemplo, http: //www.mathcove.net/petersen/lessons/get-lesson?les=30 ). Portanto, você pode chamar sua classe de gráfico para concluir os gráficos divididos.

Bart Jansen
fonte
Obrigado Bart. Não sai exatamente da língua, mas acho que terá que servir.
Gål GD
E quanto ao gráfico dividido independente ? Ou seria provável que isso fosse confundido com outra coisa?
Gål GD
6

Em um artigo recente, Hüffner, Komusiewicz e Nichterlein se referem a essa classe como gráficos esparsos de divisão . Eles também se referem à classe de complemento, os gráficos de divisão completos, como gráficos de divisão densa .

Hüffner, Komusiewicz e Nichterlein. "Editando gráficos em poucas panelinhas: esquemas de complexidade, aproximação e kernelização".

Pål GD
fonte