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