Displaying similar documents to “Pebbling dynamic graphs in minimal space”

Cutwidth of the de Bruijn graph

André Raspaud, Ondrej Sýkora, Imrich Vrt'o (1995)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

Note: The Smallest Nonevasive Graph Property

Michał Adamaszek (2014)

Discussiones Mathematicae Graph Theory

Similarity:

A property of n-vertex graphs is called evasive if every algorithm testing this property by asking questions of the form “is there an edge between vertices u and v” requires, in the worst case, to ask about all pairs of vertices. Most “natural” graph properties are either evasive or conjectured to be such, and of the few examples of nontrivial nonevasive properties scattered in the literature the smallest one has n = 6. We exhibit a nontrivial, nonevasive property of 5-vertex graphs...

On bandwidth, cutwidth, and quotient graphs

Dominique Barth, François Pellegrini, André Raspaud, Jean Roman (1995)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

Gallai and anti-Gallai graphs of a graph

S. Aparna Lakshmanan, S. B. Rao, A. Vijayakumar (2007)

Mathematica Bohemica

Similarity:

The paper deals with graph operators—the Gallai graphs and the anti-Gallai graphs. We prove the existence of a finite family of forbidden subgraphs for the Gallai graphs and the anti-Gallai graphs to be H -free for any finite graph H . The case of complement reducible graphs—cographs is discussed in detail. Some relations between the chromatic number, the radius and the diameter of a graph and its Gallai and anti-Gallai graphs are also obtained.