On edge irregularity strength of line graph and line cut-vertex graph of comb graph

H. M. Nagesh and V. R. Girish
Notes on Number Theory and Discrete Mathematics
Print ISSN 1310–5132, Online ISSN 2367–8275
Volume 28, 2022, Number 3, Pages 517–524
DOI: 10.7546/nntdm.2022.28.3.517-524
Full paper (PDF, 172 Kb)

Details

Authors and affiliations

H. M. Nagesh
Department of Science & Humanities, PES University
Electronic City Campus, Hosur Road, Bangalore – 560 100, India

V. R. Girish
Department of Science & Humanities, PES University
Electronic City Campus, Hosur Road, Bangalore – 560 100, India

Abstract

For a simple graph G, a vertex labeling \phi:V(G) \rightarrow \{1, 2,\ldots,k\} is called k-labeling. The weight of an edge xy in G, written w_{\phi}(xy), is the sum of the labels of end vertices x and y, i.e., w_{\phi}(xy)=\phi(x)+\phi(y). A vertex k-labeling is defined to be an edge irregular k-labeling of the graph G if for every two different edges e and f, w_{\phi}(e) \neq w_{\phi}(f). The minimum k for which the graph G has an edge irregular k-labeling is called the edge irregularity strength of G, written es(G). In this paper, we find the exact value of edge irregularity strength of line graph of comb graph P_n \bigodot K_1 for n=2,3,4; and determine the bounds for n \geq 5. Also, the edge irregularity strength of line cut-vertex graph of P_n \bigodot K_1 for n=2; and determine the bounds for n \geq 3.

Keywords

  • Irregular assignment
  • Irregularity strength
  • Irregular total k-labeling
  • Edge irregularity strength
  • Comb graph

2020 Mathematics Subject Classification

  • 05C38
  • 05C78

References

  1. Ahmad, A., Ashok, G., & Rinovia, S. (2018). Computing the edge irregularity strengths of chain graphs and the join of two graphs. Electronic Journal of Graph Theory and Applications, 6(1), 201–207.
  2. Ahmad, A., Bača, M., Bashir, Y., & Siddiqui, M. K. (2012). Total edge irregularity strength of strong product of two paths. Ars Combinatoria, 106, 449–459.
  3. Ahmad, A., Bača, M., & Siddiqui, M. K. (2014). On edge irregular total labeling of
    categorical product of two cycles. Theory of Computing Systems, 54, 1–12.
  4. Ahmad, A., Al-Mushayt, O., & Bača, M. (2014). On edge irregularity strength of graphs. Applied Mathematics and Computation, 243, 607–610.
  5. Ahmad, A., Siddiqui, M. K., & Afzal, D. (2012). On the total edge irregularity strength of zigzag graphs. Australasian Journal of Combinatorics, 54, 141–149.
  6. Ahmad, A., Bača, M., & Nadeem, M. F. (2016). On the edge irregularity strength of Toeplitz graphs. Scientific Bulletin-University Politehnica of Bucharest, 78, 155–162.
  7. Ahmad, A., Al-Mushayt, O., & Siddiqui, M. K. (2012). On the total edge irregularity strength of hexagonal grid graphs. Australasian Journal of Combinatorics, 53, 263–271.
  8. Bača, M., Jendrol, S., Miller, M., & Ryan, J. (2007). On irregular total labellings. Discrete Mathematics, 307, 1378–1388.
  9. Bača, M., & Siddiqui, M. K. (2014). Total edge irregularity strength of generalized prism. Applied Mathematics and Computation, 235, 168–173.
  10. Chartrand, G., Jacobson, M. S., Lehel, J., Oellermann, O. R., & Saba, F. (1988). Irregular networks. Congressus Numerantium, 64, 187–192.
  11. Frieze, A., Gould, R. J., Karonski, M., & Finder, F. (2002). On graph irregularity strength. Journal of Graph Theory, 41, 120–137.
  12. Gallian, J. A. (2019). A dynamic survey graph labeling. Electronic Journal of
    Combinatorics, 19, 1–553.
  13. Kulli, V. R., Muddebihal, M. H. (1975). On lict and litact graph of a graph. Proceeding of the Indian National Science Academy, 41, 275–280.
  14. Tarawneh, I., Hasni, R., & Ahmad, A. (2016). On the edge irregularity strength of corona product of graphs with paths. Applied Mathematics E-Notes, 16, 80–87.
  15. Tarawneh, I., Hasni, R., & Ahmad, A. (2016). On the edge irregularity strength of
    corona product of cycle with isolated vertices. AKCE International Journal of Graphs and Combinatorics, 13, 213–217.
  16. Tarawneh, I., Hasni, R., Ahmad, A., & Lau, G. C. (2020). On the edge irregularity strength of corona product of graphs with cycle. Discrete Mathematics, Algorithms and Applications, 12(6), Article ID 2050083.
  17. Tarawneh, I., Hasni, R., & Asim, M. A. (2018). On the edge irregularity strength of disjoint union of star graph and subdivision of star graph. Ars Combinatoria, 141, 93–100.
  18. Tarawneh, I., Hasni, R., Asim, M. A., & Siddiqui, M. A. (2019). On the edge irregularity strength of disjoint union of graphs. Ars Combinatoria, 142, 239–249.
  19. Zhang, X., Cancan, M., Nadeem, M. F., & Imran, M. (2020). Edge irregularity strength of certain families of comb graph. Proyecciones (Antofagasta. On line), 39(4), 787–797.

Manuscript history

  • Received: 4 March 2022
  • Revised: 2 August 2022
  • Accepted: 4 August 2022
  • Online First: 10 August 2022

Related papers

Cite this paper

Nagesh, H. M, & Girish, V. R. (2022). On edge irregularity strength of line graph and line cut-vertex graph of comb graph. Notes on Number Theory and Discrete Mathematics, 28(3), 517-524, DOI: 10.7546/nntdm.2022.28.3.517-524.

Comments are closed.