An L(2,1)-labeling for a graph G consists of assigning non- negative integers, 0s, to the nodes of G so that adjacent nodes get values at least two apart and nodes at distance two get different values. Minimize s is an NP-complete problem. Here is conjectured that this problem remains NP-complete also for unigraphs, i.e. graphs uniquely de- termined by their own degree sequence up to isomorphism, and a linear time algorithm for L(2,1)-labeling unigraphs is designed.
L(2,1)-labelling of unigraphs / Petreschi, Rossella. - STAMPA. - (2010). (Intervento presentato al convegno SIAM Conference on Discrete Mathematics tenutosi a Austin (Texas/USA) nel Giugno 2010).
L(2,1)-labelling of unigraphs
PETRESCHI, Rossella
2010
Abstract
An L(2,1)-labeling for a graph G consists of assigning non- negative integers, 0s, to the nodes of G so that adjacent nodes get values at least two apart and nodes at distance two get different values. Minimize s is an NP-complete problem. Here is conjectured that this problem remains NP-complete also for unigraphs, i.e. graphs uniquely de- termined by their own degree sequence up to isomorphism, and a linear time algorithm for L(2,1)-labeling unigraphs is designed.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
