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:
André Raspaud, Ondrej Sýkora, Imrich Vrt'o (1995)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Abbas, N., Culberson, J., Stewart, L. (2005)
Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]
Similarity:
Cheston, Grant A., Jap, Tjoen Seng (2006)
Journal of Graph Algorithms and Applications
Similarity:
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...
Francesco Regonati, N. Zagaglia Salvi (1994)
Czechoslovak Mathematical Journal
Similarity:
Dominique Barth, François Pellegrini, André Raspaud, Jean Roman (1995)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
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 -free for any finite graph . 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.
Gutman, Ivan (1983)
Publications de l'Institut Mathématique. Nouvelle Série
Similarity: