An advance in infinite graph models for the analysis of transportation networks

• Autorzy: Cera M. , Fedriani E. M.

Identyfikatory

DOI

10.1515/amcs-2016-0061

• Języki publikacji: EN

Abstrakty

EN

This paper extends to infinite graphs the most general extremal issues, which are problems of determining the maximum number of edges of a graph not containing a given subgraph. It also relates the new results with the corresponding situations for the finite case. In particular, concepts from ‘finite’ graph theory, like the average degree and the extremal number, are generalized and computed for some specific cases. Finally, some applications of infinite graphs to the transportation of dangerous goods are presented; they involve the analysis of networks and percolation thresholds.

Słowa kluczowe

EN

infinite graph; average degree; extremal problems; road transport network; percolation threshold

PL

graf nieskończony; zagadnienie ekstremum; sieć transportowa; próg perkolacji

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2016
• Tom: Vol. 26, no. 4
• Strony: 855--869
• Opis fizyczny: Bibliogr. 35 poz., rys.

Twórcy

autor

Cera M.

• Department of Applied Mathematics I, University of Seville, ETSIA, Ctra. Utrera km 1, ES-41013 Seville, Spain

autor

Fedriani E. M.

• Department of Economics, Quantitative Methods and Economic History, Pablo de Olavide University, Ctra. Utrera km 1, ES-41013 Seville, Spain

Bibliografia

• [1] Balaji, S. and Revathi, N. (2012). An efficient approach for the optimization version of maximum weighted clique problem, WEAS Transactions on Mathematics 11(9): 773–783.
• [2] Barooah, P. and Hespanha, J. (2008). Estimation from relative measurements: Electrical analogy and large graphs, IEEE Transactions on Signal Processing 56(6): 2181–2193.
• [3] Bauderon, M. (1989). On system of equations defining infinite graphs, in J. van Leeuwen (Ed.), Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, Vol. 344, Springer-Verlag, Berlin/Heidelberg, pp. 54–73.
• [4] Caro, M., Fedriani, E. and Tenorio, A. (2015). Design of an efficient algorithm to determine a near-optimal location of parking areas for dangerous goods in the European Road Transport Network, in F. Corman et al. (Eds.), ICCL 2015, Lecture Notes in Computer Science, Vol. 9335, Springer International Publishing, Cham, pp. 617–626.
• [5] Cayley, A. (1895). The theory of groups, graphical representation, Cambridge Mathematical Papers 10: 26–28.
• [6] Cera, M., Diánez, A. and Márquez, A. (2000). The size of a graph without topological complete subgraphs, SIAM Journal on Discrete Mathematics 13(3): 295–301.
• [7] Cera, M., Diánez, A. and Márquez, A. (2004). Extremal graphs without topological complete subgraphs, SIAM Journal on Discrete Mathematics 18(2): 288–396.
• [8] Diestel, R. (2000). Graph Theory, Springer-Verlag, Berlin/Heidelberg.
• [9] Dirac, G. (1960). In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen, Mathematische Nachrichten 22: 61–85.
• [10] Dirac, G. and Schuster, S. (1954). A theorem of Kuratowski, Indagationes Mathematicae 16: 343–348.
• [11] Dridi, M. and Kacem, I. (2004). A hybrid approach for scheduling transportation networks, International Journal of Applied Mathematics and Computer Science 14(3): 397–409.
• [12] Fedriani, E., Mínguez, N. and Martín, A. (2005). Estabilidad de los indicadores topológicos de pobreza, Rect@ 13(1), Record No. 39.
• [13] Frucht, R. (1938). Herstellung von Graphen mit vorgegebener abstrakten Gruppe, Compositio Mathematica 6: 239–250.
• [14] Grünbaum, B. and Shephard, G. (1987). Tiling and Patterns, Freeman, New York, NY.
• [15] Klaučo, M., Blažek, S. and Kvasnica, M. (2016). An optimal path planning problem for heterogeneous multi-vehicle systems, International Journal of Applied Mathematics and Computer Science 26(2): 297–308, DOI: 10.1515/amcs-2016-0021.
• [16] Kudělka, M., Zehnalová, S., Horák, Z., Krömer, P. and Snášel, V. (2015). Local dependency in networks, International Journal of Applied Mathematics and Computer Science 25(2): 281–293, DOI: 10.1515/amcs-2015-0022.
• [17] Li, F. (2012). Some results on tenacity of graphs, WEAS Transactions on Mathematics 11(9): 760–772.
• [18] Li, F., Ye, Q. and Sheng, B. (2012). Computing rupture degrees of some graphs, WEAS Transactions on Mathematics 11(1): 23–33.
• [19] Mader, W. (1967). Homomorphieegenshaften und mittlere Kantendichte von Graphen, Mathematische Annalen 174: 265–268.
• [20] Mader, W. (1998a). 3n − 5 edges do force a subdivision of K5, Combinatorica 18(4): 569–595.
• [21] Mader, W. (1998b). Topological minors in graphs of minimum degree n, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 49: 199–211.
• [22] Milková, E. (2009). Constructing knowledge in graph theory and combinatorial optimization, WSEAS Transactions on Mathematics 8(8): 424–434.
• [23] Peng, W., Dong, G., Yang, K. and Su, J. (2013). A random road network model and its effect on topological characteristics of mobile delay-tolerant networks, IEEE Transactions Mobile Computing 13(12): 2706–2718.
• [24] Péter, T. (2012). Modeling nonlinear road traffic networks for junction control, International Journal of Applied Mathematics and Computer Science 22(3): 723–732, DOI: 10.2478/v10006-012-0054-1.
• [25] Ruiz, E., Hernández, M. and Fedriani, E. (2008). The development of mining heritage tourism: A systemic approach, in A.D. Ramos and P.S. Jiménez (Eds.), Tourism Development: Economics, Management and Strategy, Nova Science Publishers, Inc., Hauppauge, NY, pp. 121–143.
• [26] Sahimi, M. (1994). Applications of Percolation Theory, Taylor and Francis, London.
• [27] Stauffer, D. and Aharony, A. (1992). Introduction to Percolation Theory, Taylor and Francis, London.
• [28] Stein, M. (2011). Extremal infinite graph theory, Discrete Mathematics 311(15): 1472–1496.
• [29] Stein, M. and Zamora, J. (2013). Forcing large complete (topological) minors in infinite graphs, SIAM Journal on Discrete Mathematics 27(2): 697–707.
• [30] Wagner, K. (1960). Bemerkungen zu Hadwigers Vermutung, Mathematische Annalen 141: 433–451.
• [31] Wierman, J. and Naor, D. (2005). Criteria for evaluation of universal formulas for percolation thresholds, Physical Review E 71(036143).
• [32] Wierman, J., Naor, D. and Cheng, R. (2005). Improved site percolation threshold universal formula for two-dimensional matching lattices, Physical Review E 72(066116).
• [33] Yang, Y., Lin, J. and Dai, Y. (2002). Largest planar graphs and largest maximal planar graphs of diameter two, Journal of Computational and Applied Mathematics 144(1–2): 349–358.
• [34] Yousefi-Azaria, H., Khalifeha, M. and Ashrafi, A. (2011). Calculating the edge Wiener and edge Szeged indices of graphs, Journal of Computational and Applied Mathematics 235(16): 4866–4870.
• [35] Zemanian, A. (1988). Infinite electrical networks: A reprise, IEEE Transactions on Circuits and Systems 35(11): 1346–1358.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.