Distance three labelings of trees

DOI10.1016/j.dam.2011.02.004zbMath1241.05123OpenAlexW2099793997MaRDI QIDQ415278

Petr A. Golovach, Bernard Lidický, Jiří Fiala, 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) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Related Items

Characterization results for the \(L(2, 1, 1)\)-labeling problem on trees, Optimal \(L(\delta_1,\delta_2,1)\)-labeling of eight-regular grids, Unnamed Item, Unnamed Item, Distance-constrained labellings of Cartesian products of graphs, Linear and cyclic distance-three labellings of trees

Cites Work

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