Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userWord-representability of triangulations of grid-covered cylinder graphs
141
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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$).
rate research
Read More
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). 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 $xy$ is an edge in $E$. In this paper we initiate the study of word-representable Toeplitz graphs, which are Riordan graphs of the Appell type. We prove that several general classes of Toeplitz graphs are word-representable, and we also provide a way to construct non-word-representable Toeplitz graphs. Our work not only merges the theories of Riordan matrices and word-representable graphs via the notion of a Riordan graph, but also it provides the first systematic study of word-representability of graphs defined via patterns in adjacency matrices. Moreover, our paper introduces the notion of an infinite word-representable Riordan graph and gives several general examples of such graphs. It is the first time in the literature when the word-representability of infinite graphs is discussed.
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 that a tree is 12-representable if and only if it is a double caterpillar. Moreover, Jones et al. initiated the study of 12-representability of induced subgraphs of a grid graph, and asked whether it is possible to characterize such graphs. This question in is meant to be about induced subgraphs of a grid graph that consist of squares, which we call square grid graphs. However, an induced subgraph in a grid graph does not have to contain entire squares, and we call such graphs line grid graphs. In this paper we answer the question of Jones et al. by providing a complete characterization of $12$-representable square grid graphs in terms of forbidden induced subgraphs. Moreover, we conjecture such a characterization for the line grid graphs and give a number of results towards solving this challenging conjecture. Our results are a major step in the direction of characterization of all 12-representable graphs since beyond our characterization, we also discuss relations between graph labelings and 12-representability, one of the key open questions in the area.
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 decomposable graph and $G$ is well-covered with a perfect matching of Konig type $e_{1},...,e_{g}$ without square with two $e_i$s. We characterize well-covered graphs without 3-cycles, 5-cycles and 7-cycles. Also, we study when graphs without 3-cycles and 5-cycles are vertex decomposable or shellable. Furthermore, we give some properties and relations between critical, extendables and shedding vertices. Finally, we characterize unicyclic graphs with each one of the following properties: unmixed, vertex decomposable, shellable and Cohen-Macaulay.
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 Part~II, we proceed further on to the contractible case. We propose two different novel characterizations of contractible HCs, from which we construct digraphs for enumerating the contractible HCs. Given the impression which the computational data for $m leq 9$ convey, we conjecture that the asymptotic domination of the contractible HCs versus the non-contractible HCs, among the total number of HCs, depends on the parity of $m$.}
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
