Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: hereditary clique-Helly graph

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Simplicial and nonsimplicial complete subgraphs

100%

McKee T.

Discussiones Mathematicae Graph Theory

2011

tom 31

nr 3

577-586

Define a complete subgraph Q to be simplicial in a graph G when Q is contained in exactly one maximal complete subgraph ('maxclique') of G; otherwise, Q is nonsimplicial. Several graph classes-including strong p-Helly graphs and strongly chordal graphs-are shown to have pairs of peculiarly related new characterizations: (i) for every k ≤ 2, a certain property holds for the complete subgraphs that are in k or more maxcliques of G, and (ii) in every induced subgraph H of G, that same property holds for the nonsimplicial complete subgraphs of H. One example: G is shown to be hereditary clique-Helly if and only if, for every k ≤ 2, every triangle whose edges are each in k or more maxcliques is itself in k or more maxcliques; equivalently, in every induced subgraph H of G, if each edge of a triangle is nonsimplicial in H, then the triangle itself is nonsimplicial in H.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 McKee T.

1 2011

Wyniki wyszukiwania

Simplicial and nonsimplicial complete subgraphs