Distance three labelings of trees

DOI10.1016/J.DAM.2011.02.004MaRDI QIDQ415278zbMATH OpenOpenAlexFDO

Authors Jiří Fiala, Petr A. Golovach, Bernard Lidický, Daniël Paulusma, Jan Kratochvíl

Publication date 11 May 2012

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2011.02.004

zbMATH Keywords

circular distancedistance constrained graph labelinglinear distance

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Network design and communication in computer systems (68M10)

Recommendations

• \(L(2,1,1)\)-labeling is NP-complete for trees
• Characterization results for the \(L(2, 1, 1)\)-labeling problem on trees
• Linear and cyclic distance-three labellings of trees
• scientific article; zbMATH DE number 7295442
• The \(L(h,1,1)\)-labelling problem for trees

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2044507 (Why is no real title available?)
• scientific article; zbMATH DE number 2197889 (Why is no real title available?)
• A Linear Time Algorithm for L(2,1)-Labeling of Trees
• A coloring problem on the \(n\)-cube
• A distance-labelling problem for hypercubes
• A survey on labeling graphs with a condition at distance two
• Algorithms for Square Roots of Graphs
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• An O\((n^{1.75})\) algorithm for \(L(2,1)\)-labeling of trees
• An exact algorithm for the channel assignment problem
• Automata, Languages and Programming
• Computational Complexity of the Distance Constrained Labeling Problem for Trees (Extended Abstract)
• Exact algorithms for \(L(2,1)\)-labeling of graphs
• Fixed-parameter complexity of \(\lambda\)-labelings
• Graph labellings with variable weights, a survey
• Graph-Theoretic Concepts in Computer Science
• New bounds on a hypercube coloring problem.
• On \(L(d,1)\)-labelings of graphs
• On a hypercube coloring problem
• On improved exact algorithms for \(L(2,1)\)-labeling of graphs
• Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover
• Partial covers of graphs
• Systems of pairs of \(q\)-distant representatives, and graph colorings
• The $L(2,1)$-Labeling Problem on Graphs
• The \(L(h,1,1)\)-labelling problem for trees
• The complexity of satisfiability problems
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Tree Powers
• \(L(2,1,1)\)-labeling is NP-complete for trees
• \(L(h,1,1)\)-labeling of outerplanar graphs

Cited in

(13)

• Distance-constrained labellings of Cartesian products of graphs
• The multi-level distance labeling for lobster tree
• Linear and cyclic distance-three labellings of trees
• \(L(2,1,1)\)-labeling is NP-complete for trees
• Characterization results for the \(L(2, 1, 1)\)-labeling problem on trees
• scientific article; zbMATH DE number 7688018 (Why is no real title available?)
• Graph-Theoretic Concepts in Computer Science
• Optimal \(L(\delta_1,\delta_2,1)\)-labeling of eight-regular grids
• Automata, Languages and Programming
• Labeling trees with a condition at distance two
• Distance-constrained labeling of complete trees
• Distance Constrained Labelings of Trees
• scientific article; zbMATH DE number 7651161 (Why is no real title available?)

This page was built for publication: Distance three labelings of trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q415278)