Game connectivity of graphs. (English) Zbl 1447.05138
Summary: In this paper, we introduce a new game invariant of graphs, called game connectivity, which is related to the connectivity of graphs. We investigate many fundamental and significant topics of the game connectivity of graphs, and propose many open problems and conjectures.
MSC:
| 05C57 | Games on graphs (graph-theoretic aspects) |
| 91A43 | Games involving graphs |
| 05C40 | Connectivity |
| 05C35 | Extremal problems in graph theory |
References:
| [1] | Bodlaender, H. L., On the complexity of some coloring games, Internat. J. Found. Comput. Sci., 2, 133-147 (1991) · Zbl 0753.05061 |
| [2] | Brešar, B.; Klavžar, S.; Rall, D. F., Domination game and an imagination strategy, SIAM J. Discrete Math., 24, 979-991 (2010) · Zbl 1223.05189 |
| [3] | Diestel, R., (Graph Theory. Graph Theory, Graduate Texts in Mathematics, vol. 173 (2010), Springer) · Zbl 1204.05001 |
| [4] | Esfahanian, A. H., Connectivity algorithms, Encyclopedia Math. Appl., 147, 268-281 (2013) |
| [5] | Even, S., An algorithm for determining whether the connectivity of a graph is at least \(k\), SIAM J. Comput., 4, 393-396 (1975) · Zbl 0311.05133 |
| [6] | Even, S.; Taijan, R. E., Network flow and testing graph connectivity, SIAM J. Comput., 4, 507-518 (1975) · Zbl 0328.90031 |
| [7] | Fàbrega, J.; Fiol, M. A., Further topics in connectivity, (Handbook of Graph Theory (2004), CRC Press: CRC Press London, New York), 300-329 |
| [8] | Gravier, S.; Meslem, K.; Schmidt, S.; Slimani, S., A new game invariant of graphs: the game distinguishing number, Discrete Math. Theor. Comput. Sci., 19 (2017) · Zbl 1400.05158 |
| [9] | Hellwig, A.; Volkmann, L., Maximally edge-connected and vertex-connected graphs and digraphs: A survey, Discrete Math., 308, 3265-3296 (2008) · Zbl 1160.05038 |
| [10] | Kanevsky, A., Finding all minimum-size separating vertex sets in a graph, Networks, 23, 533-541 (1993) · Zbl 0798.90042 |
| [11] | Loeb, S.; Mahoney, T.; Reiniger, B.; Wise, J., Dynamic coloring parameters for graphs with given genus, Discrete Appl. Math., 235, 129-141 (2018) · Zbl 1375.05098 |
| [12] | Mader, W., Connectivity and edge-connectivity in finite graphs, (Bollobás, B., Surveys in Combinatorics. Surveys in Combinatorics, London Math. Soc. Lecture Note Ser., vol. 38 (1979)), 66-95 · Zbl 0404.05040 |
| [13] | N. Matsumoto, T. Nakamigawa, Game edge-connectivity of graphs, in preparation. · Zbl 1465.05114 |
| [14] | Oellermann, O. R., Connectivity and edge-connectivity in graphs: a survey, Congr. Numer., 116, 231-252 (1996) · Zbl 0905.05044 |
| [15] | Schaefer, T. J., On the complexity of some two-person perfect-information games, J. Comput. System Sci., 16, 185-225 (1978) · Zbl 0383.90112 |
| [16] | Whitney, H., Congruent graphs and the connectivity of graphs, Amer. J. Math., 54, 150-168 (1932) · JFM 58.0609.01 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
