Existe-t-il un graphique circulaire sans triangle, sans coupe en étoile, avec plus de n arêtes?

J'essaie de trouver un graphique avec ces propriétés pour mes études, mais malheureusement je ne trouve pas un tel graphique.

Est-ce que quelqu'un sait s'il y a ce graphique, ou pourquoi est-il impossible d'exister?

graph-theory graph-classes Rafael Oliveira Lopes
la source

Pouvez-vous expliquer votre terminologie? Qu'est-ce que "star-cutset free" et qu'est-ce que "circle graph"?

Yuval Filmus

Sûr. =) Un graphe circulaire est un graphe (non orienté) dont les sommets peuvent être associés à des accords dans un cercle de telle sorte que deux sommets sont adjacents si les accords correspondants se croisent. Voici une image à titre d'exemple (de Wikipédia): en.wikipedia.org/wiki/File:Circle_graph.svg Et nous pouvons dire qu'un graphique a un star-cutset lorsque vous avez un sommet v tel que supprimer v et ses voisins (N [v]) du graphique le rend déconnecté.

Rafael Oliveira Lopes

ISGCI a des définitions de graphique sans triangle et cercle . Une étoile liasse est un sous - ensemble

de sommets qui sépare le graphique, de telle sorte qu'un sommet de

est adjacent à tous les autres sommets dans

S

$S$

S

$S$

S

$S$

Jeffε

Ce document peut être pertinent.

Jeffε

Réponses:

$G$ $G$ $G$ $n$

$C$ $G$

$C$

$C$ $v$ $N[v]$

$G$ $v$ $v$ $v$ $G$

Serge Gaspers
la source

n

$n$

n

$n$

Ok, comme corrigé je pense que cela fonctionne, et est plus simple que ma preuve.

David Eppstein

$n$ $m$ $m+n+1$ $2n$ $m>n$ $p$ $c$ $p$ $c$ $p$

David Eppstein
la source