1. Moo Young Sohn,
Title: A characterization of planar graphs with small diameter.
Abstract: The graphs that arise from such physical networks are usually
planar. An important applications of planar graphs is in designing
and construction of electrical circuits. So it is sometimes
important to minimize the amount of nonplanarity. Planar graphs with
small diameter are often important in applications. What is the
characterization of regular planar graphs with diameter 2? In this
talk, We shall deal with the problem of chracterization of regular
planar graph with diameter two by using elementary method.
2. Changwoo Lee,
Title: The Expected Independent Domination Number of a Random Recursive Tree
Abstract: We derive a formula for the expected value of the independent
domination number of a random recursive tree with n vertices and show
that the independent domination number of almost every recursive tree
with vertices is quite close to.
3. Sang-Gu Lee,
Title: The Binet Formula and Representations of $k$-generalized
Fibonacci Numbers
Abstract: We will consider a generalization of Fibonacci sequence, which is
called the k-generalized Fibonacci sequence for positive integer k >=
2. In this lecture, we will derive a generalized Binet formula for
the k-generalized Fibonacci sequence by using the determinant and we
give several combinatorial representations of k-generalized Fibonacci
numbers. This include five different representations of k-generalized
Fibonacci sequence.
4. Sangwook Ree,
Title : On Bipartite Tournament Matrices
Abstract: A tournament is the record of a round-robin competition between
players. It is combinatorially interesting and represented by a digraph
whose adjacency matrix is called a tournament matrix. Tournament
matrices enjoy many interesting combinatorial properties. They can be
studied combinatorial matrix theoretically as well as graph
theoretically. By grouping players to teams, we get a generalization of
tournaments and tournament matrices, which we call respectively
multipartite tournaments and multipartite toutnament matrices. We look
at the spectral bounds of bipartite tournament matrices, that is,
tournament matrices of two teams, with arbitrary team size. We see when
bipartite matrices exist and how players and teams of the matrices are
evenly ranked. We show that a bipartite tournament matrix can be both
regular and normal when and only when it has the same team size. We also
find the condition for the variance of the Perron vector of the
bipartite tournament matrix to vanish.
5. Sungchul Lee,
Title : The construction of minimal spanning tree and the strong limit laws.
Abstract : Let K_n be the complete graph with vertex set and edge set . For
each edge $e$ in $E_n$ we attach an weight $U(e)$ where $\{U(e):e\in
E_n\}$ are iid uniform random variables on the unit interval $[0,1]$. A
minimal spanning tree on $K_n$ is a spanning tree $T_n$ on $V_n$ such
that $\sum_{e \in T_n} U(e) = \min \{ \sum_{e \in T} U(e) : T \mbox{ a
spanning tree on $V_n$} \}$. In this talk we establish the large
deviation for the length, the number of vertices of degree $\al$, the
number of edges of ${\cal T}(K_n)$ with weight at most $t/n$, by
introducing a new algorithm for the construction of minimal spanning
tree and estimating the corresponding moment generating function, and
hence obtain the strong limit laws.
6. Chung-Nim Lee,
Title : Counting Geodesic Paths in the n-Dimensional Digital Space
Abstract :Between two points of the n-dimensional euclidean space, there
is a unique geodesic path. However there are n different geodesic
paths in the discrete space of n dimensional digital space depending
on the possible n different metric functions. We address the problem
of counting the number of geodesic paths between two given points in
each metric function. This problem has been solved by works by
Rosenfeld and his colleagues for dimension two, and Goh and his
colleagues for dimension three.
Applications are found in digital image processing.
7. Junho Song,
Title : An Asymptotic Formula for $\exp(\frac{x}{1-x})$
Abstract : We show that $G(x)=e^{x/(1-x)}-1$ is the exponential generating
function for the labeled digraphs whose weak components are transitive
tournaments and derive both a recursive formula and an explicit
formula for the number of them on $n$ vertices. Moreover, we
investigate the asymptotic behavior for the coefficients of $G(x)$
using Hayman's method.
8. Jin Ho Kwak,
Title : Combinatorial Versions of Hurwitz Classification Theorem for
Branched Surface Coverings and Related Enumeration Problems
Abstract : In this talk, we aim to give new versions of Hurwitz Theorems
for the classification and the existence of branched surface coverings
and also to give new combinatorial proofs of them. As results, we can
drive several enumeration formulas for some kinds of branched surface
coverings, like as regular coverings. For example, The number of
nonisomorphic $n$-fold branched coverings of a given closed surface
can be determined by the number of nonisomorphic $n$-fold unbranched
coverings of the surface and the number of nonisomorphic $n$-fold
graph coverings of a suitable bouquet of circles. The same thing is
also true for regular branched coverings. Some explicit enumeration of
them are also possible.
9. Suk-Geun Hwang,
Title : Genaralized Hessenberg matrices and expansion of bipartite graphs
Abstract : Genelized Hessenberg matrices are those (0,1)-matrices which are
incidence matrices of bipartite fraphs obtained from the connected
graph with exactly one edge on two vertices by so called successive
copying rows or columns. In this talk we discuss about a new metod of
constructing generalized Hessenberg matrices by graph theoretical
means, and investigate some properties of combinatorial concepts in
connection with generalized Hessenberg matrices.
10. Sung-Yell Song
Title: Enumeration of certain biological codes
Abstract : We count the spanning time for certain abstract biological
codes by using the methods of generating functions and recursion. We
derive several enumeration formulas.
11. Hyun Kwang Kim
Title: On Regular Polytope Numbers
Abstract : A classical theorem of Lagrange says that every natural number
can be written as a sum of four squares. We can generalize this
beautiful result in two ways. The one way is a horizontal
generalization (Cauchy's polygonal number theorem) which says that
every natural number can be written as a sum of k k-gonal numbers. The
other way is a vertical generalization (Hilbert-Waring problem) which
states that every natural number can be written as a sum of 4 squares,
9 cubes, 19 fourth powers, 37 fifth powers,and so on. In this talk we
shall consider a horizontal generalization of Hilbert-Waring problem,
or equivalently, a vertical generalization of Cauchy's polygonal
number theorem. More precisely, we shall associate to each regular
polytope a sequence of natural numbers which we shall call regular
polytope numbers, and consider the problem of expressing natural
number as a sum of regular polytope numbers. The way of construting
regular polytope numbers as well as numerical data will be presented.
12. Sungpyo Hong
Title : Bipartite graph bundles with connected fibers
Abstract : The isomorphism classes of graph bundles and graph coverings
over a finite connected simple graph G have been enumerated by Kwak
and Lee. Recently, Archdeacon, at al, characterized bipartite
coverings of G and enumerated the isomorphism classes of regular
2p-fold bipartite coverings of G, when G is nonbipartite. In this
talk, we characterize bipartite graph bundles over G and derive some
enumeration formulas of the isomorphism classes of them when the fiber
is a connected bipartite graph. As an application, we compute the
exact numbers of the isomorphism classes of bipartite graph bundles
over G when the fiber is the path P_n or the cycle C_n.
13. Suh-Ryung Kim
Title: On graph inquality $\theta(G^m) \leq \theta(G)$
Abstract : In this talk, we present some results on the graph inequality
$\theta (G^m) \leq \theta(G)$ where $\theta(G)$ is the edge clique
cover number of a graph $G$. We show that any graph $G$ with at most
$\theta(G)$ vertices satisfies $\theta (G^2) \leq \theta(G)$. Among
the graphs with more than $\theta (G)$ vertices, we find some chordal
graphs violating the inequality and show that dually chordal graphs
and power-chordal graphs satisfy the inequality. We show that
$\theta(G^{2l+1}) \leq \theta(G)$ for any simple graph $G$ and
construct a graph not satisfying $\theta(G^{2l}) \leq \theta(G)$. We
also give an exact formula computing $\theta (T^m)$ for a tree $T$.
14. Han Hyuk Cho
Title: Perfect minus dominations and public key systems
Abstract : Finding perfect minus domination is a NP-complete problem, and
its application to cryptosystem is an interesting application.
Finding perfect minus domination is related to finding a pair of
disjoint perfect dominations. In this paper, we consider the perfect
minus domination in cubic graph, and the public key crypto-system
related to the perfect minus domination. We also consider the possible
key attack and message attack related to the crypto-system.
15. Jaeun Lee
Title: Distributions of regular branched surface coverings
Abstract : For the question: In how many different ways can a given
surface be a branched covering of another given surface, there are
several partial answers by Kwak, Lee et al: enumerating the
equivalence classes of regular branched prime-fold coverings of
surfaces, and under the condition that the covering transformation
group is the dihedral group, or the direct sum of m copies of the
cyclic group of order prime. Recently, Kwak et al. enumerated the
number of equivalence classes of branched orientable A-coverings of an
nonorientable surface, but the covering surface is not specified when
the covering transformation group A is a finite abelian group. In
this talk, we apply Jones's result to determine the distribution of
the branched A-coverings of an orientable surface when A is any finite
group. As the main result of this paper, we extend this work to
determine the distribution of the branched A-coverings of any
nonorientable surface when A is any finite group.
16. Yoomi Rho,
Title : An Extremal Problem concerning Graphs not containing $K_t$ and
$K_{t,t}$
Abstract : We consider the following problem. Let $t$ and $n$ be positive
integers with $n\geq t\geq 2$. Determine the maximum number of edges
of a graph of order $n$ that contains neither $K_t$ nor $K_{t,t}$ as a
subgraph. For $n<2t$, it is solved by Tur\'{a}n's theorem and for
$n=2t$, by Brualdi and Mellendorf. We solve it for $n=2t+1$.
17. Vince Grolmusz
Title: Constructing Set-Systems with Prescribed Intersection Sizes
Abstract: Let $f$ be an $n$ variable polynomial with positive integer
coefficients, and let ${\cal H}=\{H_1,H_2,\ldots,H_m\}$ be a
set-system on the $n$-element universe. We define set-system
$f({\cal H})=\{G_1,G_2,\ldots,G_m\}$, and prove that
$f(H_{i1}\cap H_{i2}\cap\ldots\cap H_{ik})=|G_{i1}\cap
G_{i2}\cap\ldots\cap G_{ik}|$, for any $1\leq k\leq m$, where
$f(H_{i1}\cap H_{i2}\cap\ldots\cap H_{ik})$ denotes the value
of $f$ on the characteristic vector of $H_{i1}\cap
H_{i2}\cap\ldots\cap H_{ik}$.
The construction of $f({\cal H})$ is a straightforward
polynomial--time algorithm from ${\cal H}$ and polynomial $f$.
In this paper we use this algorithm for constructing
set-systems with prescribed intersection sizes modulo an
integer.
As a by-product of our method, some Ray-Chaudhuri--Wilson-like
theorems are proved.
18. Mikl\'os Ruszink\'o
Title: Superimposed codes by Ruszinko et. al.
Abstract: A family of subsets of an $n$-set is a binary superimposed
code if no set is covered by the union of $r$ others. We will
discuss the extremal properties of such families in binary
regular and non-regular cases. We will also show the
connections of these codes to distributed computing. Th
geometric version of this problem will be also
investigated. Most of the results were obtained jointly with
Zolt\'an F\"uredi.
19. Andr\'as Luk\'acs
Title: Concepts for strong negative dependence of several
binary-valued random variables
Abstract: In the talk some concept of mutual negative dependence of
binary-valued random variables are considered. These
properties are enhancement of the pairwise negative
correlations of random variables. The main concepts are the
usual negative association and the van den Berg-Kesten
property, both a possible counterpart of the positive
association (FKG inequality). Examples, counter-examples,
and conjectures are presented.