We present two results about structural properties of delta-matroids which come from graphs and other two results about obtaining vertex-minors and pivot-minors while preserving the connectivities.
First, we introduce delta-graphic matroids and study their structural properties to characterize the class of delta-matroids that are twisted matroids and graphic delta-matroids. We give a structural characterization of delta-graphic matroids by providing the decomposition theorem. We also prove that every minor-minimal matroid which is not delta-graphic has at most 48 elements.
Second, we introduce Γ-graphic delta-matroids defined from graphs whose vertices are labelled by elements of an abelian group Γ. We provide a polynomial-time algorithm to solve the separation problem on these delta-matroids, and as an application, we present polynomial-time algorithms for two graph problems. We further investigate various properties of Γ-graphic delta-matroids.
Third, we show that for any two pairs (Q, R) and (S, T ) of disjoint sets of vertices, if a simple graph is large, then there exist two ways to reduce the graph by a vertex-minor operation while preserving the connectivity between Q and R, and the connectivity between S and T.
Finally, we prove that if a sequentially 3-rank-connected graph is large, then there exists a sequen- tially 3-rank-connected vertex-minor with one fewer number of vertices.
이 논문에서는 그래프로 정의되는 delta-matroid의 성질에 대한 두 결과와 그래프의 연결성을 유지한 채로 vertex-minor 혹은 pivot-minor를 얻는 방법들에 관한 두 결과를 소개한다.
첫 번째로, graphic delta-matroid이면서 twisted matroid인 delta-matroid의 구조적 성질을 관찰하기 위하여, delta-graphic matroid라는 새로운 종류의 matroid를 정의하였고 구조적 성질을 탐구하였다. 먼저 delta-graphic matroid의 분해정리를 증명하였고, delta-graphic이 아니면서 minor 관계로 극소인 delta- matroid의 크기가 48 이하임을 증명하였다.
두 번째로 가환군 Γ에 대해서, 모든 꼭짓점에 Γ의 원소가 부여된 그래프로부터 만들어지는 Γ-graphic delta-matroid를 정의하였다. 이 delta-matroid에 관해서 분리 문제를 풀기 위한 다항식 시간 알고리즘을 고안하였고, 이에 대한 응용으로 여러 그래프 문제들의 다항식 시간 알고리즘을 제시하였다. 마지막으로 Γ-graphic delta-matroid의 다른 다양한 성질도 연구하였다.
세 번째로 임의의 두 쌍의 서로소인 꼭짓점 집합 (Q,R)과 (S,T)에 대하여, 그래프가 충분히 크면 Q와 R 사이의 연결성과 S와 T 사이의 연결성을 유지하는 최소 두 가지 방법의 vertex-minor 연산이 존재함을 증명하였다.
마지막으로 sequentially 3-rank-connected인 그래프가 충분히 크면 꼭짓점 개수가 하나 적으면서 여전히 sequentially 3-rank-connected인 vertex-minor를 찾을 수 있다는 것을 증명하였다.