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

Martín Cera; Eugenio M. Fedriani

doi:10.1515/amcs-2016-0061

.blurhash-client-img { display: none !important; }

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

International Journal of Applied Mathematics and Computer Science

Volume 26 (2016): Issue 4 (December 2016)

By: Martín Cera and Eugenio M. Fedriani

Open Access

|Dec 2016

Abstract

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.

References

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.
Search in Google Scholar Back to article
Barooah, P. and Hespanha, J. (2008). Estimation from relative measurements: Electrical analogy and large graphs, IEEE Transactions on Signal Processing 56(6): 2181-2193.10.1109/TSP.2007.912270
Search in Google Scholar Back to article
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.10.1007/3-540-50728-0_35
Search in Google Scholar Back to article
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.10.1007/978-3-319-24264-4_42
Search in Google Scholar Back to article
Cayley, A. (1895). The theory of groups, graphical representation, Cambridge Mathematical Papers 10: 26-28.
Search in Google Scholar Back to article
Cera, M., Diánez, A. and Márquez, A. (2000). The size of a graph without topological complete subgraphs, SIAMJournal on Discrete Mathematics 13(3): 295-301.10.1137/S0895480197315941
Search in Google Scholar Back to article
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.10.1137/S0895480100378677
Search in Google Scholar Back to article
Diestel, R. (2000). Graph Theory, Springer-Verlag, Berlin/Heidelberg.
Search in Google Scholar Back to article
Dirac, G. (1960). In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen, Mathematische Nachrichten 22: 61-85.10.1002/mana.19600220107
Search in Google Scholar Back to article
Dirac, G. and Schuster, S. (1954). A theorem of Kuratowski, Indagationes Mathematicae 16: 343-348.10.1016/S1385-7258(54)50043-0
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Fedriani, E., Mínguez, N. and Mart´ın, A. (2005). Estabilidad de los indicadores topológicos de pobreza, Rect@ 13(1), Record No. 39.
Search in Google Scholar Back to article
Frucht, R. (1938). Herstellung von Graphen mit vorgegebener abstrakten Gruppe, Compositio Mathematica 6: 239-250.
Search in Google Scholar Back to article
Grünbaum, B. and Shephard, G. (1987). Tiling and Patterns, Freeman, New York, NY.
Search in Google Scholar Back to article
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.10.1515/amcs-2016-0021
Search in Google Scholar Back to article
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.10.1515/amcs-2015-0022
Search in Google Scholar Back to article
Li, F. (2012). Some results on tenacity of graphs, WEAS Transactions on Mathematics 11(9): 760-772.
Search in Google Scholar Back to article
Li, F., Ye, Q. and Sheng, B. (2012). Computing rupture degrees of some graphs, WEAS Transactions on Mathematics 11(1): 23-33.
Search in Google Scholar Back to article
Mader, W. (1967). Homomorphieegenshaften und mittlere Kantendichte von Graphen, Mathematische Annalen 174: 265-268.10.1007/BF01364272
Search in Google Scholar Back to article
Mader, W. (1998a). 3n − 5 edges do force a subdivision of K5, Combinatorica 18(4): 569-595.10.1007/s004930050041
Search in Google Scholar Back to article
Mader, W. (1998b). Topological minors in graphs of minimum degree n, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 49: 199-211.10.1090/dimacs/049/14
Search in Google Scholar Back to article
Milková, E. (2009). Constructing knowledge in graph theory and combinatorial optimization, WSEAS Transactions on Mathematics 8(8): 424-434.
Search in Google Scholar Back to article
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.10.1109/TMC.2013.66
Search in Google Scholar Back to article
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.10.2478/v10006-012-0054-1
Search in Google Scholar Back to article
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´enez (Eds.), Tourism Development: Economics, Management and Strategy, Nova Science Publishers, Inc., Hauppauge, NY, pp. 121-143.
Search in Google Scholar Back to article
Sahimi, M. (1994). Applications of Percolation Theory, Taylor and Francis, London.10.1201/9781482272444
Search in Google Scholar Back to article
Stauffer, D. and Aharony, A. (1992). Introduction to Percolation Theory, Taylor and Francis, London.
Search in Google Scholar Back to article
Stein, M. (2011). Extremal infinite graph theory, Discrete Mathematics 311(15): 1472-1496.10.1016/j.disc.2010.12.018
Search in Google Scholar Back to article
Stein, M. and Zamora, J. (2013). Forcing large complete (topological) minors in infinite graphs, SIAM Journal on Discrete Mathematics 27(2): 697-707.10.1137/100819722
Search in Google Scholar Back to article
Wagner, K. (1960). Bemerkungen zu Hadwigers Vermutung, Mathematische Annalen 141: 433-451.10.1007/BF01360256
Search in Google Scholar Back to article
Wierman, J. and Naor, D. (2005). Criteria for evaluation of universal formulas for percolation thresholds, Physical Review E 71(036143).10.1103/PhysRevE.71.03614315903529
Search in Google Scholar Back to article
Wierman, J., Naor, D. and Cheng, R. (2005). Improved site percolation threshold universal formula for two-dimensional matching lattices, Physical Review E 72(066116).10.1103/PhysRevE.72.06611616486019
Search in Google Scholar Back to article
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.10.1016/S0377-0427(01)00572-6
Search in Google Scholar Back to article
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.10.1016/j.cam.2011.02.019
Search in Google Scholar Back to article
Zemanian, A. (1988). Infinite electrical networks: A reprise, IEEE Transactions on Circuits and Systems 35(11): 1346-1358.10.1109/31.14459
Search in Google Scholar Back to article

Articles in this issue

DOI: https://doi.org/10.1515/amcs-2016-0061 | Journal eISSN: 2083-8492 | Journal ISSN: 1641-876X

Journal RSS Feed

Language: English

Page range: 855 - 869

Submitted on: Sep 29, 2015

Accepted on: Jul 2, 2016

Published on: Dec 30, 2016

Published by: University of Zielona Góra

In partnership with: Paradigm Publishing Services

Publication frequency: 4 issues per year

Keywords:

infinite graph,

average degree,

extremal problems,

road transport network,

percolation

Related subjects:

Mathematics,

Applied mathematics

© 2016 Martín Cera, Eugenio M. Fedriani, published by University of Zielona Góra
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Volume 26 (2016): Issue 4 (December 2016)