[그래프이론 (Graph Theory) 문제풀이] Determine κ and κ′ for each graph below.

그래프이론 (Graph Theory) 문제를 풀어보자. 이번에 풀어볼 문제는 “Determine κ and κ′ for each graph below.” 이다.

그래프이론 (Graph Theory) 문제풀이

이번에 풀고자 하는 그래프이론 (Graph Theory) 문제는 아래와 같다.

Determine κ and κ′ for each graph below.

여기서 말하는 그래프는 아래에 두개가 있다.

(풀이)
사실… 난 이거 어떻게 풀어야 되는지 모르겠다. 아래와 같이 vertex cut의 vertex는 보라색 동그라미로 표시했다. edge cut의 edge는 빨간색으로 표시했다.

참고글

[그래프이론 (Graph Theory) 문제풀이] For each n ∈ N, find an n-vertex graph such that κ′(G) > κ(G).

[그래프이론 (Graph Theory)] For each even n ≥ 16, construct a 3-regular simple graph with n vertices having no 1-factor.

[그래프이론(Graph Theory) 문제풀이] Let G be a simple graph with diameter at least 4. Prove that complement of G has diameter at most 2.

[그래프이론(Graph Theory) 문제풀이] For each k, list the isomorphism classes of trees with maximum degree k and at most six vertices. Do the same for diameter k. (Explain why there are no others.)

문제출처- 광주과학기술원 최정옥 교수님의 “그래프 이론” 수업 (2023년 가을학기) 중 Homework 6 문제