Labelling Graphs with a Condition at Distance 2

DOI10.1137/0405048zbMath0767.05080OpenAlexW2148410650MaRDI QIDQ4030197

Publication date: 1 April 1993

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/75e521e85a766384590b767ad9779dfc13201753

zbMATH Keywords

cycle graph coloring NP-completeness Hamilton paths labelling graphs channel assignments labelling numbers

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (only showing first 100 items - show all)

Radio and radial radio numbers of certain sunflower extended graphs ⋮ A new sufficient condition for a tree \(T\) to have the \((2,1)\)-total number \(\Delta +1\) ⋮ Characterization results for the \(L(2, 1, 1)\)-labeling problem on trees ⋮ A new approach on locally checkable problems ⋮ A channel assignment problem for optical networks modelled by Cayley graphs ⋮ Extremal problems on consecutive \(L(2,1)\)-labelling ⋮ The minimum span of \(L(2,1)\)-labelings of certain generalized Petersen graphs ⋮ Optimal channel assignment and \(L(p,1)\)-labeling ⋮ \(L(2, 1)\)-labeling of circulant graphs ⋮ Pair \(L(2, 1)\)-labelings of infinite graphs ⋮ Relating path coverings to vertex labellings with a condition at distance two ⋮ Computing a minimum paired-dominating set in strongly orderable graphs ⋮ The List \(L(2, 1)\)-labeling of planar graphs ⋮ Radio-\(k\)-labeling of cycles for large \(k\) ⋮ The total graph of a hypergraph ⋮ Wegner's conjecture on 2-distance coloring ⋮ Computational complexity of distance edge labeling ⋮ The complexity of \(L(p, q)\)-edge-labelling ⋮ \(L(2,1)\)-labeling for subdivisions of cycle dominated graphs ⋮ New results on radio \(k\)-labelings of distance graphs ⋮ List covering of regular multigraphs ⋮ Facial \(L(2, 1)\)-edge-labelings of trees ⋮ On some \(L(2, 1)\)-coloring parameters of certain graph classes ⋮ \(L(2,1)\)-colorings and irreducible no-hole colorings of the direct product of graphs ⋮ On the \(L\)(2,~1)-labeling conjecture for brick product graphs ⋮ \(L(3, 2, 1)\)- and \(L(4, 3, 2, 1)\)-labeling problems on interval graphs ⋮ Some results on the injective chromatic number of graphs ⋮ On \(L(2,1)\)-labeling of generalized Petersen graphs ⋮ Computing graph invariants on rotagraphs using dynamic algorithm approach: The case of (2, 1)-colorings and independence numbers ⋮ Group path covering and distance two labeling of graphs ⋮ On the complexity of exact algorithm for \(L(2,1)\)-labeling of graphs ⋮ No-hole \(L(2,1)\)-colorings ⋮ On the \(L(2,1)\)-labelings of amalgamations of graphs ⋮ Radio number for total graph of paths ⋮ Greedy \(F\)-colorings of graphs ⋮ Irreducible no-hole \(L(2, 1)\)-coloring of edge-multiplicity-paths-replacement graph ⋮ New results in \(t\)-tone coloring of graphs ⋮ The \(L(2,1)\)-labelling problem for cubic Cayley graphs on dihedral groups ⋮ \(L(p,q)\)-labeling of sparse graphs ⋮ Distance two edge labelings of lattices ⋮ \((p,q)\)-total labeling of complete graphs ⋮ Algorithms for graphs with small octopus ⋮ Improved lower bounds for the radio number of trees ⋮ On \((p, 1)\)-total labelling of some 1-planar graphs ⋮ Distance-constrained labellings of Cartesian products of graphs ⋮ Computing \(L(p, 1)\)-labeling with combined parameters ⋮ Optimal radio labellings of block graphs and line graphs of trees ⋮ Antipodal number of full \(m\)-ary trees ⋮ Infinitely many trees with maximum number of holes zero, one, and two ⋮ On a distance-constrained graph labeling to model cooperation ⋮ \(L(2, 1)\)-labelling of graphs with few \(P_4\)'s ⋮ Channel assignment problem and \(n\)-fold \(t\)-separated \(L(j_1,j_2,\dots,j_m)\)-labeling of graphs ⋮ Nordhaus-Gaddum-type results for path covering and \(L(2,1)\)-labeling numbers ⋮ On \(L(2,1)\)-coloring split, chordal bipartite, and weakly chordal graphs ⋮ On the number of 2-packings in a connected graph ⋮ Systems of distant representatives ⋮ \(L(2,1)\)-labeling of direct product of paths and cycles ⋮ An exact algorithm for the channel assignment problem ⋮ A note on collections of graphs with non-surjective lambda labelings ⋮ Lambda number for the direct product of some family of graphs ⋮ A new graph parameter and a construction of larger graph without increasing radio \(k\)-chromatic number ⋮ On irreducible no-hole \(L(2,1)\)-coloring of subdivision of graphs ⋮ Multiple \(L(j,1)\)-labeling of the triangular lattice ⋮ Generalized list \(T\)-colorings of cycles ⋮ \(L(2, 1)\)-labeling of permutation and bipartite permutation graphs ⋮ The complexity of frugal colouring ⋮ The \(L(2,1)\)-labeling of unigraphs ⋮ Theory of computational complexity. Part 7. Transl. from the Russian ⋮ A note on the chromatic number of the square of Kneser graph \(K(2 k + 1, k)\) ⋮ The \((d, 1)\)-total labelling of Sierpiński-like graphs ⋮ Frequency assignment problem in networks with limited spectrum ⋮ On \(L(h,k)\)-labeling index of inverse graphs associated with finite cyclic groups ⋮ Frequency assignment model of zero divisor graph ⋮ Anti-\(k\)-labeling of graphs ⋮ Lambda number of the power graph of a finite group ⋮ The list \(L(2,1)\)-labeling of planar graphs with large girth ⋮ The \(k\)-distance chromatic number of trees and cycles ⋮ Distance two surjective labelling of paths and interval graphs ⋮ Subexponential algorithms for variants of the homomorphism problem in string graphs ⋮ On \(\text{Ł}(\wp, \wp - 1, \dots, 1)\) labelings of circulant graphs ⋮ Improved bounds on the span of \(L(1,2)\)-edge labeling of some infinite regular grids ⋮ \( L ( 2 , 1 )\)-labeling of disk intersection graphs ⋮ List \(r\)-dynamic coloring of sparse graphs ⋮ On \(L(2 , 1)\)-labelings of oriented graphs ⋮ \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited ⋮ On \(L(2,1)\)-labelings of Cartesian products of paths and cycles ⋮ \(2\)-distance coloring of planar graphs with maximum degree \(5\) ⋮ Radio fuzzy graphs and assignment of frequency in radio stations ⋮ 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)\) ⋮ Optimal frequency assignment and planar list \(L(2, 1)\)-labeling ⋮ Coloring a dominating set without conflicts: \(q\)-subset square coloring ⋮ Distance-constrained labeling of complete trees ⋮ On \((s,t)\)-relaxed \(L(2,1)\)-labelings of the triangular lattice ⋮ 2-distance colorings of some direct products of paths and cycles ⋮ \((2,1)\)-total labeling of trees with large maximum degree ⋮ \(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 ⋮ Distance-two labelings of graphs ⋮ Optimal \(L(3, 2, 1)\)-labeling of triangular lattice

This page was built for publication: Labelling Graphs with a Condition at Distance 2