Scholarlink

<p>As an analog of intersection graphs among digraphs, <i>catch digraphs</i> were introduced by Hiroshi Maehara in 1984. Later on, Prisner focused his research on <i>interval catch digraphs</i>, which he identified as diasteroidal triple free digraphs. It has been used to solve a variety of real-world challenges, such as networking, telecommunication operations, traffic control, and location problems. <i>Oriented catch digraphs</i> are those catch digraphs that have exactly one edge direction attached to each edge of the corresponding underlying graph. In this article, we consider two important subclasses of oriented catch digraphs, namely, <i>oriented interval catch digraphs</i> and <i>oriented circular-arc catch digraphs</i>. First, we characterize those oriented interval catch digraphs whose underlying graphs are trees in terms of forbidden subdigraphs. Next, we provide a characterization of connected proper oriented interval catch digraphs whose underlying graphs are chordal, by determining the complete list of forbidden induced subdigraphs. Another interesting result is characterizing oriented circular-arc catch digraphs, which are tournaments.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

On Some Subclasses of Oriented Catch Digraphs

  • 期刊论文

  • 发表日期：

    2025年1月20日

查看全文
  • Sanchita Paul

摘要

As an analog of intersection graphs among digraphs, catch digraphs were introduced by Hiroshi Maehara in 1984. Later on, Prisner focused his research on interval catch digraphs, which he identified as diasteroidal triple free digraphs. It has been used to solve a variety of real-world challenges, such as networking, telecommunication operations, traffic control, and location problems. Oriented catch digraphs are those catch digraphs that have exactly one edge direction attached to each edge of the corresponding underlying graph. In this article, we consider two important subclasses of oriented catch digraphs, namely, oriented interval catch digraphs and oriented circular-arc catch digraphs. First, we characterize those oriented interval catch digraphs whose underlying graphs are trees in terms of forbidden subdigraphs. Next, we provide a characterization of connected proper oriented interval catch digraphs whose underlying graphs are chordal, by determining the complete list of forbidden induced subdigraphs. Another interesting result is characterizing oriented circular-arc catch digraphs, which are tournaments.