Essa classe de gráfico tem um nome?

12

É formulado estendendo gráficos de limite . Dado um gráfico de limiar onde C é o clique e eu é o conjunto independente, minha extensão é a seguinte: Cada vértice v Eu posso ser substituído por um novo clique K v, de modo que os vértices de K v tenham a mesmos vizinhos de v .(C,I)CIvIKvKvv

Eu acho que isso deveria ter sido estudado, mas é difícil pesquisar isso em graphclasses.org.

Yixin Cao
fonte
Parece ser um gráfico de interseção de intervalos aninhados ( graphclasses.org/classes/gc_347.html ), mas preciso verificar.
Yixin Cao

Respostas:

15

C4P42P3C4P42K2C4P4) - gráficos gratuitos. Eu não acho que tenha um nome; pelo menos, não parece estar listado em graphclasses.org.

Para verificar se essa é a caracterização correta, considere a representação de gráficos trivialmente perfeitos como os fechamentos transitivos de florestas enraizadas. Uma floresta gera um gráfico de limite (conectado) se, e somente se, tiver um caminho direcionado que contenha todos os nós que não sejam folhas: adicionar um novo vértice isolado corresponde, na floresta, a adicionar uma nova árvore de nó único, que não alterar essa propriedade e adicionar um novo vértice conectado a todos os outros corresponde a adicionar uma nova raiz conectada a todas as raízes de árvores anteriores, o que novamente não altera essa propriedade (a nova raiz pode fazer parte do caminho) .

2P3

2K2P42P3

David Eppstein
fonte
2P3(C4,P4)
2P3