Displaying similar documents to “Methods of destroying the symmetries of a graph.”

Centers in line graphs

Martin Knor, Ľudovít Niepel, Ľubomír Šoltés (1993)

Mathematica Slovaca

Similarity:

On the proper intervalization of colored caterpillar trees

Carme Àlvarez, Maria Serna (2009)

RAIRO - Theoretical Informatics and Applications

Similarity:

This paper studies the computational complexity of the problem (), when the input graph is a colored caterpillar, parameterized by hair length. In order prove our result we establish a close relationship between the and a graph layout problem the (). We show a dichotomy: the and the are NP-complete for colored caterpillars of hair length 2, while both problems are in P for colored caterpillars of hair length 2. For the hardness results we provide a reduction from the , while the...

Bar k -visibility graphs.

Dean, Alice M., Evans, William, Gethner, Ellen, Laison, Joshua D., Safari, Mohammad Ali, Trotter, William T. (2007)

Journal of Graph Algorithms and Applications

Similarity: