Minimax properties of some density measures in graphs and digraphs

References

• J. Anderson, A study of arc strong connectivity of digraphs, Ph.D. dissertation, West Virginia University, 2017.
   Google Scholar
• J. Anderson, H.-J. Lai, X. Lin, and M. Xu, On k-maximal strength digraphs, J. Graph Theory 84 (2017), pp. 17–25.
   Web of Science ®Google Scholar
• J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, 2nd ed., Springer-Verlag, London, 2009.
   Google Scholar
• V. Batagelj and M. Zaversnik, An algorithm for cores decomposition of networks, preprint (2003). Available at arXiv preprint cs/0310049.
   Google Scholar
• J.A. Bondy and U.S.R. Murty, Graph Theory, Springer, New York, 2008.
   Google Scholar
• P. Erdös, On the structure of linear graphs, Israel J. Math. 1 (1963), pp. 156–160.
   Web of Science ®Google Scholar
• P. Erdös and A. Rényi, On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutató Int. K‘´ozl. 5 (1960), pp. 17–61.
   Google Scholar
• A.H. Esfahanian, Generalized measures of fault tolerance with application to N-cube networks, IEEE Trans. Comput. 38 (1989), pp. 1586–1591.
   Web of Science ®Google Scholar
• A.H. Esfahanian and S.L. Hakimi, On computing a conditional edge-connectivity of a graph, Inf. Process. Lett. 27 (1988), pp. 195–199.
   Web of Science ®Google Scholar
• S. Even, Graph Algorithms, Computer Science Press, Woodland Hills, CA, 1979.
   Google Scholar
• H.N. Gabow, A matroid approach to finding edge-connectivity and packing arborescences, J. Comput. Syst. Sci. 50(2) (1995), pp. 259–273.
   Web of Science ®Google Scholar
• H.N. Gabow, Using expander graphs to find vertex connectivity, J. Assoc. Comput. Mach. 53 (2006), pp. 800–844.
   Web of Science ®Google Scholar
• Z. Galil, Finding the vertex connectivity of graphs, SIAM J. Comput. 9(1) (1980), pp. 197–199.
   Web of Science ®Google Scholar
• C. Giatsidis, D. Thilikos, and M. Vazirgiannis, Evaluating cooperation in communities with the k-core structure, in 2011 International Conference on Advances in Social Networks Analysis and Mining (ASONAM), IEEE, Kaohsiung, Taiwan, 2011, pp. 87–93.
   Google Scholar
• A.M. Hobbs, Network survivability, in Applications of Discrete Mathematics, J.G. Michaels and K.H. Rosen, eds., McGraw-Hill, Inc., New York, 1991, pp. 332–353.
   Google Scholar
• T.R. Jensen and B. Toft, Graph Coloring Problems, Wiley and Sons, New York, 1995, pp. 210–211.
   Google Scholar
• P. Li, H.-J. Lai, and M. Xu, Disjoint spanning arborescences in k-arc-strong digraphs, Ars Combin., accepted.
   Google Scholar
• D.R. Lick and A.T. White, k-degenerate subgraphs, Canad. J. Math. 22 (1970), pp. 1082–1096.
   Google Scholar
• X. Lin, S. Fan, H.-J. Lai, and M. Xu, On the lower bound of k-maximal digraphs, Discrete Math. 339 (2016), pp. 2500–2510.
   Web of Science ®Google Scholar
• D.W. Matula, A min-max theorem for graphs with application to graph coloring, SIAM Rev. 10(168) (1968), pp. 481–482.
   Google Scholar
• D.W. Matula, The cohesive strength of graphs, in The Many Facets of Graph Theory, G. Chartrand and S.F. Kapoor, eds., Lecture Notes in Mathematics, No. 110, Springer-Verlag, Berlin, 1969, pp. 215–221.
   Google Scholar
• D.W. Matula, K-components, clusters, and slicings in graphs, SIAM J. Appl. Math. 22 (1972), pp. 459–480.
   Web of Science ®Google Scholar
• D.W. Matula, Subgraph connectivity number of a graph, in Theory and Applications of Graphs, Y. Alavi and D.R. Ricks, eds., Lecture Notes in Mathematics, No. 642, Springer-Verlag, Berlin, 1978, pp. 371–383.
   Google Scholar
• J.G. Oxley, Colouring, packing and the critical problem, Quart. J. Math. Oxford Ser. (2) 29 (1978), pp. 11–22.
   Web of Science ®Google Scholar
• B. Pitte, J. Spencer, and N. Wormald, Sudden emergence of a giant k-core in a random graph, J. Comb. Theory Ser. B 67 (1996), pp. 111–151.
   Web of Science ®Google Scholar
• C.-P. Schnorr, Bottlenecks and edge connectivity in unsymmetrical networks, SIAM J. Comput. 8(2) (1979), pp. 265–274.
   Web of Science ®Google Scholar
• S.B. Seidman, Network structure and minimum degree, Soc. Networks 5(3) (1983), pp. 269–287.
   Web of Science ®Google Scholar
• G. Szekeres and H.S. Wilf, An inequality for the chromatic number of a graph, J. Comb. Theory 4 (1968), pp. 1–3.
   Google Scholar
• R. Tarjan, Depth-first search and linear graph algorithms, SIAM J. Comput. 2 (1972), pp. 146–160.
   Google Scholar
• J.M. Xu, Super or restricted connectivity of graphs, a survey, preprint.
   Google Scholar