Determining the representation number and the permutation-representation number (referred to as the prn) of bipartite graphs is known to be computationally hard. Nonetheless, in the literature, there are results for some specific classes of graphs such as trees, even cycles, ladder graphs, and crown graphs. In this paper, we focus on a subclass of bipartite graphs known as stacked book graphs and show that for a stacked book graph, the prn is at most three. Subsequently, we prove that the representation number and the prn of a stacked book graph are the same. We also provide a complete classification of stacked book graphs with respect to their prn.

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

The Representation Number and the prn of Stacked Book Graphs

  • Khyodeno Mozhui,
  • K. V. Krishna

摘要

Determining the representation number and the permutation-representation number (referred to as the prn) of bipartite graphs is known to be computationally hard. Nonetheless, in the literature, there are results for some specific classes of graphs such as trees, even cycles, ladder graphs, and crown graphs. In this paper, we focus on a subclass of bipartite graphs known as stacked book graphs and show that for a stacked book graph, the prn is at most three. Subsequently, we prove that the representation number and the prn of a stacked book graph are the same. We also provide a complete classification of stacked book graphs with respect to their prn.