1. bookVolume 26 (2016): Issue 4 (December 2016)
Journal Details
License
Format
Journal
First Published
05 Apr 2007
Publication timeframe
4 times per year
Languages
English
access type Open Access

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

Published Online: 30 Dec 2016
Page range: 855 - 869
Received: 29 Sep 2015
Accepted: 02 Jul 2016
Journal Details
License
Format
Journal
First Published
05 Apr 2007
Publication timeframe
4 times per year
Languages
English

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.

Keywords

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

Barooah, P. and Hespanha, J. (2008). Estimation from relative measurements: Electrical analogy and large graphs, IEEE Transactions on Signal Processing 56(6): 2181-2193.Search in Google Scholar

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.Search in Google Scholar

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.Search in Google Scholar

Cayley, A. (1895). The theory of groups, graphical representation, Cambridge Mathematical Papers 10: 26-28.Search in Google Scholar

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.Search in Google Scholar

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.Search in Google Scholar

Diestel, R. (2000). Graph Theory, Springer-Verlag, Berlin/Heidelberg.Search in Google Scholar

Dirac, G. (1960). In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen, Mathematische Nachrichten 22: 61-85.Search in Google Scholar

Dirac, G. and Schuster, S. (1954). A theorem of Kuratowski, Indagationes Mathematicae 16: 343-348.Search in Google Scholar

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

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

Frucht, R. (1938). Herstellung von Graphen mit vorgegebener abstrakten Gruppe, Compositio Mathematica 6: 239-250.Search in Google Scholar

Grünbaum, B. and Shephard, G. (1987). Tiling and Patterns, Freeman, New York, NY.Search in Google Scholar

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.Search in Google Scholar

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.Search in Google Scholar

Li, F. (2012). Some results on tenacity of graphs, WEAS Transactions on Mathematics 11(9): 760-772.Search in Google Scholar

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

Mader, W. (1967). Homomorphieegenshaften und mittlere Kantendichte von Graphen, Mathematische Annalen 174: 265-268.Search in Google Scholar

Mader, W. (1998a). 3n − 5 edges do force a subdivision of K5, Combinatorica 18(4): 569-595.Search in Google Scholar

Mader, W. (1998b). Topological minors in graphs of minimum degree n, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 49: 199-211.Search in Google Scholar

Milková, E. (2009). Constructing knowledge in graph theory and combinatorial optimization, WSEAS Transactions on Mathematics 8(8): 424-434.Search in Google Scholar

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.Search in Google Scholar

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.Search in Google Scholar

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

Sahimi, M. (1994). Applications of Percolation Theory, Taylor and Francis, London.Search in Google Scholar

Stauffer, D. and Aharony, A. (1992). Introduction to Percolation Theory, Taylor and Francis, London.Search in Google Scholar

Stein, M. (2011). Extremal infinite graph theory, Discrete Mathematics 311(15): 1472-1496.Search in Google Scholar

Stein, M. and Zamora, J. (2013). Forcing large complete (topological) minors in infinite graphs, SIAM Journal on Discrete Mathematics 27(2): 697-707.Search in Google Scholar

Wagner, K. (1960). Bemerkungen zu Hadwigers Vermutung, Mathematische Annalen 141: 433-451.Search in Google Scholar

Wierman, J. and Naor, D. (2005). Criteria for evaluation of universal formulas for percolation thresholds, Physical Review E 71(036143).Search in Google Scholar

Wierman, J., Naor, D. and Cheng, R. (2005). Improved site percolation threshold universal formula for two-dimensional matching lattices, Physical Review E 72(066116).Search in Google Scholar

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.Search in Google Scholar

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.Search in Google Scholar

Zemanian, A. (1988). Infinite electrical networks: A reprise, IEEE Transactions on Circuits and Systems 35(11): 1346-1358.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo