기초과학연구원 이산수학그룹
In this talk, we present sufficient conditions to guarantee the invertibility of rational circulant matrices with any given size. These sufficient conditions consist of linear combinations in terms of the …
The local connectivity $ \kappa_D(r,v) $ from $ r $ to $ v $ is defined to be the maximal number of internally disjoint $r\rightarrow v $ paths in $ …
For positive integers, $r \ge 3, h \ge 1,$ and $k \ge 1$, Bollobás, Saito, and Wormald proved some sufficient conditions for an $h$-edge-connected $r$-regular graph to have a k-factor …
For a graph $H$, a graph $G$ is $H$-saturated if $G$ does not contain $H$ as a subgraph but for any $e\in E(\overline G)$, $G+e$ contains $H$. In this note, we prove …
We give a strongly polynomial-time algorithm for integer linear programs defined by integer coefficient matrices whose subdeterminants are bounded by a constant and that contain at most two nonzero entries …
$q$-analogues of quantities in mathematics involve perturbations of classical quantities using the parameter $q$, and revert to the original quantities when $q$ goes $1$. An important example is the $q$-analogues …
In the k-cut problem, we are given an edge-weighted graph and want to find the least-weight set of edges whose deletion breaks the graph into k connected components. It is …
Tree decompositions are a powerful tool in structural graph theory; they are traditionally used in the context of forbidden graph minors. Connecting tree decompositions and forbidden induced subgraphs has until …
We show that for pairs (Q,R) and (S,T) of disjoint subsets of vertices of a graph G, if G is sufficiently large, then there exists a vertex v in V(G)−(Q∪R∪S∪T) such …
We call an induced cycle of length at least four a hole. The parity of a hole is the parity of its length. Forbidding holes of certain types in a graph …