KPPY 60

The goal is to report on some long-term work on certain combinatorial properties of knot/link diagrams of given canonical genus. These turned out to have various ramifications and applications, including (1) enumeration of alternating knots by genus, (2) words in formal alphabets (Wicks forms), (3) graph embedding problems on surfaces, (4) markings and the $sl_N$ graph polynomial, (5) hyperbolic volume of polyhedra, graphs and links. I will try to explain (at least as far as time allows) some interrelations between these topics.

The maximum subgraph problem for a fixed graph property $P$ asks: Given a graph $G$, find a subgraph $H$ of $G$ that satisfies property $P$ that has the maximum number of edges. Similarly, we can talk about maximum induced subgraph problem. The property $P$ can be planarity, acyclicity, bipartiteness, etc. We will discuss some old and new problems of this flavor, focusing on the algorithmic aspects of these problems. In particular, we will describe some old results on the maximum bipartite subgraph problem and some new results on the maximum series-parallel subgraph problem.

Let $L$ be the ring $\mathbb{Z}[x]/(x^3-4x)$. Let $G$ be the quadrangle graph and let $A_G$ be the adjacency matrix of $G$. Then $x^3-4x$ is the minimal polynomial of $A_G$. Thus $L$ is the ring related to $G$. Let $\Lambda$ be the subring of $\mathbb{Q}[x]/(x^3-4x)$ satisfying $\Lambda$ is isomorphic to $L$. In this talk, our aim is to obtain the Dirichlet series of the number of $\Lambda$-submodules of $L$. We applied Louis Solomon's works to this calculation by using computer program GAP. We will introduce how to calculate the Dirichlet series.

In this talk, we will discuss distance-hereditary graphs. Distance-hereditary graphs are exactly the graphs preserving the distance between two vertices when taking any connected induced subgraph. There are many characterizations of distance-hereditary graphs, one being that they have tree-like structure with respect to a certain "split" operation. However, there are few known theorems using this structure. We provide the following, using the tree-like structure of distance-hereditary graphs. 1. A characterization of distance-hereditary graphs having linear rank-width at most k. 2. Two variants of Bouchet's Tree Theorem to cographs and diamond-free chordal graphs. 3. A test of local equivalent in distance-hereditary graphs. This is joint work with Mamadou Kante and Isolde Idler.