Displaying similar documents to “On the simplex graph operator”

Some news about oblique graphs

Andrey A. Dobrynin, Leonid S. Melnikov, Jens Schreyer, Hansjoachim Walther (2002)

Discussiones Mathematicae Graph Theory

Similarity:

A k-gon α of a polyhedral graph G(V,E,F) is of type ⟨b₁,b₂,...,bₖ⟩ if the vertices incident with α in cyclic order have degrees b₁,b₂,...,bₖ and ⟨b₁,b₂,...,bₖ⟩ is the lexicographic minimum of all such sequences available for α. A polyhedral graph G is oblique if it has no two faces of the same type. Among others it is shown that an oblique graph contains vertices of degree 3.

Recognizing Chordal Graphs: Lex BFS and MCS 1

Broderick Arneson, Piotr Rudnicki (2006)

Formalized Mathematics

Similarity:

We are formalizing the algorithm for recognizing chordal graphs by lexicographic breadth-first search as presented in [13, Section 3 of Chapter 4, pp. 81-84]. Then we follow with a formalization of another algorithm serving the same end but based on maximum cardinality search as presented by Tarjan and Yannakakis [25].This work is a part of the MSc work of the first author under supervision of the second author. We would like to thank one of the anonymous reviewers for very useful suggestions. ...

Simplicial and nonsimplicial complete subgraphs

Terry A. McKee (2011)

Discussiones Mathematicae Graph Theory

Similarity:

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...

The edge C₄ graph of some graph classes

Manju K. Menon, A. Vijayakumar (2010)

Discussiones Mathematicae Graph Theory

Similarity:

The edge C₄ graph of a graph G, E₄(G) is a graph whose vertices are the edges of G and two vertices in E₄(G) are adjacent if the corresponding edges in G are either incident or are opposite edges of some C₄. In this paper, we show that there exist infinitely many pairs of non isomorphic graphs whose edge C₄ graphs are isomorphic. We study the relationship between the diameter, radius and domination number of G and those of E₄(G). It is shown that for any graph G without isolated vertices,...