American Institute of Mathematical Sciences

Advanced
doi: 10.3934/mfc.2021029
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

On $ {L}(2,1) $-labelings of some products of oriented cycles

Lucas Colucci 1,, and  Ervin Győri 2,

1. 

Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Reáltanoda u. 13–15, 1053 Budapest, Hungary
2. 

Central European University, Department of Mathematics and its Applications, Nádor u. 9, 1051 Budapest, Hungary

* Corresponding author: Lucas Colucci

Received  December 2019 Revised  July 2021 Early access November 2021

Fund Project: The first author is partially supported by the National Research, Development and Innovation, NKFIH grant K 116769. The second author is partially supported by the National Research, Development and Innovation, NKFIH grants K 116769 and SNN 117879

We refine two results of Jiang, Shao and Vesel on the $ L(2,1) $-labeling number $ \lambda $ of the Cartesian and the strong product of two oriented cycles. For the Cartesian product, we compute the exact value of $ \lambda(\overrightarrow{C_m} \square \overrightarrow{C_n}) $ for $ m $, $ n \geq 40 $; in the case of strong product, we either compute the exact value or establish a gap of size one for $ \lambda(\overrightarrow{C_m} \boxtimes \overrightarrow{C_n}) $ for $ m $, $ n \geq 48 $.

Keywords: $ L(2,1) $-labeling, oriented graphs, graph products, Cartesian product of graphs, strong product of graphs.
Mathematics Subject Classification: Primary: 05C15, 05C78; Secondary: 05C20.
Citation: Lucas Colucci, Ervin Győri. On $ {L}(2,1) $-labelings of some products of oriented cycles. Mathematical Foundations of Computing, doi: 10.3934/mfc.2021029
References:
[1]

T. Calamoneri, The ${L}(h, k) $-labelling problem: An updated survey and annotated bibliography, 2014, Available on http://www.dsi.uniroma1.it/calamo/PDF-FILES/survey.pdf. Google Scholar

[2]

G. J. Chang and S.-C. Liaw, The ${L}(2, 1) $-labeling problem on ditrees, Ars Combin., 66 (2003), 23-31.   Google Scholar

[3]

W. K. Hale, Frequency assignment: Theory and applications, Proceedings of the IEEE, 68 (1980), 1497-1514.  doi: 10.1109/PROC.1980.11899.  Google Scholar

[4]

Z. Shao, H. Jiang and A. Vesel, ${L}(2, 1) $-labeling of the cartesian and strong product of two directed cycles, Mathematical Foundations of Computing, 1 (2018), 49-61.  doi: 10.3934/mfc.2018003.  Google Scholar

[5]

J. J. Sylvester, et al, Mathematical questions with their solutions, Educational times 41, 21 (1884), 6pp. Google Scholar

[6]

K. -C. Yeh, Labeling Graphs with a Condition at Distance Two, PhD thesis, University of South Carolina, 1990. Google Scholar

[7]

R. K. Yeh, A survey on labeling graphs with a condition at distance two, Discrete Math., 306 (2006), 1217-1231.  doi: 10.1016/j.disc.2005.11.029.  Google Scholar

show all references

References:
[1]

T. Calamoneri, The ${L}(h, k) $-labelling problem: An updated survey and annotated bibliography, 2014, Available on http://www.dsi.uniroma1.it/calamo/PDF-FILES/survey.pdf. Google Scholar

[2]

G. J. Chang and S.-C. Liaw, The ${L}(2, 1) $-labeling problem on ditrees, Ars Combin., 66 (2003), 23-31.   Google Scholar

[3]

W. K. Hale, Frequency assignment: Theory and applications, Proceedings of the IEEE, 68 (1980), 1497-1514.  doi: 10.1109/PROC.1980.11899.  Google Scholar

[4]

Z. Shao, H. Jiang and A. Vesel, ${L}(2, 1) $-labeling of the cartesian and strong product of two directed cycles, Mathematical Foundations of Computing, 1 (2018), 49-61.  doi: 10.3934/mfc.2018003.  Google Scholar

[5]

J. J. Sylvester, et al, Mathematical questions with their solutions, Educational times 41, 21 (1884), 6pp. Google Scholar

[6]

K. -C. Yeh, Labeling Graphs with a Condition at Distance Two, PhD thesis, University of South Carolina, 1990. Google Scholar

[7]

R. K. Yeh, A survey on labeling graphs with a condition at distance two, Discrete Math., 306 (2006), 1217-1231.  doi: 10.1016/j.disc.2005.11.029.  Google Scholar

Figure 1.  The Cartesian product of $\overrightarrow {{P_3}} $ and $\overrightarrow {{P_4}} $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  The strong product of $\overrightarrow {{P_3}} $ and $\overrightarrow {{P_4}} $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  A $ \overrightarrow{P_4} \boxtimes \overrightarrow{P_4} $ subgraph of $ \overrightarrow{C_m} \boxtimes \overrightarrow{C_n} $
Figure Options

Download full-size image

Download as PowerPoint slide

[1]

Zehui Shao, Huiqin Jiang, Aleksander Vesel. L(2, 1)-labeling of the Cartesian and strong product of two directed cycles. Mathematical Foundations of Computing, 2018, 1 (1) : 49-61. doi: 10.3934/mfc.2018003
[2]

Shuangliang Tian, Ping Chen, Yabin Shao, Qian Wang. Adjacent vertex distinguishing edge-colorings and total-colorings of the Cartesian product of graphs. Numerical Algebra, Control & Optimization, 2014, 4 (1) : 49-58. doi: 10.3934/naco.2014.4.49
[3]

Braxton Osting, Jérôme Darbon, Stanley Osher. Statistical ranking using the $l^{1}$-norm on graphs. Inverse Problems & Imaging, 2013, 7 (3) : 907-926. doi: 10.3934/ipi.2013.7.907
[4]

Christine A. Kelley, Deepak Sridhara, Joachim Rosenthal. Zig-zag and replacement product graphs and LDPC codes. Advances in Mathematics of Communications, 2008, 2 (4) : 347-372. doi: 10.3934/amc.2008.2.347
[5]

Serge Nicaise. Control and stabilization of 2 × 2 hyperbolic systems on graphs. Mathematical Control & Related Fields, 2017, 7 (1) : 53-72. doi: 10.3934/mcrf.2017004
[6]

Barton E. Lee. Consensus and voting on large graphs: An application of graph limit theory. Discrete & Continuous Dynamical Systems, 2018, 38 (4) : 1719-1744. doi: 10.3934/dcds.2018071
[7]

Jennifer D. Key, Washiela Fish, Eric Mwambene. Codes from the incidence matrices and line graphs of Hamming graphs $H^k(n,2)$ for $k \geq 2$. Advances in Mathematics of Communications, 2011, 5 (2) : 373-394. doi: 10.3934/amc.2011.5.373
[8]

Litao Guo, Bernard L. S. Lin. Vulnerability of super connected split graphs and bisplit graphs. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1179-1185. doi: 10.3934/dcdss.2019081
[9]

Hirobumi Mizuno, Iwao Sato. L-functions and the Selberg trace formulas for semiregular bipartite graphs. Conference Publications, 2003, 2003 (Special) : 638-646. doi: 10.3934/proc.2003.2003.638
[10]

Srimathy Srinivasan, Andrew Thangaraj. Codes on planar Tanner graphs. Advances in Mathematics of Communications, 2012, 6 (2) : 131-163. doi: 10.3934/amc.2012.6.131
[11]

Cristina M. Ballantine. Ramanujan type graphs and bigraphs. Conference Publications, 2003, 2003 (Special) : 78-82. doi: 10.3934/proc.2003.2003.78
[12]

Daniele D'angeli, Alfredo Donno, Michel Matter, Tatiana Nagnibeda. Schreier graphs of the Basilica group. Journal of Modern Dynamics, 2010, 4 (1) : 167-205. doi: 10.3934/jmd.2010.4.167
[13]

James B. Kennedy, Jonathan Rohleder. On the hot spots of quantum graphs. Communications on Pure & Applied Analysis, 2021, 20 (9) : 3029-3063. doi: 10.3934/cpaa.2021095
[14]

Yong Lin, Gábor Lippner, Dan Mangoubi, Shing-Tung Yau. Nodal geometry of graphs on surfaces. Discrete & Continuous Dynamical Systems, 2010, 28 (3) : 1291-1298. doi: 10.3934/dcds.2010.28.1291
[15]

Rodrigo P. Pacheco, Rafael O. Ruggiero. On C1, β density of metrics without invariant graphs. Discrete & Continuous Dynamical Systems, 2018, 38 (1) : 247-261. doi: 10.3934/dcds.2018012
[16]

Dina Ghinelli, Jennifer D. Key. Codes from incidence matrices and line graphs of Paley graphs. Advances in Mathematics of Communications, 2011, 5 (1) : 93-108. doi: 10.3934/amc.2011.5.93
[17]

Wooyeon Kim, Seonhee Lim. Notes on the values of volume entropy of graphs. Discrete & Continuous Dynamical Systems, 2020, 40 (9) : 5117-5129. doi: 10.3934/dcds.2020221
[18]

Renato Iturriaga, Héctor Sánchez Morgado. The Lax-Oleinik semigroup on graphs. Networks & Heterogeneous Media, 2017, 12 (4) : 643-662. doi: 10.3934/nhm.2017026
[19]

Thomas Zaslavsky. Quasigroup associativity and biased expansion graphs. Electronic Research Announcements, 2006, 12: 13-18.

[20]

Deng Lu, Maria De Iorio, Ajay Jasra, Gary L. Rosner. Bayesian inference for latent chain graphs. Foundations of Data Science, 2020, 2 (1) : 35-54. doi: 10.3934/fods.2020003

 Impact Factor: 

Tools

Metrics

  • PDF downloads (37)
  • HTML views (35)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy