Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userWord-representability of Toeplitz graphs
57
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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$).
Let $X$ be a simplicial complex on vertex set $V$. We say that $X$ is $d$-representable if it is isomorphic to the nerve of a family of convex sets in $mathbb{R}^d$. We define the $d$-boxicity of $X$ as the minimal $k$ such that $X$ can be written as the intersection of $k$ $d$-representable simplicial complexes. This generalizes the notion of boxicity of a graph, defined by Roberts. A missing face of $X$ is a set $tausubset V$ such that $tau otin X$ but $sigmain X$ for any $sigmasubsetneq tau$. We prove that the $d$-boxicity of a simplicial complex on $n$ vertices without missing faces of dimension larger than $d$ is at most $leftlfloorfrac{1}{d+1}binom{n}{d}rightrfloor$. The bound is sharp: the $d$-boxicity of a simplicial complex whose set of missing faces form a Steiner $(d,d+1,n)$-system is exactly $frac{1}{d+1}binom{n}{d}$.
For an integer $n>2$, a rank-$n$ matroid is called an $n$-spike if it consists of $n$ three-point lines through a common point such that, for all $kin{1, 2, ..., n - 1}$, the union of every set of $k$ of these lines has rank $k+1$. Spikes are very special and important in matroid theory. In 2003 Wu found the exact numbers of $n$-spikes over fields with 2, 3, 4, 5, 7 elements, and the asymptotic values for larger finite fields. In this paper, we prove that, for each prime number $p$, a $GF(p$) representable $n$-spike $M$ is only representable on fields with characteristic $p$ provided that $n ge 2p-1$. Moreover, $M$ is uniquely representable over $GF(p)$.
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.
We confirm the equitable $Delta$-coloring conjecture for interval graphs and establish the monotonicity of equitable colorability for them. We further obtain results on equitable colorability about square (or Cartesian) and cross (or direct) products of graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
