|کد مقاله||کد نشریه||سال انتشار||مقاله انگلیسی||ترجمه فارسی||نسخه تمام متن|
|4949888||1364262||2017||6 صفحه PDF||سفارش دهید||دانلود کنید|
A graph G=(V,E) is word-representable if there exists a word w over the alphabet V such that letters x and y alternate in w if and only if (x,y)âE for each xâ y. The set of word-representable graphs generalizes several important and well-studied graph families, such as circle graphs, comparability graphs, 3-colorable graphs, graphs of vertex degree at most 3, etc. By answering an open question from HalldÃ³rsson etÂ al. (2011), in the present paper we show that not all graphs of vertex degree at most 4 are word-representable. Combining this result with some previously known facts, we derive that the number of n-vertex word-representable graphs is 2n23+o(n2).
Journal: Discrete Applied Mathematics - Volume 216, Part 1, 10 January 2017, Pages 136-141