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.
@article{bwmeta1.element.bwnjournal-article-amcv26i4p855bwm,
author = {Mart\'\i n Cera and Eugenio M. Fedriani},
title = {An advance in infinite graph models for the analysis of transportation networks},
journal = {International Journal of Applied Mathematics and Computer Science},
volume = {26},
year = {2016},
pages = {855-870},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-amcv26i4p855bwm}
}
Martín Cera; Eugenio M. Fedriani. An advance in infinite graph models for the analysis of transportation networks. International Journal of Applied Mathematics and Computer Science, Tome 26 (2016) pp. 855-870. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-amcv26i4p855bwm/
[000] 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.
[001] Barooah, P. and Hespanha, J. (2008). Estimation from relative measurements: Electrical analogy and large graphs, IEEE Transactions on Signal Processing 56(6): 2181-2193.
[002] 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.
[003] 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.
[004] Cayley, A. (1895). The theory of groups, graphical representation, Cambridge Mathematical Papers 10: 26-28.
[005] 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. | Zbl 0947.05045
[006] 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. | Zbl 1068.05032
[007] Diestel, R. (2000). Graph Theory, Springer-Verlag, Berlin/Heidelberg. | Zbl 0957.05001
[008] Dirac, G. (1960). In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen, Mathematische Nachrichten 22: 61-85. | Zbl 0096.17903
[009] Dirac, G. and Schuster, S. (1954). A theorem of Kuratowski, Indagationes Mathematicae 16: 343-348. | Zbl 0055.17002
[010] 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. | Zbl 1137.90331
[011] Fedriani, E., Mínguez, N. and Martín, A. (2005). Estabilidad de los indicadores topológicos de pobreza, Rect@ 13(1), Record No. 39.
[012] Frucht, R. (1938). Herstellung von Graphen mit vorgegebener abstrakten Gruppe, Compositio Mathematica 6: 239-250. | Zbl 0020.07804
[013] Grünbaum, B. and Shephard, G. (1987). Tiling and Patterns, Freeman, New York, NY. | Zbl 0601.05001
[014] 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. | Zbl 1347.93186
[015] Kudĕlka, M., Zehnalová, S., Horák, Z., Krömer, P. and Snásĕl, V. (2015). Local dependency in networks, International Journal of Applied Mathematics and Computer Science 25(2): 281-293, DOI: 10.1515/amcs-2015-0022. | Zbl 1322.94130
[016] Li, F. (2012). Some results on tenacity of graphs, WEAS Transactions on Mathematics 11(9): 760-772.
[017] Li, F., Ye, Q. and Sheng, B. (2012). Computing rupture degrees of some graphs, WEAS Transactions on Mathematics 11(1): 23-33.
[018] Mader, W. (1967). Homomorphieegenshaften und mittlere Kantendichte von Graphen, Mathematische Annalen 174: 265-268. | Zbl 0171.22405
[019] Mader, W. (1998a). 3n - 5 edges do force a subdivision of K5, Combinatorica 18(4): 569-595. | Zbl 0924.05039
[020] Mader, W. (1998b). Topological minors in graphs of minimum degree n, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 49: 199-211. | Zbl 0931.05075
[021] Milková, E. (2009). Constructing knowledge in graph theory and combinatorial optimization, WSEAS Transactions on Mathematics 8(8): 424-434.
[022] 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.
[023] 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. | Zbl 1302.93034
[024] 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.
[025] Sahimi, M. (1994). Applications of Percolation Theory, Taylor and Francis, London.
[026] Stauffer, D. and Aharony, A. (1992). Introduction to Percolation Theory, Taylor and Francis, London. | Zbl 0862.60092
[027] Stein, M. (2011). Extremal infinite graph theory, Discrete Mathematics 311(15): 1472-1496. | Zbl 1223.05200
[028] Stein, M. and Zamora, J. (2013). Forcing large complete (topological) minors in infinite graphs, SIAM Journal on Discrete Mathematics 27(2): 697-707. | Zbl 1272.05088
[029] Wagner, K. (1960). Bemerkungen zu Hadwigers Vermutung, Mathematische Annalen 141: 433-451. | Zbl 0096.17904
[030] Wierman, J. and Naor, D. (2005). Criteria for evaluation of universal formulas for percolation thresholds, Physical Review E 71(036143).
[031] Wierman, J., Naor, D. and Cheng, R. (2005). Improved site percolation threshold universal formula for two-dimensional matching lattices, Physical Review E 72(066116).
[032] 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. | Zbl 1003.05062
[033] 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. | Zbl 1222.05037
[034] Zemanian, A. (1988). Infinite electrical networks: A reprise, IEEE Transactions on Circuits and Systems 35(11): 1346-1358.