Abstract | ||
---|---|---|
An L(2,1)-labeling of a graph G=(V,E) is a function f:V(G)-{0,1,2,...} such that |f(u)-f(v)|=2 whenever uv@?E(G) and |f(u)-f(v)|=1 whenever u and v are at distance two apart. The span of an L(2,1)-labeling f of G, denoted as SP"2(f,G), is the maximum value of f(x) over all x@?V(G). The L(2,1)-labeling number of a graph G, denoted as @l(G), is the least integer k such that G admits an L(2,1)-labeling of span k. The problem of computing @l(G) of a graph is known to be NP-complete. Griggs and Yeh have conjectured that @l(G)= |
Year | DOI | Venue |
---|---|---|
2012 | 10.1016/j.ipl.2012.04.003 | Inf. Process. Lett. |
Keywords | Field | DocType |
maximum value,graph g,orderable graph,dually chordal graph,integer k,span k,approximation algorithms | Discrete mathematics,Indifference graph,Combinatorics,Interval graph,Bipartite graph,Clique-sum,Chordal graph,Degree (graph theory),Treewidth,Pathwidth,Mathematics | Journal |
Volume | Issue | ISSN |
112 | 13 | 0020-0190 |
Citations | PageRank | References |
3 | 0.41 | 17 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
B. S. Panda | 1 | 99 | 21.18 |
Preeti Goel | 2 | 10 | 1.54 |