BZPEER

preprint2022arXiv

Digraphs whose m-step competition graphs are trees

In this paper, we completely characterize the digraphs of order $n$ whose $m$ -step competition graphs are star graphs for positive integers $2\leq m < n$ . This result in matrix version identifies the solution set to the matrix equation $X^m(X^T)^m= Λ_n+I_n$ for positive integers $2\leq m < n$ where $I_n$ is the identity matrix of order $n$ and $Λ_n$ is a $(0,1)$ Boolean matrix such that the first row and the first column consist of $1$ 's except $(1,1)$ -entry and the remaining entries are $0$ , which is the adjacency matrix of a star graph of order $n$ . We also derive meaningful properties of the digraphs whose $m$ -step competition graphs are trees. In the process, we extend a result of Helleloid~[Connected triangle-free $m$ -step competition graphs, Discrete Appl.\ Math.\ 145 (2005) 376--383] by showing that for all positive integers $m \geq 2$ and $n$ , the connected triangle-free $m$ -step competition graph on $n$ vertices is a tree.

preprint2022arXiv

Planarity of generalized ladder graphs

The Cartesian product of P_2 and P_n is called an n-ladder graph for a positive integer n. We call two paths P_m and P_n together with some edges each of which joins a vertex on P_m and a vertex on P_n a generalized (m,n)-ladder graph. In this paper, we completely characterize the planar generalized ladder graphs and the outerplanar generalized ladder graphs. A functigraph C(P_n ,f) is a generalized (n,n)-ladder graph. Consequently, our result solves the problem posed by A. Chen et al. (2011) to characterize planar functigraphs C(P_n ,f).

preprint2020arXiv

Counting independent sets in Riordan graphs

The notion of a Riordan graph was introduced recently, and it is a far-reaching generalization of the well-known Pascal graphs and Toeplitz graphs. However, apart from a certain subclass of Toeplitz graphs, nothing was known on independent sets in Riordan graphs. In this paper, we give exact enumeration and lower and upper bounds for the number of independent sets for various classes of Riordan graphs. Remarkably, we offer a variety of methods to solve the problems that range from the structural decomposition theorem to methods in combinatorics on words. Some of our results are valid for any graph.

preprint2016arXiv

On $(1,2)$ -step competition graphs of bipartite tournaments

In this paper, we study $(1,2)$ -step competition graphs of bipartite tournaments. A bipartite tournament means an orientation of a complete bipartite graph. We show that the $(1,2)$ -step competition graph of a bipartite tournament has at most one non-trivial component or consists of exactly two complete components of size at least three and, especially in the former, the diameter of the nontrivial component is at most three if it exists. Based on this result, we show that, among the connected non-complete graphs which are triangle-free or the cycles of which are edge-disjoint, $K_{1,4}$ is the only graph that can be represented as the $(1,2)$ -step competition graph of a bipartite tournament. We also completely characterize a complete graph and the disjoint union of two complete graphs, respectively, which can be represented as the $(1,2)$ -step competition graph of a bipartite tournament. Finally we present the maximum number of edges and the minimum number of edges which the $(1,2)$ -step competition graph of a bipartite tournament might have.

preprint2016arXiv

On the competition graphs of $d$ -partial orders

In this paper, we study the competition graphs of $d$ -partial orders and obtain their characterization which extends results given by Cho and Kim \cite{chokim} in 2005. We also show that any graph can be made into the competition graph of a $d$ -partial order for some positive integer $d$ as long as adding isolated vertices is allowed. We then introduce the notion of the partial order competition dimension of a graph and study graphs whose partial order competition dimensions are at most three.

preprint2016arXiv

On the competition graphs of $d$ -partial orders

In this paper, we study the competition graphs of $d$ -partial orders and obtain their characterization which extends results given by Cho and Kim \cite{chokim} in 2005. We also show that any graph can be made into the competition graph of a $d$ -partial order for some positive integer $d$ as long as adding isolated vertices is allowed. We then introduce the notion of the partial order competition dimension of a graph and study graphs whose partial order competition dimensions are at most three.

preprint2016arXiv

On the partial order competition dimensions of chordal graphs

Choi {\it et al.} [{J.~Choi, K.~S.~Kim, S.~-R.~Kim, J.~Y.~Lee, and Y.~Sano}: {On the competition graphs of $d$ -partial orders}, \emph{Discrete Applied Mathematics} (2015), \texttt{http://dx.doi.org/10.1016/j.dam.2015.11.004}] introduced the notion of the partial order competition dimension of a graph. It was shown that complete graphs, interval graphs, and trees, which are chordal graphs, have partial order competition dimensions at most three. In this paper, we study the partial order competition dimensions of chordal graphs. We show that chordal graphs have partial order competition dimensions at most three if the graphs are diamond-free. Moreover, we also show the existence of chordal graphs containing diamonds whose partial order competition dimensions are greater than three.

preprint2016arXiv

On the partial order competition dimensions of chordal graphs

Choi {\it et al.} [{J.~Choi, K.~S.~Kim, S.~-R.~Kim, J.~Y.~Lee, and Y.~Sano}: {On the competition graphs of $d$ -partial orders}, \emph{Discrete Applied Mathematics} (2015), \texttt{http://dx.doi.org/10.1016/j.dam.2015.11.004}] introduced the notion of the partial order competition dimension of a graph. It was shown that complete graphs, interval graphs, and trees, which are chordal graphs, have partial order competition dimensions at most three. In this paper, we study the partial order competition dimensions of chordal graphs. We show that chordal graphs have partial order competition dimensions at most three if the graphs are diamond-free. Moreover, we also show the existence of chordal graphs containing diamonds whose partial order competition dimensions are greater than three.

preprint2016arXiv

On the phylogeny graphs of degree-bounded digraphs

Hefner [K. A. S. Hefner, K. F. Jones, S. -R. Kim, R. J. Lundgren and F. S. Roberts: $(i,j)$ competition graphs, Discrete Applied Mathematics, 32, (1991) 241-262] characterized acyclic digraphs each vertex of which has inderee and outdegree at most two and whose competition graphs are interval. They called acyclic digraphs each vertex of which has inderee and outdegree at most two $(2,2)$ digraphs. In this paper, we study the phylogeny graphs of $(2,2)$ digraphs. Especially, we give a sufficient condition and necessary conditions for $(2,2)$ digraphs having chordal phylogeny graphs. Phylogeny graphs are also called moral graphs in Bayesian network theory. Our work is motivated by problems related to evidence propagation in a Bayesian network for which it is useful to know which acyclic digraphs have their moral graphs being chordal.

preprint2015arXiv

On the safe set of Cartesian product of two complete graphs

For a connected graph $G$ , a vertex subset $S$ of $V(G)$ is a safe set if for every component $C$ of the subgraph of $G$ induced by $S$ , $|C| \ge |D|$ holds for every component $D$ of $G-S$ such that there exists an edge between $C$ and $D$ , and, in particular, if the subgraph induced by $S$ is connected, then $S$ is called a connected safe set. For a connected graph $G$ , the safe number and the connected safe number of $G$ are the minimum among sizes of the safe sets and the minimum among sizes of the connected safe sets, respectively, of $G$ . Fujita et al. introduced these notions in connection with a variation of the facility location problem. In this paper, we study the safe number and the connected safe number of Cartesian product of two complete graphs. Figuring out a way to reduce the number of components to two without changing the size of safe set makes it sufficient to consider only partitions of an integer into two parts without which it would be much more complicated to take care of all the partitions. In this way, we could show that the safe number and the connected safe number of Cartesian product of two complete graphs are equal and present a polynomial-time algorithm to compute them. Especially, in the case where one of complete components has order at most four, we precisely formulate those numbers.

preprint2014arXiv

A matrix equation $X^n = aI$

In this paper, we study a matrix equation $X^n = aI$ . We factorize $X^n - aI$ based upon the factorization of $x^n - a$ and then give a necessary and sufficient condition for one of the factors to be the zero matrix.

preprint2014arXiv

On consecutive edge magic total labeling of connected bipartite graphs

Since Sedlá$\breve{\mbox{c}}$ek introduced the notion of magic labeling of a graph in 1963, a variety of magic labelings of a graph have been defined and studied. In this paper, we study consecutive edge magic labelings of a connected bipartite graph. We make a very useful observation that there are only four possible values of $b$ for which a connected bipartite graph has a $b$ -edge consecutive magic labeling. On the basis of this fundamental result, we deduce various interesting results on consecutive edge magic labelings of bipartite graphs, especially caterpillars and lobsters, which extends the results given by Sugeng and Miller.

preprint2013arXiv

On the matrix sequence $\{Γ(A^m)\}_{m=1}^\infty$ for a Boolean matrix $A$ whose digraph is linearly connected

In this paper, we extend the results given by Park {\em et al.} \cite{ppk} by studying the convergence of the matrix sequence $\{Γ(A^m)\}_{m=1}^\infty$ for a matrix $A \in \mathcal{B}_n$ the digraph of which is linearly connected with an arbitrary number of strong components. In the process for generalization, we concretize ideas behind their arguments. We completely characterize $A$ for which $\{Γ(A^m)\}_{m=1}^\infty$ converges. Then we find its limit when all of the irreducible diagonal blocks are of order at least two. We go further to characterize $A$ for which the limit of $\{Γ(A^m)\}_{m=1}^\infty$ is a $J$ block diagonal matrix. All of these results are derived by studying the $m$ -step competition graph of the digraph of $A$ .

preprint2012arXiv

Competitively tight graphs

The competition graph of a digraph $D$ is a (simple undirected) graph which has the same vertex set as $D$ and has an edge between two distinct vertices $x$ and $y$ if and only if there exists a vertex $v$ in $D$ such that $(x,v)$ and $(y,v)$ are arcs of $D$ . For any graph $G$ , $G$ together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number $k(G)$ of a graph $G$ is the smallest number of such isolated vertices. Computing the competition number of a graph is an NP-hard problem in general and has been one of the important research problems in the study of competition graphs. Opsut [1982] showed that the competition number of a graph $G$ is related to the edge clique cover number $θ_E(G)$ of the graph $G$ via $θ_E(G)-|V(G)|+2 \leq k(G) \leq θ_E(G)$ . We first show that for any positive integer $m$ satisfying $2 \leq m \leq |V(G)|$ , there exists a graph $G$ with $k(G)=θ_E(G)-|V(G)|+m$ and characterize a graph $G$ satisfying $k(G)=θ_E(G)$ . We then focus on what we call \emph{competitively tight graphs} $G$ which satisfy the lower bound, i.e., $k(G)=θ_E(G)-|V(G)|+2$ . We completely characterize the competitively tight graphs having at most two triangles. In addition, we provide a new upper bound for the competition number of a graph from which we derive a sufficient condition and a necessary condition for a graph to be competitively tight.

preprint2012arXiv

The competition hypergraphs of doubly partial orders

Since Cho and Kim (2005) showed that the competition graph of a doubly partial order is an interval graph, it has been actively studied whether or not the same phenomenon occurs for other variants of competition graph and interesting results have been obtained. Continuing in the same spirit, we study the competition hypergraph, an interesting variant of the competition graph, of a doubly partial order. Though it turns out that the competition hypergraph of a doubly partial order is not always interval, we completely characterize the competition hypergraphs of doubly partial orders which are interval.

preprint2011arXiv

Holes and a chordal cut in a graph

A set $X$ of vertices of a graph $G$ is called a {\em clique cut} of $G$ if the subgraph of $G$ induced by $X$ is a complete graph and the number of connected components of $G-X$ is greater than that of $G$ . A clique cut $X$ of $G$ is called a {\em chordal cut} of $G$ if there exists a union $U$ of connected components of $G-X$ such that $G[U \cup X]$ is a chordal graph. In this paper, we consider the following problem: Given a graph $G$ , does the graph have a chordal cut? We show that $K_{2,2,2}$ -free hole-edge-disjoint graphs have chordal cuts if they satisfy a certain condition.

preprint2011arXiv

The competition number of a graph and the dimension of its hole space

The competition graph of a digraph D is a (simple undirected) graph which has the same vertex set as D and has an edge between x and y if and only if there exists a vertex v in D such that (x,v) and (y,v) are arcs of D. For any graph G, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number k(G) of G is the smallest number of such isolated vertices. In general, it is hard to compute the competition number k(G) for a graph G and it has been one of important research problems in the study of competition graphs to characterize a graph by its competition number. Recently, the relationship between the competition number and the number of holes of a graph is being studied. A hole of a graph is a cycle of length at least 4 as an induced subgraph. In this paper, we conjecture that the dimension of the hole space of a graph is no smaller than the competition number of the graph. We verify this conjecture for various kinds of graphs and show that our conjectured inequality is indeed an equality for connected triangle-free graphs.

preprint2011arXiv

The competition number of a graph in which any two holes share at most one edge

The competition graph of a digraph D is a (simple undirected) graph which has the same vertex set as D and has an edge between x and y if and only if there exists a vertex v in D such that (x,v) and (y,v) are arcs of D. For any graph G, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number k(G) of G is the smallest number of such isolated vertices. In general, it is hard to compute the competition number k(G) for a graph G and it has been one of important research problems in the study of competition graphs to characterize a graph by its competition number. A hole of a graph is a cycle of length at least 4 as an induced subgraph. It holds that the competition number of a graph cannot exceed one plus the number of its holes if G satisfies a certain condition. In this paper, we show that the competition number of a graph with exactly h holes any two of which share at most one edge is at most h+1, which generalizes the existing results on this subject.

preprint2010arXiv

Graphs having many holes but with small competition numbers

The competition number k(G) of a graph G is the smallest number k such that G together with k isolated vertices added is the competition graph of an acyclic digraph. A chordless cycle of length at least 4 of a graph is called a hole of the graph. The number of holes of a graph is closely related to its competition number as the competition number of a graph which does not contain a hole is at most one and the competition number of a complete bipartite graph $K_{\lfloor \frac{n}{2} \rfloor, \lceil \frac{n}{2} \rceil}$ which has so many holes that no more holes can be added is the largest among those of graphs with n vertices. In this paper, we show that even if a connected graph G has many holes, the competition number of G can be as small as 2 under some assumption. In addition, we show that, for a connected graph G with exactly h holes and at most one non-edge maximal clique, if all the holes of G are pairwise edge-disjoint and the clique number $ω= ω(G)$ of G satisfies $2 \leq ω\leq h+1$ , then the competition number of G is at most $h - ω+ 3$ .

preprint2009arXiv

The competition number of a graph with exactly two holes

Let D be an acyclic digraph. The competition graph of D is a graph which has the same vertex set as D and has an edge between x and y if and only if there exists a vertex v in D such that (x,v) and (y,v) are arcs of D. For any graph G, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number k(G) of G is the smallest number of such isolated vertices. A hole of a graph is a cycle of length at least 4 as an induced subgraph. In 2005, Kim [5] conjectured that the competition number of a graph with h holes is at most h+1. Though Li and Chang [8] and Kim et al. [7] showed that her conjecture is true when the holes do not overlap much, it still remains open for the case where the holes share edges in an arbitrary way. In order to share an edge, a graph must have at least two holes and so it is natural to start with a graph with exactly two holes. In this paper, the conjecture is proved true for such a graph.

Suh-Ryung Kim

Research overview

Is this your work?

20 publications

Digraphs whose m-step competition graphs are trees

Planarity of generalized ladder graphs

Counting independent sets in Riordan graphs

On $(1,2)$ -step competition graphs of bipartite tournaments

On the competition graphs of $d$ -partial orders

On the competition graphs of $d$ -partial orders

On the partial order competition dimensions of chordal graphs

On the partial order competition dimensions of chordal graphs

On the phylogeny graphs of degree-bounded digraphs

On the safe set of Cartesian product of two complete graphs

A matrix equation $X^n = aI$

On consecutive edge magic total labeling of connected bipartite graphs

On the matrix sequence $\{Γ(A^m)\}_{m=1}^\infty$ for a Boolean matrix $A$ whose digraph is linearly connected

Competitively tight graphs

The competition hypergraphs of doubly partial orders

Holes and a chordal cut in a graph

The competition number of a graph and the dimension of its hole space

The competition number of a graph in which any two holes share at most one edge

Graphs having many holes but with small competition numbers

The competition number of a graph with exactly two holes

See the researcher in context

Building this map preview

Suh-Ryung Kim

Research overview

Is this your work?

20 publications

Digraphs whose m-step competition graphs are trees

Planarity of generalized ladder graphs

Counting independent sets in Riordan graphs

On (1,2)(1,2)(1,2)-step competition graphs of bipartite tournaments

On the competition graphs of ddd-partial orders

On the competition graphs of ddd-partial orders

On the partial order competition dimensions of chordal graphs

On the partial order competition dimensions of chordal graphs

On the phylogeny graphs of degree-bounded digraphs

On the safe set of Cartesian product of two complete graphs

A matrix equation Xn=aIX^n = aIXn=aI

On consecutive edge magic total labeling of connected bipartite graphs

On the matrix sequence {Γ(Am)}m=1∞\{Γ(A^m)\}_{m=1}^\infty{Γ(Am)}m=1∞​ for a Boolean matrix AAA whose digraph is linearly connected

Competitively tight graphs

The competition hypergraphs of doubly partial orders

Holes and a chordal cut in a graph

The competition number of a graph and the dimension of its hole space

The competition number of a graph in which any two holes share at most one edge

Graphs having many holes but with small competition numbers

The competition number of a graph with exactly two holes

See the researcher in context

Building this map preview

On $(1,2)$ -step competition graphs of bipartite tournaments

On the competition graphs of $d$ -partial orders

On the competition graphs of $d$ -partial orders

A matrix equation $X^n = aI$

On the matrix sequence $\{Γ(A^m)\}_{m=1}^\infty$ for a Boolean matrix $A$ whose digraph is linearly connected