Top

Journal of Applied Mathematics and Computing

Published in:

01-10-2015 | Original Research

L(2,1)-labeling of interval graphs

Authors: Satyabrata Paul, Madhumangal Pal, Anita Pal

Published in: Journal of Applied Mathematics and Computing | Issue 1-2/2015

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

An \(L(2,1)\)-labeling of a graph \(G=(V,E)\) is a function \(f\) from the vertex set \(V(G)\) to the set of non-negative integers such that adjacent vertices get numbers at least two apart, and vertices at distance two get distinct numbers. The \(L(2,1)\)-labeling number denoted by \(\lambda _{2,1}(G)\) of \(G\) is the minimum range of labels over all such labeling. In this article, it is shown that, for an interval graph \(G\), the upper bound of \(\lambda _{2,1}(G)\) is \(\Delta +\omega \), where \(\Delta \) and \(\omega \) represents the maximum degree of the vertices and size of maximum clique respectively. An \(O(m+n)\) time algorithm is also designed to \(L(2,1)\)-label a connected interval graph, where \(m\) and \(n\) represent the number of edges and vertices respectively. Extending this idea it is shown that \(\lambda _{2,1}(G)\le \Delta +3\omega \) for circular-arc graph.

previous article Algebraic cryptanalysis of stream ciphers using decomposition of Boolean function

next article The Gray images of constacyclic codes over

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Araki, T.: Labeling bipartite permutation graphs with a condition at distance two. Discret. Appl. Math. 157, 1677–1686 (2009)MATHMathSciNetCrossRef

Barmana, S.C., Pal, M., Mondal, S.: The k-neighbourhood-covering problem on interval graphs. Int. J. Comput. Math. 87(9), 1918–1935 (2010)MathSciNetCrossRef

Bera, D., Pal, M., Pal, T.K.: A parallel algorithm for computing all hinge vertices on interval graphs. Korean J. Comput. Appl. Math. 8(2), 295–309 (2001)MATHMathSciNet

Bertossi, A.A., Pinotti, C.M., Tan, R.B.: Efficient use of radio spectrum in wireless networks with channel separation between close stations. In: DIALM 2000 Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pp. 18–27

Bertossi, A.A., Pinotti, C.M.: Approximate L(\(\delta _1, \delta _2, \ldots, \delta _t)\)-coloring of trees and interval graphs. Networks 49(3), 204–216 (2007)MATHMathSciNetCrossRef

Bonomo, F., Cerioli, M.R.: On the \(L(2,1)\)-labelling of block graphs. Int. J. Comput. Math. 88(3), 468–475 (2011)MATHMathSciNetCrossRef

Bodlaender, H.L., Kloks, T., Tan, R.B., Leeuwen, J.V.: Approximations for \(\lambda \)-colorings of graphs. Comput. J. 47(2), 193–204 (2004)MATHCrossRef

Calamoneri, T., Caminiti, S., Olariu, S., Petreschi, R.: On the \(L(h, k)\)-labeling of co-comparability graphs and circular-arc graphs. Networks 53(1), 27–34 (2009)MATHMathSciNetCrossRef

Calamoneri, T., Petreschi, R.: \(L(h,1)\)-labeling subclasses of planar graphs. J. Parallel Distrib. Comput. 64(3), 414–426 (2004)MATHCrossRef

10.

Calamoneri, T.: The \(L(h, k)\)-labelling problem: an updated survey and annotated bibliography. Comput. J. 54(8), 1344–1371 (2011)CrossRef

11.

Calamoneri, T.: Optimal \(L(h, k)\)-labeling of regular grids. Discret. Math. Theor. Comput. Sci. 8, 141–158 (2006)MATHMathSciNet

12.

Cerioli, M.R., Posner, D.F.D.: On \(L(2,1)\)-coloring split, chordal bipartite, and weakly chordal graphs. Discret. Appl. Math. 160, 2655–2661 (2012)MATHMathSciNetCrossRef

13.

Chang, G.J., Kuo, D.: The \(L(2,1)\)-labeling on graphs. SIAM J. Discret. Math. 9, 309–316 (1996)MATHMathSciNetCrossRef

14.

Frieder, O., Harary, F., Wan, P.J.: A radio coloring of a hypercube. Int. J. Comput. Math. 79(6), 665–670 (2002)MATHMathSciNetCrossRef

15.

Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, 2nd edn. Elsevier, Amsterdam (2004)MATH

16.

Gonçalves, D.: On the \(L(d,1)\)-labellinng of graphs. Discret. Math. 308, 1405–1414 (2008)MATHCrossRef

17.

Griggs, J., Yeh, R.K.: Labeling graphs with a condition at distance two. SIAM J. Discret. Math. 5, 586–595 (1992)MATHMathSciNetCrossRef

18.

Hasunuma, T., Ishii, T., Ono, H., Uno, Y.: A linear time algorithm for \(L(2,1)\)-labeling of trees. Lect. Notes Comput. Sci. 5757, 35–46 (2009)MathSciNetCrossRef

19.

Havet, F., Reed, B., Sereni, J.S.: \(L(2,1)\)-labeling of graphs, In: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, SIAM 621–630 (2008)

20.

Hale, W.K.: Frequency assignment: theory and applications. Proc. IEEE 68, 1497–1514 (1980)CrossRef

21.

Huang, Y.Z., Chiang, C.Y., Huang, L.H., Yeh, H.G.: On \(L(2,1)\)-labelling of generalized petersen graph. J. Comb. Optim 24, 266–279 (2012)MATHMathSciNetCrossRef

22.

Khan, N., Pal, A., Pal, M.: Edge colouring of cactus graphs. Adv. Model. Optim. 11(4), 407–421 (2009)MATHMathSciNet

23.

Khan, N., Pal, M., Pal, A.: (2,1)-total labelling of cactus graphs. J. Inf. Comput. Sci. 5(4), 243–260 (2010)

24.

Khan, N., Pal, M., Pal, A.: L(0, 1)-Labelling of cactus graphs. Commun. Netw. 4, 18–29 (2012)CrossRef

25.

Khan, N., Pal, A., Pal, M.: \(L(2,1)\)-labelling of cactus graphs. Mapana J. Sci. 11(4), 15–42 (2012)MathSciNet

26.

Kim, B.M., Song, B.C., Rho, Y.: \(L(2,1)\)-labellings for direct products of a triangle and a cycle. Int. J. Comput. Math. 90(3), 475–482 (2013)MATHMathSciNetCrossRef

27.

Kim, B.M., Song, B.C., Hwang, W.: Distance three labellings for \(K_n \times K_2\). Int. J. Comput. Math. 90(5), 906–911 (2013)MATHMathSciNetCrossRef

28.

Král’, D., S̆krekovski, R.: A theory about channel assignment problem. SIAM J. Discret. Math. 16, 426–437 (2003)MATHCrossRef

29.

Mandal, S., Pal, M.: Maximum weight independent set of circular-arc graph and its application. J. Appl. Math. Comput. 22(3 extra), 161–174 (2006)MATHMathSciNetCrossRef

30.

Mandal, S., Pal, A., Pal, M.: An optimal algorithm to find centres and diameter of a circular-arc graph. Adv. Model. Optim. 9(1), 155–170 (2007)MATHMathSciNet

31.

Mondal, S., Pal, M., Pal, T.K.: An optimal algorithm to solve 2-neighbourhood covering problem on interval graphs. Int. J. Comput. Math. 79(2), 189–204 (2002)MATHMathSciNetCrossRef

32.

Olariu, S.: An optimal greedy heuristic to color interval graphs. Inf. Process. Lett. 37, 21–25 (1991)MATHMathSciNetCrossRef

33.

Panda, B.S., Goel, P.: \(L(2,1)\)-labeling of dually chordal graphs and strongly orderable graphs. Inf. Process. Lett. 112, 552–556 (2012)MATHMathSciNetCrossRef

34.

Paul, S., Pal, M., Pal, A.: \(L(2,1)\)-labeling of permutation and bipartite permutation graphs. Math. Comput. Sci. doi:10.1007/s11786-014-0180-2

35.

Paul, S., Pal, M., Pal, A.: An efficient algorithm to solve \(L(0,1)\)-labelling problem on interval graphs. Adv. Model. Optim. 15(1), 31–43 (2013)

36.

Pal, M.: Some sequential and parallel algorithms on interval graphs. Ph.D Thesis, Indian Institute of Technology, Kharagpur, India (1995)

37.

Pal, M., Bhattacharjee, G.P.: A data structure on interval graphs and its applications. J. Circuits Syst. Comput. 7, 165–175 (1997)MathSciNetCrossRef

38.

Pal, M., Bhattacharjee, G.P.: Optimal sequential and parallel algorithms for computing the diameter and the center of an interval graph. Int. J. Comput. Math. 59, 1–13 (1995)MATHCrossRef

39.

Pal, M., Bhattacharjee, G.P.: An optimal parallel algorithm for computing all maximal cliques of an interval graph and its applications. J. Inst. Eng. (India) 76, 29–33 (1995)

40.

Pal, M., Bhattacharjee, G.P.: A sequential algorithm for finding a maximum weight k-independent set on interval graphs. Int. J. Comput. Math. 60, 205–214 (1996)MATHCrossRef

41.

Pal, M., Bhattacharjee, G.P.: An optimal parallel algorithm to color an interval graph. Parallel Process. Lett. 6, 439–449 (1996)MathSciNetCrossRef

42.

Pal, M., Bhattacharjee, G.P.: An optimal parallel algorithm for all-pairs shortest paths on interval graphs. Nord. J. Comput. 4, 342–356 (1997)MATHMathSciNet

43.

Pal, M., Mondal, S., Bera, D., Pal, T.K.: An optimal parallel algorithm for computing cut vertices and blocks on interval graphs. Int. J. Comput. Math. 75(1), 59–70 (2000)MATHMathSciNetCrossRef

44.

Pal, M.: Intersection graph: an introduction. Ann. Pure Appl. Math. 4(1), 43–91 (2013)

45.

Rana, A., Pal, A., Pal, M.: The conditional covering problem on unweighted interval graphs with nonuniform coverage radius. Math. Comput. Sci. 6, 33–41 (2012)MATHMathSciNetCrossRef

46.

Saha, A., Pal, M.: An algorithm to find a minimum feedback vertex set of an interval graph. Adv. Model. Optim. 7(1), 99–116 (2005)MATHMathSciNet

47.

Saha, A., Pal, M., Pal, T.K.: An optimal parallel algorithm to find 3-tree spanner of interval graph. Int. J. Comput. Math. 82(3), 259–274 (2005)MATHMathSciNetCrossRef

48.

Saha, A., Pal, M., Pal, T.K.: An optimal parallel algorithm to find all-pairs shortest paths on circular-arc graphs. J. Appl. Math. Comput. 17(1–2), 1–23 (2005)MATHMathSciNetCrossRef

49.

Saha, A., Pal, M., Pal, T.K.: Selection of programme slots of television channels for giving advertisement: a graph theoretic approach. Inf. Sci. 177(12), 2480–2492 (2007)MATHMathSciNetCrossRef

50.

Sakai, D.: Labeling chordal graphs with a condition at distance two. SIAM J. Discret. Math. 7, 133–140 (1994)MATHCrossRef

51.

Yeh, R.K.: A survey on labeling graphs with a condition at distance two. Discret. Math. 306, 1217–1231 (2006)MATHCrossRef

Title: L(2,1)-labeling of interval graphs
Authors: Satyabrata Paul
Madhumangal Pal
Anita Pal
Publication date: 01-10-2015
Publisher: Springer Berlin Heidelberg
Published in: Journal of Applied Mathematics and Computing / Issue 1-2/2015
Print ISSN: 1598-5865
Electronic ISSN: 1865-2085
DOI: https://doi.org/10.1007/s12190-014-0846-6

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1-2/2015

Asymptotic behavior of a non-autonomous predator-prey model with Hassell–Varley type functional response and random perturbation

A modified Hestenes–Stiefel projection method for constrained nonlinear equations and its linear convergence rate

Dynamics of periodic switched systems describing a single population system with impulses and hibernation

Solvability and dependence on a parameter of a fourth-order periodic boundary value problem

Positive solutions for singular higher-order fractional differential equations with nonlocal conditions

The Gray images of constacyclic codes over

Premium Partner