The Graph Theory General Position Problem on Some Interconnection Networks

• Autorzy: Manuel P. , Klavžar S.

Identyfikatory

DOI

10.3233/FI-2018-1748

• Języki publikacji: EN

Abstrakty

EN

Given a graph G, the (graph theory) general position problem is to find the maximum number of vertices such that no three vertices lie on a common geodesic. This graph invariant is called the general position number (gp-number for short) of G and denoted by gp(G). In this paper, the gp-number is determined for a large class of subgraphs of the infinite grid graph and for the infinite diagonal grid. To derive these results, we introduce monotone-geodesic labeling and prove a Monotone Geodesic Lemma that is in turn developed using the Erdös-Szekeres theorem on monotone sequences. The gp-number of the 3-dim infinite grid is bounded. Using isometric path covers, the gp-number is also determined for Beneš networks.

Słowa kluczowe

EN

Beneš network; general position problem; infinite grids; interconnection networks; isometric subgraph; monotone-geodesic labeling

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 163, nr 4
• Strony: 339--350
• Opis fizyczny: Bibliogr. 23 poz., rys.

Twórcy

autor

Manuel P.

• Department of Information Science, College of Computing Science and Engineering, Kuwait University, Kuwait

autor

Klavžar S.

• Faculty of Mathematics and Physics, University of Ljubljana, Slovenia

Bibliografia

• [1] Barragán-Ramírez GA, Rodríguez-Velázquez JA, The local metric dimension of strong product graphs. Graphs and Combinatorics, 2016:32:1263-1278.
• [2] Bogdanowicz ZR. Isomorphism between circulants and Cartesian products of cycles. Discrete Applied Mathematics, 2017;226:40-43. URL https://doi.org/10.1016/j.dam.2017.04.003.
• [3] Brešar B. Improving the Clark-Suen bound on the domination number of the Cartesian product of graphs. Discrete Mathematics, 2017;340:2398-2401. URL https://doi.org/10.1016/j.disc.2017.05.007.
• [4] Bukh B, Matoušek J. Erdős-Szekeres-type statements: Ramsey function and decidability in dimension 1. Duke Mathematical Journal, 2014;163:2243-2270.
• [5] Burckel S, Gioan E, Thomé E. Computation with no memory, and rearrangeable multicast networks. Discrete Mathematics and Theoretical Computer Science, 2014;16:121-142.
• [6] Dudeney HE. Amusements in Mathematics. Thomas Nelson and sons Ltd, 1917.
• [7] Erdös P, Szekeres G. A combinatorial problem in geometry. Compositio Mathematica, 1935;2:463-470.
• [8] Feng B, Zhang J, Zhong Q, Li W, Li S, Li H, Cheng P, Meng S, Chen L, Wu K. Experimental realization of two-dimensional boron sheets. Nature Chemistry, 2016;8:563-568. doi:10.1038/nchem.2491.
• [9] Fitzpatrick SL. The isometric path number of the Cartesian product of paths. Congressus Numerantium, 1999;137:109-119.
• [10] Froese V, Kanj I, Nichterlein A, Niedermeier R. International Journal of Computational Geometry & Applications, 2017;27:277-296. URL https://doi.org/10.1142/S021819591750008X.
• [11] Hammack R, Imrich W, Klavžar S. Handbook of Product Graphs. CRC Press, Boca Raton, FL, 2011. 2nd Edition. ISBN: 9781138199088.
• [12] Klavžar S, Manuel P, Nadjafi-Arani MJ, Sundara Rajan R, Grigorious C, Stephen S, Average distance in interconnection networks via reduction theorems for vertex-weighted graphs. The Computer Journal, 2016;59:1900-1910. URL https://doi.org/10.1093/comjnl/bxw046.
• [13] Manuel P, Abd-El-Barr MI, Rajasingh I, Rajan B. An efficient representation of Benes networks and its applications. Journal of Discrete Algorithms, 2008;6:11-19. URL https://doi.org/10.1016/j.jda.2006.08.003.
• [14] Manuel P, Klavžar S. Using A general position problem in graph theory. Bulletin of the Australian Mathematical Society, in press, 2018.
• [15] Misiak A, Stpień Z, Szymaszkiewicz A, Szymaszkiewicz L, Zwierzchowski M. A note on the no-three-inline problem on a torus. Discrete Mathematics, 2016;339:217-221. URL https://doi.org/10.1016/j.disc.2015.08.006.
• [16] Pan JJ, Chang GJ. Isometric path numbers of graphs. Discrete Mathematics, 2006;306:2091-2096. URL https://doi.org/10.1016/j.disc.2006.04.003.
• [17] Payne M, Wood DR. On the general position subset selection problem. SIAM Journal Discrete Mathematics, 2013;27:1727-1733. doi:10.1137/120897493.
• [18] Penev ES, Bhowmick S, Sadrzadeh A, Yakobson BI. Polymorphism of two-dimensional boron. Nano Letters, 2012;12:2441-2445. doi:10.1021/nl3004754.
• [19] Por A, Wood DR. No-Three-in-Line-in-3D. Algorithmica, 2007;47:481-488. doi:10.1007/s00453-006-0158-9.
• [20] Rall DF, Wash K. On minimum identifying codes in some Cartesian product graphs. Graphs and Combinatorics, 2017;33:1037-1053. doi:10.1007/s00373-017-1813-4.
• [21] Xu JM. Combinatorial Theory in Networks. Science Press, Beijing, 2013.
• [22] Yang Y, Chen Y. The thickness of amalgamations and Cartesian product of graphs. Discussiones Mathematicae Graph Theory, 2017;37:561-572. doi:10.7151/dmgt.1942.
• [23] Zhao W, Wang F, Gao X, Li H. Bondage number of the strong product of two trees. Discrete Applied Mathematics, 2017;230:133-145. URL https://doi.org/10.1016/j.dam.2017.06.019.