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

Martín Cera; Eugenio M. Fedriani

International Journal of Applied Mathematics and Computer Science (2016)

  • Volume: 26, Issue: 4, page 855-870
  • ISSN: 1641-876X

Abstract

top
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.

How to cite

top

Martín Cera, and Eugenio M. Fedriani. "An advance in infinite graph models for the analysis of transportation networks." International Journal of Applied Mathematics and Computer Science 26.4 (2016): 855-870. <http://eudml.org/doc/287177>.

@article{MartínCera2016,
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.},
author = {Martín Cera, Eugenio M. Fedriani},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {infinite graph; average degree; extremal problems; road transport network; percolation},
language = {eng},
number = {4},
pages = {855-870},
title = {An advance in infinite graph models for the analysis of transportation networks},
url = {http://eudml.org/doc/287177},
volume = {26},
year = {2016},
}

TY - JOUR
AU - Martín Cera
AU - Eugenio M. Fedriani
TI - An advance in infinite graph models for the analysis of transportation networks
JO - International Journal of Applied Mathematics and Computer Science
PY - 2016
VL - 26
IS - 4
SP - 855
EP - 870
AB - 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.
LA - eng
KW - infinite graph; average degree; extremal problems; road transport network; percolation
UR - http://eudml.org/doc/287177
ER -

References

top
  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. Zbl0947.05045
  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. Zbl1068.05032
  8. Diestel, R. (2000). Graph Theory, Springer-Verlag, Berlin/Heidelberg. Zbl0957.05001
  9. Dirac, G. (1960). In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen, Mathematische Nachrichten 22: 61-85. Zbl0096.17903
  10. Dirac, G. and Schuster, S. (1954). A theorem of Kuratowski, Indagationes Mathematicae 16: 343-348. Zbl0055.17002
  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. Zbl1137.90331
  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. Zbl0020.07804
  14. Grünbaum, B. and Shephard, G. (1987). Tiling and Patterns, Freeman, New York, NY. Zbl0601.05001
  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. Zbl1347.93186
  16. 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. Zbl1322.94130
  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. Zbl0171.22405
  20. Mader, W. (1998a). 3n - 5 edges do force a subdivision of K5, Combinatorica 18(4): 569-595. Zbl0924.05039
  21. Mader, W. (1998b). Topological minors in graphs of minimum degree n, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 49: 199-211. Zbl0931.05075
  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. Zbl1302.93034
  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. Zbl0862.60092
  28. Stein, M. (2011). Extremal infinite graph theory, Discrete Mathematics 311(15): 1472-1496. Zbl1223.05200
  29. Stein, M. and Zamora, J. (2013). Forcing large complete (topological) minors in infinite graphs, SIAM Journal on Discrete Mathematics 27(2): 697-707. Zbl1272.05088
  30. Wagner, K. (1960). Bemerkungen zu Hadwigers Vermutung, Mathematische Annalen 141: 433-451. Zbl0096.17904
  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. Zbl1003.05062
  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. Zbl1222.05037
  35. Zemanian, A. (1988). Infinite electrical networks: A reprise, IEEE Transactions on Circuits and Systems 35(11): 1346-1358. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.