Source author record

Young Soo Kwon

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.GT math.GN math.GR

Catalog footprint

Research overview

14works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

On oriented $m$ -semiregular representations of finite groups about valency two

Given a group $G$ , an {\em $m$ -Cayley digraph $\G$ over $G$ } is a digraph that has a group of automorphisms isomorphic to $G$ acting semiregularly on the vertex set with $m$ orbits. We say that $G$ admits an {\em oriented $m$ -semiregular representation} (O $m$ SR for short), if there exists a regular $m$ -Cayley digraph $\G$ over $G$ such that $\G$ is oriented and its automorphism group is isomorphic to $G$ . In particular, O $1$ SR is also named as ORR. Verret and Xia gave a classification of finite simple groups admitting an ORR of valency two in [Ars Math. Contemp. 22 (2022), \#P1.07]. Let $m\geq 2$ be an integer. In this paper, we show that all finite groups generated by at most two elements admit an O $m$ SR of valency two except four groups of small orders. Consequently, a classification of finite simple groups admitting an O $m$ SR of valency two is obtained.

preprint2015arXiv

Classification of reflexibile regular Cayley maps for dihedral groups

In this paper, we classify reflexible regular Cayley maps for dihedral groups.

preprint2015arXiv

Regular Cayley maps on dihedral groups with the smallest kernel

Let $\mathcal{M}=CM(D_n,X,p)$ be a regular Cayley map on the dihedral group $D_n$ of order $2n, n \ge 2,$ and let $π$ be the power function associated with $\mathcal{M}$ . In this paper it is shown that the kernel Ker $(π)$ of the power function $π$ is a dihedral subgroup of $D_n$ and if $n \ne 3,$ then the kernel Ker $(π)$ is of order at least $4$ . Moreover, all $\mathcal{M}$ are classified for which Ker $(π)$ is of order $4$ . In particular, besides $4$ sporadic maps on $4,4,8$ and $12$ vertices respectively, two infinite families of non- $t$ -balanced Cayley maps on $D_n$ are obtained.

preprint2014arXiv

Degree distributions for a class of Circulant graphs

We characterize the equivalence and the weak equivalence of Cayley graphs for a finite group $\C{A}$. Using these characterizations, we find degree distribution polynomials for weak equivalence of some graphs including 1) circulant graphs of prime power order, 2) circulant graphs of order $4p$ , 3) circulant graphs of square free order and 4) Cayley graphs of order $p$ or $2p$ . As an application, we find an enumeration formula for the number of weak equivalence classes of circulant graphs of prime power order, order $4p$ and square free order and Cayley graphs of order $p$ or $2p$ .

preprint2013arXiv

Chromatic-choosability of the power of graphs

The $k$ th power $G^k$ of a graph $G$ is the graph defined on $V(G)$ such that two vertices $u$ and $v$ are adjacent in $G^k$ if the distance between $u$ and $v$ in $G$ is at most $k$ . Let $χ(H)$ and $χ_l(H)$ be the chromatic number and the list chromatic number of $H$ , respectively. A graph $H$ is called {\em chromatic-choosable} if $χ_l (H) = χ(H)$ . It is an interesting problem to find graphs that are chromatic-choosable. A natural question raised by Xuding Zhu (2012) is whether there exists a constant integer $k$ such that $G^k$ is chromatic-choosable for every graph $G$ . Motivated by the List Total Coloring Conjecture, Kostochka and Woodall (2001) asked whether $G^2$ is chromatic-choosable for every graph $G$ . Kim and Park (2013) answered the Kostochka and Woodall's question in the negative by finding a family of graphs whose squares are complete multipartite graphs with partite sets of equal and unbounded size. In this paper, we answer Zhu's question by showing that for every integer $k \geq 2$ , there exists a graph $G$ such that $G^k$ is not chromatic-choosable. Moreover, for any fixed $k$ we show that the value $χ_l(G^k) - χ(G^k)$ can be arbitrarily large.

preprint2012arXiv

Banded surfaces, banded links, band indices and genera of links

Every link is shown to be presentable as a boundary of an unknotted flat banded surface. A (flat) banded link is defined as a boundary of an unknotted (flat) banded surface. A link's (flat) band index is defined as the minimum number of bands required to present the link as boundaries of an unknotted (flat) banded surface. Banded links of small (flat, respectively) band index are considered here. Some upper bounds are provided for these band indices of a link using braid representatives and canonical Seifert surfaces of the link. The relation between the band indices and genera of links is studied and the band indices of pretzel knots are calculated.

preprint2012arXiv

Enumerations of finite topologies associated with a finite graph

The number of topologies and non-homeomorphic topologies on a fixed finite set are now known up to $n=18$ , $n=16$ but still no complete formula yet (Sloane). There are one to one correspondence among topologies, preorder and digraphs. In this article, we enumerate topologies and non-homeomorphic topologies whose underlying graph is a given finite graph.

preprint2011arXiv

A note on the existence of an alternating sign on a spanning tree of graphs

For a spanning tree T of a connected graph G and for a labelling ϕ: E(T) \rightarrow {+, -}, ϕis called an alternating sign on a spanning tree T of a graph G if for any cotree edge e \in E(G)-E(T), the unique path in T joining both end vertices of e has alternating signs. In the present note, we prove that any graph has a spanning tree T and an alternating sign on T.

preprint2011arXiv

Classification of nonorientable regular embeddings of Hamming graphs

By a regular embedding of a graph K in a surface we mean a 2-cell embedding of K in a compact connected surface such that the automorphism group acts regularly on flags. In this paper, we classify the nonorientable regular embeddings of the Hamming graph H(d,n). We show that there exists such an embedding if and only if n=2 and d=2, or n=3 or 4 and d>0, or n=6 and d=1 or 2. We also give constructions and descriptions of these embeddings.

preprint2011arXiv

The distinguishing numbers of merged Johnson graphs

In present article, we determine the distinguishing number of the merged Johnson graphs which are generalization of both the Kneser graphs and of the Johnson graphs.

preprint2010arXiv

Classification of nonorientable regular embeddings of complete bipartite graphs

A 2-cell embedding of a graph $G$ into a closed (orientable or nonorientable) surface is called regular if its automorphism group acts regularly on the flags - mutually incident vertex-edge-face triples. In this paper, we classify the regular embeddings of complete bipartite graphs $K_{n,n}$ into nonorientable surfaces. Such regular embedding of $K_{n,n}$ exists only when $n = 2p_1^{a_1}p_2^{a_2}... p_k^{a_k}$ (a prime decomposition of $n$ ) and all $p_i \equiv \pm 1 (\mod 8)$ . In this case, the number of those regular embeddings of $K_{n,n}$ up to isomorphism is $2^k$ .

preprint2010arXiv

On the existence problem of the total domination vertex critical graphs

The existence problem of the total domination vertex critical graphs has been studied in a series of articles. The aim of the present article is twofold. First, we settle the existence problem with respect to the parities of the total domination number m and the maximum degree Delta : for even m except m=4, there is no m-gamma_t-critical graph regardless of the parity of Delta; for m=4 or odd m \ge 3 and for even Delta, an m-gamma_t-critical graph exists if and only if Delta \ge 2 \lfloor \frac{m-1}{2}\rfloor; for m=4 or odd m \ge 3 and for odd Delta, if Delta \ge 2\lfloor \frac{m-1}{2}\rfloor +7, then m-gamma_t-critical graphs exist, if Delta < 2\lfloor \frac{m-1}{2}\rfloor, then m-gamma_t-critical graphs do not exist. The only remaining open cases are Delta = 2\lfloor \frac{m-1}{2}\rfloor +k, k=1, 3, 5. Second, we study these remaining open cases when m=4 or odd m \ge 9. As the previously known result for m = 3, we also show that for Delta(G)= 3, 5, 7, there is no 4-gamma_t-critical graph of order Delta(G)+4. On the contrary, it is shown that for odd m \ge 9 there exists an m-gamma_t-critical graph for all Delta \ge m-1.

preprint2007arXiv

A classification of prime-valent regular Cayley maps on some groups

A Cayley map is a 2-cell embedding of a Cayley graph into an orientable surface with the same local orientation induced by a cyclic permutation of generators at each vertex. In this paper, we provide classifications of prime-valent regular Cayley maps on abelian groups, dihedral groups and dicyclic groups. Consequently, we show that all prime-valent regular Cayley maps on dihedral groups are balanced and all prime-valent regular Cayley maps on abelian groups are either balanced or anti-balanced. Furthermore, we prove that there is no prime-valent regular Cayley map on any dicyclic group.

preprint2007arXiv

The weighted complexity and the determinant functions of graphs

The complexity of a graph can be obtained as a derivative of a variation of the zeta function or a partial derivative of its generalized characteristic polynomial evaluated at a point [\textit{J. Combin. Theory Ser. B}, 74 (1998), pp. 408--410]. A similar result for the weighted complexity of weighted graphs was found using a determinant function [\textit{J. Combin. Theory Ser. B}, 89 (2003), pp. 17--26]. In this paper, we consider the determinant function of two variables and discover a condition that the weighted complexity of a weighted graph is a partial derivative of the determinant function evaluated at a point. Consequently, we simply obtain the previous results and disclose a new formula for the Bartholdi zeta function. We also consider a new weighted complexity, for which the weights of spanning trees are taken as the sum of weights of edges in the tree, and find a similar formula for this new weighted complexity. As an application, we compute the weighted complexities of the product of the complete graphs.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Young Soo Kwon

Research overview

Is this your work?

14 publications

On oriented $m$ -semiregular representations of finite groups about valency two

Classification of reflexibile regular Cayley maps for dihedral groups

Regular Cayley maps on dihedral groups with the smallest kernel

Degree distributions for a class of Circulant graphs

Chromatic-choosability of the power of graphs

Banded surfaces, banded links, band indices and genera of links

Enumerations of finite topologies associated with a finite graph

A note on the existence of an alternating sign on a spanning tree of graphs

Classification of nonorientable regular embeddings of Hamming graphs

The distinguishing numbers of merged Johnson graphs

Classification of nonorientable regular embeddings of complete bipartite graphs

On the existence problem of the total domination vertex critical graphs

A classification of prime-valent regular Cayley maps on some groups

The weighted complexity and the determinant functions of graphs

See the researcher in context

Building this map preview

Young Soo Kwon

Research overview

Is this your work?

14 publications

On oriented mmm-semiregular representations of finite groups about valency two

Classification of reflexibile regular Cayley maps for dihedral groups

Regular Cayley maps on dihedral groups with the smallest kernel

Degree distributions for a class of Circulant graphs

Chromatic-choosability of the power of graphs

Banded surfaces, banded links, band indices and genera of links

Enumerations of finite topologies associated with a finite graph

A note on the existence of an alternating sign on a spanning tree of graphs

Classification of nonorientable regular embeddings of Hamming graphs

The distinguishing numbers of merged Johnson graphs

Classification of nonorientable regular embeddings of complete bipartite graphs

On the existence problem of the total domination vertex critical graphs

A classification of prime-valent regular Cayley maps on some groups

The weighted complexity and the determinant functions of graphs

See the researcher in context

Building this map preview

On oriented $m$ -semiregular representations of finite groups about valency two