Maxcliques (maximal complete subgraphs) and unit disks (closed neighborhoods of vertices) sometime play almost interchangeable roles in graph theory. For instance, interchanging them makes two existing characterizations of chordal graphs into two new characterizations. More intriguingly, these characterizations of chordal graphs can be naturally strengthened to new characterizations of strongly chordal graphs
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.
An i-chord of a cycle or path is an edge whose endpoints are a distance i ≥ 2 apart along the cycle or path. Motivated by many standard graph classes being describable by the existence of chords, we investigate what happens when i-chords are required for specific values of i. Results include the following: A graph is strongly chordal if and only if, for i ∈ {4,6}, every cycle C with |V(C)| ≥ i has an (i/2)-chord. A graph is a threshold graph if and only if, for i ∈ {4,5}, every path P with |V(P)| ≥ i has an (i -2)-chord.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.