Displaying similar documents to “Independence complexes and edge covering complexes via Alexander duality.”

On 3-simplicial vertices in planar graphs

Endre Boros, Robert E. Jamison, Renu Laskar, Henry Martyn Mulder (2004)

Discussiones Mathematicae Graph Theory

Similarity:

A vertex v in a graph G = (V,E) is k-simplicial if the neighborhood N(v) of v can be vertex-covered by k or fewer complete graphs. The main result of the paper states that a planar graph of order at least four has at least four 3-simplicial vertices of degree at most five. This result is a strengthening of the classical corollary of Euler's Formula that a planar graph of order at least four contains at least four vertices of degree at most five.

On the simplex graph operator

Bohdan Zelinka (1998)

Discussiones Mathematicae Graph Theory

Similarity:

A simplex of a graph G is a subgraph of G which is a complete graph. The simplex graph Simp(G) of G is the graph whose vertex set is the set of all simplices of G and in which two vertices are adjacent if and only if they have a non-empty intersection. The simplex graph operator is the operator which to every graph G assigns its simplex graph Simp(G). The paper studies graphs which are fixed in this operator and gives a partial answer to a problem suggested by E. Prisner.