<p>The notion of word-representable graphs is a generalization of comparability graphs, in which graphs are represented by words. The complexity of word-representation of a word-representable graph is captured through representation number, whereas the corresponding concept is the permutation-representation number for comparability graphs. The graphs with the (permutation-)representation number at most two were characterized in the literature. While certain examples in the class of graphs with the (permutation-)representation number three are known, no characterization for these classes are available. In this work, we prove that the representation number of melon graphs is at most three. Further, we characterize the class of melon graphs restricted to comparability graphs and show that their permutation-representation number is also at most three. Moreover, this work characterizes the word-representable line graphs of melon graphs and establish that their representation number is at most three.</p>

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

Word-Representation of Melon Graphs

  • Khyodeno Mozhui,
  • K. V. Krishna

摘要

The notion of word-representable graphs is a generalization of comparability graphs, in which graphs are represented by words. The complexity of word-representation of a word-representable graph is captured through representation number, whereas the corresponding concept is the permutation-representation number for comparability graphs. The graphs with the (permutation-)representation number at most two were characterized in the literature. While certain examples in the class of graphs with the (permutation-)representation number three are known, no characterization for these classes are available. In this work, we prove that the representation number of melon graphs is at most three. Further, we characterize the class of melon graphs restricted to comparability graphs and show that their permutation-representation number is also at most three. Moreover, this work characterizes the word-representable line graphs of melon graphs and establish that their representation number is at most three.