ﻻ يوجد ملخص باللغة العربية
A graph $G=(V,E)$ is word-representable if there exists a word $w$ over the alphabet $V$ such that letters $x$ and $y$, $x eq y$, alternate in $w$ if and only if $(x,y)in E$. Halld{o}rsson et al. have shown that a graph is word-representable if and only if it admits a so-called semi-transitive orientation. A corollary to this result is that any 3-colorable graph is word-representable. Akrobotu et al. have shown that a triangulation of a grid graph is word-representable if and only if it is 3-colorable. This result does not hold for triangulations of grid-covered cylinder graphs, namely, there are such word-representable graphs with chromatic number 4. In this paper we show that word-representability of triangulations of grid-covered cylinder graphs with three sectors (resp., more than three sectors) is characterized by avoiding a certain set of six minimal induced subgraphs (resp., wheel graphs $W_5$ and $W_7$).
Distinct letters $x$ and $y$ alternate in a word $w$ if after deleting in $w$ all letters but the copies of $x$ and $y$ we either obtain a word of the form $xyxycdots$ (of even or odd length) or a word of the form $yxyxcdots$ (of even or odd length).
The notion of a 12-representable graph was introduced by Jones et al.. This notion generalizes the notions of the much studied permutation graphs and co-interval graphs. It is known that any 12-representable graph is a comparability graph, and also t
In this paper we give two characterizations of the $p times q$-grid graphs as co-edge-regular graphs with four distinct eigenvalues.
Let $G=(V,E)$ be a graph. If $G$ is a Konig graph or $G$ is a graph without 3-cycles and 5-cycle, we prove that the following conditions are equivalent: $Delta_{G}$ is pure shellable, $R/I_{Delta}$ is Cohen-Macaulay, $G$ is unmixed vertex decomposabl
In this series of papers, the primary goal is to enumerate Hamiltonian cycles (HCs) on the grid cylinder graphs $P_{m+1}times C_n$, where $n$ is allowed to grow whilst $m$ is fixed. In Part~I, we studied the so-called non-contractible HCs. Here, in P