|
|
Pure Mathematics 2025
极小3-连通平面图的构造
|
Abstract:
设
是由满足以下条件的3-连通平面二部图所组成的图类：
的一部是3度点的集合，另外一部是度至少为4的点的集合。本文证明了若G是极小3-连通平面图且G中不存在边e使得G/e或G/e\f是极小3-连通平面图，则
，这里f与e相邻于一个3度点。
Let
be a set of minimally 3-connected planer graphs such that every member of
is a bipartite graph with one parts of vertices of degree three and the other parts of degree at least four. Let G be a minimally 3-connected planar graph. This paper show that if G has no edge e such that either G/e or G/e\f is minimally 3-connected planar graph then
; here e and f are two edges incident to a vertex of degree 3.
| [1] | Mader, W. (1972) Ecken Vom Gradn in Minimalenn-Fach Zusammenhangenden Graphen. Archiv der Mathematik, 23, 219-224. https://doi.org/10.1007/bf01304873 |
| [2] | Ota, K. and Saito, A. (1988) Non-Separating Induced Cycles in 3-Connected Graphs. Scientia Series A, 2, 101-105. |
| [3] | Dean, N., Hemminger, R.L. and Ota, K. (1989) Longest Cycles in 3‐Connected Graphs Contain Three Contractible Edges. Journal of Graph Theory, 13, 17-21. https://doi.org/10.1002/jgt.3190130105 |
| [4] | Dawes, R.W. (1986) Minimally 3-Connected Graphs. Journal of Combinatorial Theory, Series B, 40, 159-168. https://doi.org/10.1016/0095-8956(86)90074-2 |
| [5] | Coullard, C.R. and Oxley, J.G. (1992) Extensions of Tutte’s Wheels-And-Whirls Theorem. Journal of Combinatorial Theory, Series B, 56, 130-140. https://doi.org/10.1016/0095-8956(92)90012-m |
| [6] | Kingan, S.R. (2023) Deletable Edges in 3-Connected Graphs and Their Applications. arXiv:1 802.02660. |
| [7] | Dirac, G.A. (1963) Some Results Concerning the Structure of Graphs. Canadian Mathematical Bulletin, 6, 183-210. https://doi.org/10.4153/cmb-1963-019-5 |
| [8] | Mader, W. (1988) Generalizations of Critical Connectivity of Graphs. Annals of Discrete Mathematics, 38, 267-283. https://doi.org/10.1016/s0167-5060(08)70793-3 |
| [9] | Halin, R. (1969) Zur Theorie Dern-Fach Zusammenhängenden Graphen. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 33, 133-164. https://doi.org/10.1007/bf02992931 |
| [10] | Qin, C., Geng, J., Yang, H. and Xie, X. (2025) Contractible Edges in Spanning Trees of 3-Connected Graphs. Graphs and Combinatorics, 41, Article No. 22. https://doi.org/10.1007/s00373-025-02890-0 |
