토플리츠 행렬의 행 그래프

Abstract

이 논문에서는 토플리츠 행렬의 행 그래프에 대해 연구했다. 행 그래프에 대한 개념은 1984년 Green berg 외. 에서 소개되었고, 이는 1968년 Cohen에서 소개한 경쟁그래프와 밀접하게 관련되어있다.

아주 복잡한 토플리츠 행렬의 행 그래프에 대해 이해하기 위해, 행 그래프가 삼각형을 가지지 않는 토플리츠 행렬부터 연구했다. 만약 어떤 토플리츠 행렬의 행 그래프가 삼각형을 가지지 않는다면, 그 행렬의 행의 원소의 합은 $2$ 이하임을 보였다. 게다가, 행 그래프는 연결 성분으로 경로와 회로만을 가지고, 그 길이의 종류가 제한됨을 보였다. 또한 토플리츠 행렬의 행 그래프가 회로 성분 하나로 이루어진 경우, 경로 성분 하나로 이루어진 경우, 특정한 경로 성분을 가지는 경우에 대해 연구했다. 특히, 토플리츠 행렬의 행 그래프가 회로 성분 하나가 될 조건을 완벽히 분석했다.

In this paper, we study row graphs of Toeplitz matrices. The notion of row graphs was introduced by Greenberg~{\em et al.} in 1984 and is closely related to the notion of competition graphs, which has been extensively studied since Cohen had introduced it in 1968.

To understand the structure of the row graphs of Toeplitz matrices, which seem to be quite complicated, we have begun with Toeplitz matrices whose row graphs are triangle-free. We could show that if the row graph $G$ of a Toeplitz matrix $T$ is triangle-free, then $T$ has the maximum row sum at most $2$. Furthermore, it turns out that $G$ is a disjoint union of paths and cycles whose lengths cannot vary that much in such a case. Then we study $(0,1)$-Toeplitz matrices whose row graphs have only path components, only cycle components, and a cycle component of specific length, respectively. In particular, we completely characterize a $(0,1)$-Toeplitz matrix whose row graph is a cycle.