Article in press
Authors:
Azam Sadat Emadi
University of Mazandaran, Department of Mathematics, Faculty of Mathematical Sciences, Babolsar, Iran
email: math_emadi2000@yahoo.com
Doost Ali Mojdeh
University of Mazandaran, Department of Mathematics, Faculty of Mathematical Sciences, Babolsar, Iran
email: damojdeh@umz.ac.ir
Title:
Total vertex product irregularity strength of graphs
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2022-07-10 , Revised: 2023-03-15 , Accepted: 2023-03-15 , Available online: 2023-04-20 , https://doi.org/10.7151/dmgt.2495
Abstract:
Consider a simple graph $G$. We call a labeling $w:E(G)\cup V(G)\rightarrow
\{1, 2, \dots, s\}$ (total vertex) product-irregular, if all
product degrees $pd_G(v)$ induced by this labeling are distinct, where
$pd_G(v)=w(v)×\prod_{e\ni v}w(e)$. The strength of $w$ is $s$, the maximum
number used to label the members of $E(G)\cup V(G)$. The minimum value of $s$
that allows some irregular labeling is called the total vertex product
irregularity strength and denoted $tvps(G)$. We provide some general bounds,
as well as exact values for chosen families of graphs.
Keywords:
product-irregular labeling, total vertex product irregularity strength, vertex-distinguishing labeling
References:
- M. Aigner and E. Triesch, Irregular assignments of trees and forests, SIAM J. Discrete Math. 3 (1990) 439–449.
https://doi.org/10.1137/0403038 - D. Amar and O. Togni, Irregularity strength of trees, Discrete Math. 190 (1998) 15–38.
https://doi.org/10.1016/S0012-365X(98)00112-5 - M. Anholcer, Product irregularity strength of graphs, Discrete Math. 309 (2009) 6434–6439.
https://doi.org/10.1016/j.disc.2008.10.014 - M. Anholcer, Product irregularity strength of certain graphs, Ars Math. Contemp. 7 (2014) 23–29.
https://doi.org/10.26493/1855-3974.258.2a0 - M. Anholcer, M. Kalkowski and J. Przybyło, A new upper bound for the total vertex irregularity strength of graphs, Discrete Math. 309 (2009) 6316–6317.
https://doi.org/10.1016/j.disc.2009.05.023 - M. Anholcer and C. Palmer, Irregular labellings of circulant graphs, Discrete Math. 312 (2012) 3461–3466.
https://doi.org/10.1016/j.disc.2012.06.017 - M. Bača, S. Jendrol', M. Miller and J. Ryan, On irregular total labellings, Discrete Math. 307 (2007) 1378–1388.
https://doi.org/10.1016/j.disc.2005.11.075 - G. Chartrand, M.S. Jacobson, J. Lehel, O.R. Oellermann, S. Ruiz and F. Saba, Irregular networks, Congr. Numer. 64 (1988) 187–192.
- R. Darda and A. Hujdurović, On bounds for the product irregularity strength of graphs, Graphs Combin. 31 (2015) 1347–1357.
https://doi.org/10.1007/s00373-014-1458-5 - P. Erdős, On some applications of graph theory to number theoretic problems, Publ. Ramanujan Inst. 1 (1969) 131–136.
- R.J. Faudree and J. Lehel, Bounds on the irregularity strength of regular graphs, in: Colloquia Mathematica Societatis János Bolyai 52, Combinatorics, Eger (Hungary), (North-Holland, Amsterdam 1987) 239–246.
- M. Ferrara, R.J. Gould, M. Karoński and F. Pfender, An iterative approach to graph irregularity strength, Discrete Appl. Math. 158 (2010) 1189–1194.
https://doi.org/10.1016/j.dam.2010.02.003 - A. Frieze, R.J. Gould, M. Karoński and F. Pfender, On graph irregularity strength, J. Graph Theory 41 (2002) 120–137.
https://doi.org/10.1002/jgt.10056 - M. Kalkowski, M. Karoński and F. Pfender, A new upper bound for the irregularity strength of graphs, SIAM J. Discrete Math. 25 (2011) 1319–1321.
https://doi.org/10.1137/090774112 - J. Lehel, Facts and quests on degree irreglar assignments, in: Graph Theory, Combinatorics and Applications, (Wiley, New York 1991) 765–782.
- P. Majerski and J. Przybyło, On the irregularity strength of dense graphs, SIAM J. Discrete Math. 28 (2014) 197–205.
https://doi.org/10.1137/120886650 - P. Majerski and J. Przybyło, Total vertex irregularity strength of dense graphs, J. Graph Theory 76 (2014) 34–41.
https://doi.org/10.1002/jgt.21748 - T. Nierhoff, A tight bound on the irregularity strength of graphs, SIAM J. Discrete Math. 13 (2000) 313–323.
https://doi.org/10.1137/S0895480196314291 - Nurdin, E.T. Baskoro, A.N.M. Salman and N.N. Gaos, On the total vertex irregularity strength of trees, Discrete Math. 310 (2010) 3043–3048.
https://doi.org/10.1016/j.disc.2010.06.041 - O. Pikhurko, Characterization of product anti-magic graphs of large order, Graphs Combin. 23 (2007) 681–689.
https://doi.org/10.1007/s00373-007-0748-6 - J. Skowronek-Kaziów, $1$,$2$-conjecture-the multiplicative version, Inform. Process. Lett. 107 (2008) 93–95.
https://doi.org/10.1016/j.ipl.2008.01.006 - J. Skowronek-Kaziów, Multiplicative vertex-colouring weightings of graphs, Inform. Process. Lett. 112 (2012) 191–194.
https://doi.org/10.1016/j.ipl.2011.11.009 - M. Tchebichef, Mémoire sur les nombres premiers, J. Math. Pures Appl. Série 1 17 (1852) 366–390.
Close