A survey on labeling graphs with a condition at distance two
From MaRDI portal
Publication:2497501
If \(k\), \(d_{1}\), \(d_{2}\) are positive integers, a \(k\)-\(L\left(d_{1}, d_{2}\right)\) labeling of a graph \(G\) is a function mapping the vertices to \(\{0,1,\dots,k\}\) in such a way that the distance between the labels of \(u\) and \(v\) is \(\geq d_{i}\) whenever \(d_{G}(u,v)=i\) for \(i=1,2\). The \(L\left(d_{1}, d_{2}\right)\)-number of \(G\) is the smallest \(k\) such that there exists such a labeling. The study of these labelings was motivated by radio-frequency assignment problems. This paper surveys all important results in the area, most of which consist of calculating (bounds on) the \(L\left(d_{1}, d_{2}\right)\) number for various families of graphs. No proofs are included, so it is a necessary but not sufficient resource for beginners in the area. For experts it will serve as an essential summary of the state of the art.
Recommendations
Cites work
- \(L(h,1)\)-labeling subclasses of planar graphs
- A Theorem about the Channel Assignment Problem
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Colouring weighted bipartite graphs with a co-site constraint
- Computing graph invariants on rotagraphs using dynamic algorithm approach: The case of (2, 1)-colorings and independence numbers
- Distance-two labelings of graphs
- Graph distance‐dependent labeling related to code assignment in computer networks
- Graph labeling and radio channel assignment
- Graph theory
- Hamiltonicity and circular distance two labellings
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 1185300 (Why is no real title available?)
- scientific article; zbMATH DE number 3652373 (Why is no real title available?)
- scientific article; zbMATH DE number 3509316 (Why is no real title available?)
- scientific article; zbMATH DE number 1500531 (Why is no real title available?)
- scientific article; zbMATH DE number 1792593 (Why is no real title available?)
- scientific article; zbMATH DE number 841588 (Why is no real title available?)
- scientific article; zbMATH DE number 881282 (Why is no real title available?)
- scientific article; zbMATH DE number 1409224 (Why is no real title available?)
- scientific article; zbMATH DE number 1420920 (Why is no real title available?)
- scientific article; zbMATH DE number 1439442 (Why is no real title available?)
- scientific article; zbMATH DE number 2197889 (Why is no real title available?)
- scientific article; zbMATH DE number 2197903 (Why is no real title available?)
- Labeling Chordal Graphs: Distance Two Condition
- Labeling Planar Graphs with Conditions on Girth and Distance Two
- Labeling products of complete graphs with a condition at distance two
- Labeling trees with a condition at distance two
- Labeling trees with a condition at distance two.
- Labelling Graphs with a Condition at Distance 2
- Labelling graphs with the circular difference
- No-hole \(L(2,1)\)-colorings
- On L(2,1)-labelings of Cartesian products of paths and cycles
- On \(L(d,1)\)-labelings of graphs
- On generalized Petersen graphs labeled with a condition at distance two
- On labeling the vertices of products of complete graphs with distance constraints
- On powers of chordal graphs and their colorings
- On Regular Graphs Optimally Labeled with a Condition at Distance Two
- On the $\lambda$-Number of $Q_n $ and Related Graphs
- Optimal L(2,1)-labeling of Cartesian products of cycles, with an application to independent domination
- Optimal L(2, 1)-labeling of strong products of cycles [transmitter frequency assignment]
- Relating path coverings to vertex labellings with a condition at distance two
- The $L(2,1)$-Labeling Problem on Graphs
- The edge span of distance two labellings of graphs
- The L(2,1)-labeling and operations of graphs
Cited in
(only showing first 100 items - show all)- Coloring the square of the Kneser graph \(\mathrm{KG}(2k+1,k)\) and the Schrijver graph \(\mathrm{SG}(2k+2,k)\)
- L(h,1,1)-labeling of outerplanar graphs
- L(h,k)-labelings of Hamming graphs
- The complexity of the L(p,q)-labeling problem for bipartite planar graphs of small degree
- Labeling bipartite permutation graphs with a condition at distance two
- Combinatorial optimization in system configuration design
- On \((d,1)\)-total numbers of graphs
- \(L(2, 1)\)-labeling of circulant graphs
- Pair \(L(2, 1)\)-labelings of infinite graphs
- \(L(2,1)\)-labeling for subdivisions of cycle dominated graphs
- \(L(j,k)\)-labeling numbers of square of paths
- Channel assignment problem and n-fold t-separated L(j₁,j₂,,j_m)-labeling of graphs
- On \(L(2,1)\)-labeling of generalized Petersen graphs
- Weighted improper colouring
- Group path covering and distance two labeling of graphs
- On the \(L(2,1)\)-labelings of amalgamations of graphs
- Radio number for total graph of paths
- Distance two edge labelings of lattices
- (p,q)-total labeling of complete graphs
- Lambda number for the direct product of some family of graphs
- Multiple L(j,1)-labeling of the triangular lattice
- \(L(2, 1)\)-labeling of permutation and bipartite permutation graphs
- Lambda number of the power graph of a finite group
- On \(L(2 , 1)\)-labelings of oriented graphs
- Deriving bounds on \(L(k_1,k_2)\) labeling of triangular lattice by exploring underlined graph structures
- A note on the \(L (2, 1)\)-labelling problem of \(\mathcal{G} (k, m)\)
- On \(L(2,1)\)-labelings of some products of oriented cycles
- \(L(2,1)\)-colorings and irreducible no-hole colorings of the direct product of graphs
- Optimal radio labellings of block graphs and line graphs of trees
- On \((p, 1)\)-total labelling of NIC-planar graphs
- On a distance-constrained graph labeling to model cooperation
- Anti-\(k\)-labeling of graphs
- On \((s,t)\)-relaxed \(L(2,1)\)-labelings of the triangular lattice
- 2-distance colorings of some direct products of paths and cycles
- \(L(d,1)\)-labelings of the edge-path-replacement by factorization of graphs
- Radio number for the product of a path and a complete graph
- Characterization results for the \(L(2, 1, 1)\)-labeling problem on trees
- The minimum span of \(L(2,1)\)-labelings of certain generalized Petersen graphs
- A linear time algorithm for L(2,1)-labeling of trees
- An extremal problem on non-full colorable graphs
- \(L(j, k)\)-number of direct product of path and cycle
- Further results on the radio number of trees
- Radio number for middle graph of paths
- Labeling matched sums with a condition at distance two
- Circular \(L(j,k)\)-labeling number of direct product of path and cycle
- On \((s,t)\)-relaxed \(L(2,1)\)-labelings of the square lattice
- \(L(2,1)\)-labeling of oriented planar graphs
- Path covering number and \(L(2,1)\)-labeling number of graphs
- On the hole index of \(L(2,1)\)-labelings of \(r\)-regular graphs
- L(1, 2)-edge-labelings for lattices
- \( L ( p , q )\)-labelings of subdivisions of graphs
- On the universality and extremality of graphs with a distance constrained colouring
- The lambda number of the power graph of a finite \(p\)-group
- \(L(h, k)\)-labelling for octagonal grid
- An O(n n) algorithm for finding edge span of cacti
- Distance three labellings for \(K _n\times K_2\)
- Optimal L(j,k)-edge-labeling of regular grids
- The \((2,1)\)-total labeling number of outerplanar graphs is at most \(\Delta + 2\)
- Fast exact algorithm for \(L(2,1)\)-labeling of graphs
- L(2,1)-labeling of graphs: known results and open problems
- (2,1)-total labeling of a class of subcubic graphs
- Radio graceful Hamming graphs
- Distance Constrained Labelings of Trees
- An $\mbox{O}(n^{1.75})$ Algorithm for L(2,1)-Labeling of Trees
- scientific article; zbMATH DE number 5763155 (Why is no real title available?)
- L(2,1)-labelings on the modular product of two graphs
- Fast exact algorithm for L(2,1)-labeling of graphs
- L(p,2,1)-labeling of the infinite regular trees
- The (p,q)-total labeling problem for trees
- Exact \(\lambda\)-numbers of generalized Petersen graphs of certain higher-orders and on Möbius strips
- L(2,1)-labelling of generalized prisms
- Distance three labelings of trees
- \(L(2,1)\)-labeling of dually chordal graphs and strongly orderable graphs
- A tight upper bound on the (\(2,1\))-total labeling number of outerplanar graphs
- Hole: An Emerging Character in the Story of Radio k-Coloring Problem
- The game \(L(d,1)\)-labeling problem of graphs
- Randomly colouring graphs (a combinatorial view)
- L(2, 1)-edge-labelings of the edge-path-replacement of a graph
- scientific article; zbMATH DE number 6940804 (Why is no real title available?)
- scientific article; zbMATH DE number 6963895 (Why is no real title available?)
- \(L(2,1)\)-labelings of subdivisions of graphs
- The minimum span of \(L(2,1)\)-labelings of generalized flowers
- scientific article; zbMATH DE number 841588 (Why is no real title available?)
- \(\lambda\)-numbers of several classes of snarks
- \(L(1, 2)\)-labeling numbers on square of cycles
- On \((s,t)\)-relaxed \(L(1,1)\)-labelling of trees
- \(L(1,1)\)-labelling of the direct product of a complete graph and a cycle
- L(2,1)-labeling of interval graphs
- Price of anarchy for graph coloring games with concave payoff
- Radio number for middle graph of dandelion
- More relations between -labeling and Hamiltonian paths with emphasis on line graph of bipartite multigraphs
- L(3,1)-labeling of circulant graphs
- A note on \(L (2, 1)\)-labelling of trees
- L(2,1)-labeling of Kneser graphs and coloring squares of Kneser graphs
- On \((p,1)\)-total labelling of planar graphs
- \(l(3,2,1)\)-labeling for the product of a complete graph and a cycle
- On irreducible no‐hole L(2, 1)‐coloring of trees
- \(L(3,2,1)\)-labeling for cylindrical grid: the Cartesian product of a path and a cycle
- Distance two labeling on the square of a cycle
- Optimal radiocoloring of trees
This page was built for publication: A survey on labeling graphs with a condition at distance two
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2497501)
