## Donggyu Kim (김동규) gave a talk on an analog of the theorem of Oxley and Wu on matroids for vertex-minors of graphs at the Discrete Math Seminar

On February 21, 2022, Donggyu Kim (김동규) from KAIST / IBS Discrete Mathematics Group gave a talk at the Discrete Math Seminar on an analog of the theorem of Oxley and Wu on matroids for vertex-minors of graphs. The title of his talk was “A stronger version of Tutte’s wheel theorem for vertex-minors“.

## Donggyu Kim (김동규), A stronger version of Tutte’s wheel theorem for vertex-minors

Tutte (1961) proved that every simple $3$-connected graph $G$ has an edge $e$ such that $G \setminus e$ or $G / e$ is simple $3$-connected, unless $G$ is isomorphic to a wheel. We call such an edge non-essential. Oxley and Wu (2000) proved that every simple $3$-connected graph has at least $2$ non-essential edges unless it is isomorphic to a wheel. Moreover, they proved that every simple $3$-connected graph has at least $3$ non-essential edges if and only if it is isomorphic to neither a twisted wheel nor a $k$-dimensional wheel with $k\geq2$.

We prove analogous results for graphs with vertex-minors. For a vertex $v$ of a graph $G$, let $G*v$ be the graph obtained from $G$ by deleting all edges joining two neighbors of $v$ and adding edges joining non-adjacent pairs of two neighbors of $v$. This operation is called the local complementation at $v$, and we say two graphs are locally equivalent if one can be obtained from the other by applying a sequence of local complementations. A graph $H$ is a vertex-minor of a graph $G$ if $H$ is an induced subgraph of a graph locally equivalent to $G$. A split of a graph is a partition $(A,B)$ of its vertex set such that $|A|,|B| \geq 2$ and for some $A’\subseteq A$ and $B’\subseteq B$, two vertices $x\in A$ and $y\in B$ are adjacent if and only if $x\in A’$ and $y\in B’$. A graph is prime if it has no split.

A vertex $v$ of a graph is non-essential if at least two of three kinds of vertex-minor reductions at $v$ result in prime graphs. We prove that every prime graph with at least $5$ vertices has at least two non-essential vertices unless it is locally equivalent to a cycle. It is stronger than a theorem proved by Allys (1994), which states that every prime graph with at least $5$ vertices has a non-essential vertex unless it is locally equivalent to a cycle. As a corollary of our result, one can obtain the first result of Oxley and Wu. Furthermore, we show that every prime graph with at least $5$ vertices has at least $3$ non-essential vertices if and only if it is not locally equivalent to a graph with two specified vertices $x$ and $y$ consisting of at least two internally-disjoint paths from $x$ to $y$ in which $x$ and $y$ have no common neighbor.

This is joint work with Sang-il Oum.

## Donggyu Kim (김동규), 𝝘-graphic delta-matroids and their applications

Bouchet (1987) defined delta-matroids by relaxing the base exchange axiom of matroids. Oum (2009) introduced a graphic delta-matroid from a pair of a graph and its vertex subset. We define a $\Gamma$-graphic delta-matroid for an abelian group $\Gamma$, which generalizes a graphic delta-matroid.

For an abelian group $\Gamma$, a $\Gamma$-labelled graph is a graph whose vertices are labelled by elements of $\Gamma$. We prove that a certain collection of edge sets of a $\Gamma$-labelled graph forms a delta-matroid, which we call a $\Gamma$-graphic delta-matroid, and provide a polynomial-time algorithm to solve the separation problem, which allows us to apply the symmetric greedy algorithm of Bouchet (1987) to find a maximum weight feasible set in such a delta-matroid. We also prove that a $\Gamma$-graphic delta-matroid is a graphic delta-matroid if and only if it is even. We prove that every $\mathbb{Z}_p^k$-graphic delta matroid is represented by some symmetric matrix over a field of characteristic of order $p^k$, and if every $\Gamma$-graphic delta-matroid is representable over a finite field $\mathbb{F}$, then $\Gamma$ is isomorphic to $\mathbb{Z}_p^k$ and $\mathbb{F}$ is a field of order $p^\ell$ for some prime $p$ and positive integers $k$ and $\ell$.

This is joint work with Duksang Lee and Sang-il Oum.

## Welcome Donggyu Kim (김동규), a new graduate student, and William Overman, a visiting undergraduate student in the IBS discrete mathematics group

The IBS discrete mathematics group welcomes two new students.

Donggyu Kim (김동규) is a new graduate student from July 2019 and is currently a graduate student at the department of mathematical sciences, KAIST.

William Overman is a visiting student from June 2019 to August 2019 and is currently an undergraduate student in California Institute of Technology. His research visit is sponsored by his home university. 기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209