Minimal κ-connected Graphs with Small Number of Vertices of Degree κ

• Autorzy: Karpov D. V.

Identyfikatory

DOI

10.3233/FI-2016-1361

• Języki publikacji: EN

Słowa kluczowe

EN

graph connectivity; number theory; paths; cycles; topological degree; undirected graph

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 145, nr 3
• Strony: 279--312
• Opis fizyczny: Bibliogr. 14 poz., rys.

Twórcy

autor

Karpov D. V.

• St. Petersburg Department of V.A.Steklov Mathematical Institute, Fontanka 27, 191023 St.Petersburg, Russia

Bibliografia

• [1] Dirac GA. Minimally 2-connected graphs. J. Reine and Angew. Math. 1967; 268:204–216.
• [2] Plummer MD. On minimal blocks. Trans. Amer. Math. Soc. 1968; 134:85–94.
• [3] Mader W. On vertices of degree n in minimally n-connected graphs and digraphs. Combinatorics, Paul Erdös is Eighty, Budapest, 1996; 2:423–449.
• [4] Mader W. Zur Struktur minimal n-fach zusammenhängender Graphen. Abh. Math. Sem. Univ. Hamburg. 1979; 49:49–69.
• [5] Karpov DV. Minimal k-connected graphs with minimal number of vertices of degree k. Zapiski Nauchnykh Semenarov POMI. 2014; 427:41–65, in Russian. English translation: Journal of Mathematical Sciences, 2016; 212(6):654–665. doi:10.1007/s10958-016-2697-1.
• [6] Oxley JG. On some extremal connectivity results for graphs and matroids. Discrete Math. 1982; 41:181–198. doi:10.1016/0012-365X(82)90206-0.
• [7] Karpov DV. Minimal biconnected graphs. Zapiski Nauchnykh Semenarov POMI. 2013; 417:106–127, in Russian. English translation: Journal of Mathematical Sciences. 2015; 204(2):244–257. doi:10.1007/s10958-014-2199-y.
• [8] Karpov DV. The tree of cuts and minimal k-connected graphs. Zapiski Nauchnykh Semenarov POMI. 2014; 427:22–40, in Russian. English translation: Journal of Mathematical Sciences. 2016; 212(6):654–665. doi:10.1007/s10958-016-2696-2.
• [9] Mader W. Ecken Vom Gard n in minimalen n-fach zusammenhangenden Graphen. Arch. Math. (Basel). 1972; 23:219–224.
• [10] Göring F. Short proof of Menger’s Theorem. Discr. Math. 2000; 219:295–296. doi:10.1016/S0012-365X(00)00088-1.
• [11] Tutte WT. Connectivity in graphs. Toronto, Univ. Toronto Press; 1966.
• [12] Harary F. Graph theory. Addison-Wesley; 1969.
• [13] Karpov DV, Pastor AV. The structure of a decomposition of a triconnected graph. Zapiski Nauchnykh Semenarov POMI. 2011; 391:90–148, in Russian. English translation: Journal of Mathematical Sciences. 2012; 184(5):601–628. doi:10.1007/s10958-012-0885-1.
• [14] Karpov DV. Cutsets in a k-connected graph. Zapiski Nauchnykh Semenarov POMI. 2006; 340:33–60, in Russian. English translation: Journal of Mathematical Sciences. 2007; 145(3):4953–4966. doi: 10.1007/s10958-007-0330-z.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).