Polygon-circle and word-representable graphs |
| |
| Institution: | Global Academy of Agriculture and Food Security, University of Edinburgh, Scotland;Computing and Information Science, University of Strathclyde, Scotland;National Research University Higher School of Economics, Moscow, Russia;Ishlinsky Institute for Problems in Mechanics of the Russian Academy of Sciences, Moscow, Russia;Faculty of Mathematics and Computer Science, Babeş-Bolyai University, Str. Mihail Kogalniceanu Nr. 1, 400084 Cluj-Napoca, Romania;Department of Electronics, Computing and Mathematics, University of Derby, Kedleston Road, Derby, DE22 1GB, United Kingdom;Department of Electronics, Computing and Mathematics, University of Derby, Kedleston Road, Derby, DE22 1GB, United Kingdom;Department of Electronics, Computing and Mathematics, University of Derby, Markeaton Street, Derby, DE22 3AW, United Kingdom;Department of Applied Mathematics, Tunghai University, Taichung, Taiwan, PR China;Department of Applied Mathematics, National Chung Hsing University, Taichung, Taiwan, PR China;Former Head and Professor, Department of Applied Mathematics, Delhi Technological University, New Bawana Road, Delhi- 110042, India |
| |
| Abstract: | We describe work on the relationship between the independently-studied polygon-circle graphs and word-representable graphs.A graph G = (V, E) is word-representable if there exists a word w over the alpha-bet V such that letters x and y form a subword of the form xyxy ⋯ or yxyx ⋯ iff xy is an edge in E. Word-representable graphs generalise several well-known and well-studied classes of graphs S. Kitaev, A Comprehensive Introduction to the Theory of Word-Representable Graphs, Lecture Notes in Computer Science 10396 (2017) 36–67; S. Kitaev, V. Lozin, “Words and Graphs”, Springer, 2015]. It is known that any word-representable graph is k-word-representable, that is, can be represented by a word having exactly k copies of each letter for some k dependent on the graph. Recognising whether a graph is word-representable is NP-complete (S. Kitaev, V. Lozin, “Words and Graphs”, Springer, 2015, Theorem 4.2.15]). A polygon-circle graph (also known as a spider graph) is the intersection graph of a set of polygons inscribed in a circle M. Koebe, On a new class of intersection graphs, Ann. Discrete Math. (1992) 141–143]. That is, two vertices of a graph are adjacent if their respective polygons have a non-empty intersection, and the set of polygons that correspond to vertices in this way are said to represent the graph. Recognising whether an input graph is a polygon-circle graph is NP-complete M. Pergel, Recognition of polygon-circle graphs and graphs of interval filaments is NP-complete, Graph-Theoretic Concepts in Computer Science: 33rd Int. Workshop, Lecture Notes in Computer Science, 4769 (2007) 238–247]. We show that neither of these two classes is included in the other one by showing that the word-representable Petersen graph and crown graphs are not polygon-circle, while the non-word-representable wheel graph W5 is polygon-circle. We also provide a more refined result showing that for any k ≥ 3, there are k-word-representable graphs which are neither (k −1)-word-representable nor polygon-circle. |
| |
| Keywords: | polygon-circle graph word-representable graph Petersen graph |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
