Distance two surjective labelling of paths and interval graphs
Summary: Graph labelling problem has been broadly studied for a long period for its applications, especially in frequency assignment in (mobile) communication system, \(X\)-ray crystallography, circuit design, etc. Nowadays, surjective \(L(2,1)\)-labelling is a well-studied problem. Motivated from the \(L(2,1)\)-labelling problem and the importance of surjective \(L(2,1)\)-labelling problem, we consider surjective \(L(2,1)\)-labelling (\(\mathrm{SL}21\))-labelling) problems for paths and interval graphs. For any graph \(G=(V,E)\), an \(\mathrm{SL}21\)-labelling is a mapping \(\varphi:V\longrightarrow\{1,2, \dots,n\}\) so that, for every pair of nodes \(u\) and \(v\), if \(d(u,v)=1\), then \(|\varphi (u)-\varphi (v)|\geq2\); and if \(d(u,v)=2\), then \(|\varphi(u)-\varphi (v)|\geq1\), and every label \(1,2,\dots,n\) is used exactly once, where \(d(u,v)\) represents the distance between the nodes \(u\) and \(v\), and \(n\) is the number of nodes of graph \(G\). In the present article, it is proved that any path \(P_n\) can be surjectively \(L(2,1)\)-labelled if \(n\geq4\), and it is also proved that any interval graph (IG) \(G\) having \(n\) nodes and degree \(\Delta>2\) can be surjectively \(L(2,1)\)-labelled if \(n=3\Delta-1\). Also, we have designed two efficient algorithms for surjective \(L(2,1)\)-labelling of paths and interval graphs. The results regarding both paths and interval graphs are the first result for surjective \(L(2,1)\)-labelling.
- L(0,1)-labelling of permutation graphs
- \(L(2, 1)\)-labeling of permutation and bipartite permutation graphs
- L(2,1)-labeling of interval graphs
- \(L(3, 2, 1)\)- and \(L(4, 3, 2, 1)\)-labeling problems on interval graphs
- L(3,2,1)-labeling of graphs
- A bound on the chromatic number of the square of a planar graph
- A mathematical approach on representation of competitions: competition cluster hypergraphs
- A Theorem about the Channel Assignment Problem
- Approximations for -Colorings of Graphs
- Coloring the square of a planar graph
- Computation of certain topological coindices of graphene sheet and \(C_4C_8(S)\) nanotubes and nanotorus
- Degree sequence of graph operator for some standard graphs
- scientific article; zbMATH DE number 1185300 (Why is no real title available?)
- Labelling Graphs with a Condition at Distance 2
- On classes of infinite loaded graphs with randomly deleted edges
- On graphs with equal dominating and c-dominating energy
- On the L(h, k)‐labeling of co‐comparability graphs and circular‐arc graphs
- On the \(L(p,1)\)-labelling of graphs
- The $L(2,1)$-Labeling Problem on Graphs
- The L(3,2,1)-labeling problem on graphs
This page was built for publication: Distance two surjective labelling of paths and interval graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2045355)
